Assigning identifiers to documents to enhance the clustering property of fulltext indexes

Fabrizio Silvestri, Salvatore Orlando, Raffaele PeregoSIGIR 2004 · DOI

TL;DR

This paper proposes novel algorithms for assigning document identifiers to improve the compression efficiency of full-text indexes in web search engines. By strategically reordering document IDs, they significantly reduce the average gap between consecutive IDs in posting lists, leading to better compression ratios for various encoding schemes.

What Problem Does This Paper Address?

Web search engines rely on massive inverted indexes to quickly retrieve documents. These indexes store posting lists, which are sequences of document identifiers (DocIDs) associated with each term. To manage the enormous size of these indexes, efficient compression techniques are crucial. A common approach is to store the differences between consecutive DocIDs (d-gaps) and compress these d-gaps using variable-length encoding. The effectiveness of these compression methods hinges on the "clustering property" of posting lists – the tendency for small d-gaps to be more frequent. This paper addresses the challenge of enhancing this clustering property by intelligently assigning document identifiers. Previous methods for reordering DocIDs were computationally expensive and impractical for large-scale web collections.

Methods

The authors propose two main categories of algorithms for assigning document identifiers:

  • Top-Down Assignment: These algorithms recursively partition the document collection based on similarity.
  • Transactional B&B: An adaptation of a previous algorithm, it splits documents into partitions and recursively processes them.
  • Bisecting: A simpler approach that uses randomly chosen documents as initial centers for partitioning.
  • Bottom-Up Assignment: These algorithms group similar documents together progressively.
  • Single-pass k-means: Leverages the first pass of the k-means clustering algorithm to group documents.
  • k-scan: A simplified k-means variant that performs k scans, selecting documents most similar to a chosen centroid at each step.

A key innovation is the "Transactional Model," which allows these assignment algorithms to operate during the indexing process, rather than requiring a pre-built index. This model uses a bag-of-words representation but ignores within-document term frequencies, relying on MD5 digests for term representation and Jaccard similarity for document similarity.

Datasets

The algorithms were evaluated on the publicly available Google Programming Contest collection, which contains approximately 916,000 documents from real websites with about 1.4 million distinct terms. This collection was preprocessed into the transactional model.

Key Insights and Ideas

  • The "Clustering Property" is Key: The core idea is that by making d-gaps smaller and more frequent, compression becomes much more effective, regardless of the specific encoding scheme.
  • On-the-Fly Assignment is Practical: The "Transactional Model" allows DocID assignment to be integrated into the indexing pipeline, making it scalable for web-scale collections. This is a significant improvement over previous methods that required a fully built index.
  • Bottom-Up Approaches are Faster: While top-down methods offer theoretical elegance, bottom-up approaches like k-scan demonstrate significantly better performance in terms of completion time for large datasets.
  • Trade-offs Exist: There's a clear trade-off between the computational cost of assignment algorithms and the compression gains achieved. The original B&B algorithm achieved slightly better compression but was prohibitively slow and memory-intensive.

Key Results

  • The proposed algorithms achieved significant improvements in compression ratios, with gains of up to 20.81% reported for some encoding schemes.
  • The k-scan algorithm demonstrated the best performance in terms of completion time, exhibiting a linear trend with collection size, outperforming other proposed algorithms and previous methods.
  • The TRANSACTIONAL B&B and Bisecting algorithms showed a typical nlogn time complexity, characteristic of top-down approaches.
  • All proposed algorithms showed a linear space occupancy trend, making them suitable for large collections.
  • While the original B&B algorithm achieved slightly better compression (around 10% gain), the proposed methods were orders of magnitude faster and more memory-efficient.

Limitations and Future Work

  • Original B&B Superiority: The paper acknowledges that the original B&B algorithm, despite its impracticality, achieved slightly better compression gains. This is attributed to its ability to exploit term sampling, which was not feasible in the transactional version.
  • Future Work: The authors plan to test their algorithms with newer encoding methods (specifically mentioning a method from [2]) and investigate adaptations for dynamically changing document collections. They also suggest exploring the impact of term sampling in their transactional models.

Summary updated

BibTeX
@inproceedings{silvestri2004assigning,
  author = {Fabrizio Silvestri and Salvatore Orlando and Raffaele Perego},
  title = {{Assigning identifiers to documents to enhance the clustering property of fulltext indexes}},
  booktitle = {International ACM SIGIR Conference on Research and Development in Information Retrieval},
  year = {2004},
  doi = {10.1145/1008992.1009046},
}

Loading related content...

Figure