1. A method of generating a virtual suffix tree (ViST) structure for searching XML documents, comprising: receiving one or more XML documents; converting the one or more XML documents into respective structure-encoded sequences; generating the ViST structure comprising: generating a D-Ancestor index of node pairs in the respective structure-encoded sequences; generating an S-Ancestor index of labels in one or more suffix trees corresponding to respective ones of the structure-encoded sequences; and generating a doc-ID index encoding the D-Ancestor index and the S-Ancestor index for each node of the structure-encoded sequences, wherein the encoding of the doc-ID index contains an answer to a query matching a non-contiguous subsequence in the doc-ID index; and updating the ViST structure, the updating comprising: receiving a new XML document; transforming the new XML document into a respecitve structure-encoded sequence; inserting each element of the sequence into the D-Ancestor index to update relationships among nodes of the D-Ancestor index wherein the insertion of at least one of the elements results in the creation of a new node; assigning a new label to the new node based on an estimated number of different elements following the element corresponding to the new node and an occurrence probability of each of the elements following the element corresponding to the new node; and inserting the new label into the S-Ancestor index.