If I understand right then ESP tree is defined as : given any string $x$ of finite length over an alphabet one can construct "an" ESP tree corresponding to it say $T_x$ such that each leaf of the tree is an element of $x$

Now the above immediately implies that every node in $T_x$ corresponds to some substring of $x$.

  • This $T_x$ isn't unique - right? Are there any conventions about it? (like is there a convention that ESP must always be such that every vertex has either 2 or 3 children? If yes then why?)

  • As far as I can see one can't create a tree such that every substring will be represented by some vertex. Do we know any optimality results about what is possible at best?

  • Is there a natural relation between this and the notion of sketching and embedding of metrics?


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.