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 one or more structure-encoded sequences; and generating the ViST structure comprising: generating a D-Ancestor index; generating an S-Ancestor index; and generating a doc-ID index.