ViST

ViST: a dynamic index method for querying XML data by tree structures. 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.


References in zbMATH (referenced in 13 articles )

Showing results 1 to 13 of 13.
Sorted by year (citations)

  1. Lee, Chun-Hee; Chung, Chin-Wan: Efficient search in graph databases using cross filtering (2014)
  2. Tahraoui, Mohammed Amin; Pinel-Sauvagnat, Karen; Laitang, Cyril; Boughanem, Mohand; Kheddouci, Hamamache; Ning, Lei: A survey on tree matching and XML retrieval (2013)
  3. Lee, SangKeun; Ryu, Byung-Gul; Wu, Kun-Lung: Examining the impact of data-access cost on XML twig pattern matching (2012) ioport
  4. Ning, Bo; Liu, Chengfei: XML filtering with Xpath expressions containing parent and ancestor axes (2012) ioport
  5. Li, Guoliang; Feng, Jianhua; Wang, Jianyong; Zhou, Lizhu: Incremental sequence-based frequent query pattern mining from XML queries (2009) ioport
  6. Mandreoli, Federica; Martoglia, Riccardo; Zezula, Pavel: Principles of Holism for sequential twig pattern matching (2009) ioport
  7. Gao, Jun; Wang, Tengjiao; Yang, Dongqing: XFlat: Query-friendly encrypted XML view publishing (2008) ioport
  8. Li, Changqing; Ling, Tok Wang; Hu, Min: Efficient updates in dynamic XML data: From binary string to quaternary string (2008) ioport
  9. Ng, Patrick K. L.; Ng, Vincent T. Y.: Rrsi: Indexing XML data for proximity twig queries (2008) ioport
  10. Candan, K. Selçuk; Kim, Jong Wook; Liu, Huan; Suvarna, Reshma: Discovering mappings in hierarchical data from multiple sources using the inherent structure (2006) ioport
  11. Candan, K. Selçuk; Kim, Jong Wook; Liu, Huan; Suvarna, Reshma: Discovering mappings in hierarchical data from multiple sources using the inherent structure (2006) ioport
  12. Min, Kyung-Sub; Kim, Hyoung-Joo: A path-based node filtering method for efficient structural joins (2005)
  13. Chen, Zhiyuan; Li, Chen; Pei, Jian; Tao, Yufei; Wang, Haixun; Wang, Wei; Yang, Jiong; Yang, Jun; Zhang, Donghui: Recent progress on selected topics in database research. -- A report by nine young Chinese researchers working in the United States. (2003)