3
$\begingroup$

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?

$\endgroup$

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.