Towards Unifying Advances in Twig Join Algorithms

Grimsmo, N. and Bjørklund, T. A.

Twig joins are key building blocks in current XML indexing systems, and numerous algorithms and useful data structures have been introduced. We give a structured, qualitative analysis of recent advances, which leads to the identification of a number of opportunities for further improvements. Cases where combining competing or orthogonal techniques would be advantageous are highlighted, such as algorithms avoiding redundant computations and schemes for cheaper intermediate result management. We propose some direct improvements over existing solutions, such as reduced memory usage and stronger filters for bottom-up algorithms. In addition we identify cases where previous work has been overlooked or not used to its full potential, such as for virtual streams, or the benefits of previous techniques have been underestimated, such as for skipping joins. Using the identified opportunities as a guide for future work, we are hopefully one step closer to unification of many advances in twig join algorithms.

Cite as: Grimsmo, N. and Bjørklund, T. A. (2010). Towards Unifying Advances in Twig Join Algorithms. In Proc. 21st Australasian Database Conference (ADC 2010) Brisbane, Australia. CRPIT, 104. Shen H.T. and Bouguettaya, A. Eds., ACS. 57-66

(from crpit.com) (local if available)