Partitioned Inverted Index Compression Using Hierarchical Dirichlet Process
Runzhu He, Youli Qu · 2024
In large-scale search engines, the core data structure is the inverted index, essentially a collection of integer sequences within inverted lists. Precise partitioning of these sequences enables efficient query processing. The concept of partitioning by quantity and universe has been established for years in the field of inverted index compression algorithms. The volume of data within a post-partitioned area, defined as density, is a key determinant of the compression efficiency of partitioned inverted index algorithms. Previous studies have focused on creating denser partitioned areas atop existing inverted file indexes to improve compression efficiency. This paper proposes a novel approach that utilizes the Hierarchical Dirichlet Process model to extract document themes, categorizes documents based on these themes, and then constructs file indexes accordingly to create denser partitioned areas. Compared with other inverted index compression methods, this algorithm achieves a favorable balance between time and space efficiency.