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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.