PRIX

PRIX: indexing and querying XML using prufer sequences. We propose a new way of indexing XML documents and processing twig patterns in an XML database. Every XML document in the database can be transformed into a sequence of labels by Prufer’s method that constructs a one-to-one correspondence between trees and sequences. During query processing, a twig pattern is also transformed into its Prufer sequence. By performing subsequence matching on the set of sequences in the database, and performing a series of refinement phases that we have developed, we can find all the occurrences of a twig pattern in the database. Our approach allows holistic processing of a twig pattern without breaking the twig into root-to-leaf paths and processing these paths individually. Furthermore, we show that all correct answers are found without any false dismissals or false alarms. Experimental results demonstrate the performance benefits of our proposed techniques.


References in zbMATH (referenced in 11 articles )

Showing results 1 to 11 of 11.
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. Caminiti, Saverio; Petreschi, Rossella: Unified parallel encoding and decoding algorithms for Dandelion-like codes (2010)
  5. Jiang, Jin-Hua; Chen, Ke; Li, Xiao-Yan; Chen, Gang; Shou, Li-Dan: Efficient processing of ordered XML twig pattern matching based on extended Dewey (2009)
  6. Li, Guoliang; Feng, Jianhua; Wang, Jianyong; Zhou, Lizhu: Incremental sequence-based frequent query pattern mining from XML queries (2009) ioport
  7. Li, Changqing; Ling, Tok Wang; Hu, Min: Efficient updates in dynamic XML data: From binary string to quaternary string (2008) ioport
  8. Ng, Patrick K. L.; Ng, Vincent T. Y.: Rrsi: Indexing XML data for proximity twig queries (2008) ioport
  9. 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
  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. Wong, Kam-Fai; Yu, Jeffrey Xu; Tang, Nan: Answering XML queries using path-based indexes: a survey (2006) ioport