Towards unifying advances in twig join algorithms
Nils Grimsmo, Truls Amundsen Bjørklund · 2010
Twig joins are key building blocks in current XML indexing systems, and numerous algorithms and use-ful data structures have been introduced. We give a structured, qualitative analysis of recent advances, which leads to the identification of a number of op-portunities 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 pro-pose some direct improvements over existing solu-tions, such as reduced memory usage and stronger filters for bottom-up algorithms. In addition we iden-tify 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. Us-ing the identified opportunities as a guide for future work, we are hopefully one step closer to unification of many advances in twig join algorithms.