Optimizing Frequency Queries for Data Mining Applications

Overview

Data mining algorithms use various Trie and bitmap-based representations to optimize the support (i.e., frequency) counting performance. This paper compares the memory requirements and support counting performance of FP Tree, and Compressed Patricia Trie against several novel variants of vertical bit vectors. First, borrowing ideas from the VLDB domain, they compress vertical bit vectors using WAH encoding. Second, they evaluate the Gray code rank-based transaction reordering scheme, and show that in practice, simple lexicographic ordering, obtained by applying LSB Radix sort, outperforms this scheme.