ViSt: A Dynamic Index Method for Querying XML Data by Tree Structures

Haixun Wang, Sanghyun Park, Wei Fan, Philip S. Yu

Research output: Contribution to journalConference articlepeer-review

231 Citations (Scopus)


With the growing importance of XML in data exchange, much research has been done in providing flexible query facilities to extract data from structured XML documents. In this paper, we propose ViST, a novel index structure for searching XML documents. By representing both XML documents and XML queries in structure-encoded sequences, we show that querying XML data is equivalent to finding subsequence matches. Unlike index methods that disassemble a query into multiple sub-queries, and then join the results of these sub-queries to provide the final answers, ViST uses tree structures as the basic unit of query to avoid expensive join operations. Furthermore, ViST provides a unified index on both content and structure of the XML documents, hence it has a performance advantage over methods indexing either just content or structure. ViST supports dynamic index update, and it relies solely on B +Trees without using any specialized data structures that are not well supported by DBMSs. Our experiments show that ViST is effective, scalable, and efficient in supporting structural queries.

Original languageEnglish
Pages (from-to)110-121
Number of pages12
JournalProceedings of the ACM SIGMOD International Conference on Management of Data
Publication statusPublished - 2003
Event2003 ACM SIGMOD International Conference on Management of Data - San Diego, CA, United States
Duration: 2003 Jun 92003 Jun 12

All Science Journal Classification (ASJC) codes

  • Software
  • Information Systems


Dive into the research topics of 'ViSt: A Dynamic Index Method for Querying XML Data by Tree Structures'. Together they form a unique fingerprint.

Cite this