Holistic twig joins: optimal XML pattern matching

By Nicolas Bruno, Nick Koudas, Divesh Srivastava. ACM SIGMOD Conference, 2002

1,036 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, Information Systems, Signal Processing

View Paper: https://www.semanticscholar.org/paper/101af12224e5a8b942e6724a7feff6c352826a94

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Information Systems

In Signal Processing

Citations in the corpus

Graphs-at-a-time: query language and access methods for graph databases (2008, background): “Tree pattern matching thus plays an important role in XML query processing [1, 6].”
Schema-Free XQuery (2004, methodology): “Our algorithm is inspired by the stack-based family of algorithms for structural join [6, 7, 8, 10], and is limited to XQuery implementations that can support”
From Region Encoding To Extended Dewey: On Efficient Processing of XML Twig Pattern Matching (2005, methodology): “…of designing a proper labeling scheme, various methods have been proposed that are based on tree - traversal order(e.g. extended preorder [12]), textual positions of the start and end tags (e.g. region encoding [3]), path expressions(e.g. Dewey ID [22], PID [2]) or prime numbers (e.g. [25]).”
MonetDB/XQuery: a fast XQuery processor powered by a relational engine (2006, methodology): “In this sense, loop-lifted staircase join becomes more similar to alternative stack-based approaches such as structural join [1] and holistic twig join [ 7 ], though these algorithms lack pruning and skipping, and support the descendant axis only (and child relatively inefficiently, as a post-filter”
Holistic Twig Joins on Indexed XML Documents (2003, methodology): “Recently, there have been many proposals that advocate building certain indices on XML data to accelerate query processing [4, 7, 8, 3].”
Efficient algorithms for processing XPath queries (2002, methodology): “…evaluating axes that work more e(cid:14)ciently in practice have been proposed in the context of structural joins (see e.g. [Al-Khalifa et al. 2002; Bruno et al. 2002]) and XML-frontends for relational database management systems [Grust et al. 2004], so the main role of this section is to provide…”
High-performance complex event processing over streams (2006, methodology): “2 Active Instance Stacks (AIS) in SASE appear similar to PathStacks for XML pattern matching [3] in stack arrangements.”
Efficient Structural Joins on Indexed XML Documents (2002, methodology): “Our solutions can be easily extended to incorporate the techniques in [5] as long as the element lists are appropriately indexed.”