BPI: XML Query Evaluation Using Bitmapped Path Indices

This paper introduces a new technique for fast computation of structural join "Pattern Trees" in XML. Using a small amount of pre-computed path information, typically small enough to fit easily in main memory, the authors are able to render structural join computation almost independent of data set size. The technique is amenable to bit-mapped processing, leading to further speed-up. This paper presents the technique and experimentally evaluates its performance.