TL;DR
This paper introduces a novel method for efficiently searching large document collections for similar content. By intelligently partitioning the search index and routing documents to specific partitions based on their content, they achieve scalable similarity searches with minimal loss in accuracy, even when querying only a small fraction of the total index.
What Problem Does This Paper Address?
Finding documents that are textually similar to a given query document is a common and important task in many applications, such as identifying duplicate content, managing archival data, or finding related information. A standard approach involves extracting "features" from documents and using an inverted index to map these features to the documents they appear in. When a query document is presented, its features are used to look up matching documents in the index.
However, as the size of document repositories grows into the millions or billions, a single, monolithic inverted index becomes a significant bottleneck. It struggles to handle the sheer volume of updates and queries, leading to scalability issues. While partitioning the index across multiple servers is a natural solution, naive partitioning schemes (like those based on hashing individual features) require accessing many partitions for each document, negating the benefits of distribution. The core problem this paper addresses is how to partition a large feature index in a way that allows for efficient, parallelized similarity searches while maintaining high accuracy and minimizing the number of partitions accessed per query.
Methods
The paper proposes a content-based document routing and index partitioning scheme. Instead of routing individual features to different partitions, their approach routes all features of a document to a small, selected subset of partitions.
Here's how it works:
- Feature Extraction: Documents are first processed to extract a set of "features." The paper uses a modified chunk-based feature extraction method, where documents are broken into chunks, and characteristic fingerprints of these chunks serve as features. This is based on the idea that similar documents will share many of the same chunks and thus have overlapping feature sets.
- Document Routing Algorithm: When a document is ingested or a query is made, its features are used to determine which partitions to route to. The algorithm selects the
msmallest "bottom" features from the document's feature set. Each of thesemfeatures is then hashed and taken moduloK(the total number of partitions) to determine the target partition. This ensures that a document is routed to a small, fixed number (m) of partitions. - Index Partitioning: The feature index is partitioned into
Ksub-indices, each hosted on a separate server. Each partition stores a reverse map from features to the documents that contain them. - Scalable Search: At query time, the same routing algorithm is applied to the query document. Only the
mselected partitions are queried in parallel. The results from these partitions are then merged.
The key innovation is routing the entire document to a small subset of partitions, rather than distributing individual features across many. This is motivated by a generalization of Broder's theorem, which suggests that if two documents are similar, their "bottom" features are likely to be the same, increasing the probability they will be routed to the same partition. Using m > 1 further amplifies this probability.
Datasets
The experiments were conducted on a dataset of 179,874 HTML files from Hewlett Packard's internal support documents. This dataset contained 1,504,984 unique features. A subset of 332 files was used as query files (Fq), and the remaining files formed the document repository (Fa).
Key Insights and Ideas
- Content-Driven Routing is Key: The core idea that a document's own content dictates where its features are stored and searched for is crucial. This makes the system stateless and incremental, avoiding the need for global knowledge of the index structure.
- The Power of "Bottom" Features: Routing based on the
msmallest features (the "bottom" features) is surprisingly effective. This leverages the statistical properties of similarity measures (like Jaccard index) and min-wise hashing to ensure that similar documents have a high probability of landing in at least one common partition. - Small
mis Sufficient: The paper demonstrates that even a small routing factor (m, e.g., 3-5) is enough to achieve a high probability of finding relevant documents, significantly reducing the number of partitions queried compared to a monolithic index. - Scalability vs. Recall Trade-off: The approach offers a tunable trade-off. While querying only
mpartitions might lead to a slight decrease in overall recall (missing some weaker similarities), it dramatically improves search speed and scalability. For many applications, retaining the "top-k" results is sufficient, and this method excels at preserving those.
Key Results
- High Similarity Preservation: With
K=128partitions and a routing factor ofm=3, the average similarity measure for queries was over 0.33, close to the 0.342 achieved with a single monolithic index. Form > 4, the average similarity measure was indistinguishable from the monolithic index. - Minimal Impact on Top Results: Figure 6 shows that with
K=128andm=3, over 70% of the top-2 results were identical to those from a monolithic index, and over 90% contained at least one of the original top-2 results. - Significant Partition Size Reduction: When
K=128andm=3, the average partition size was less than 3% of the size of a monolithic index. This indicates substantial storage and query load distribution. - Recall vs. Routing Factor: Figure 5 shows that while overall recall might be lower (e.g., 24% for
m=3), the recall for the top-20 results was much higher (73%), demonstrating that the most relevant results are preserved.
Limitations and Future Work
- Dynamic Partition Growth: The authors acknowledge the need to investigate schemes for dynamically growing the number of partitions and handling overloaded partitions.
- Quantifying Storage Space Loss: Future work will involve quantifying the potential loss in storage space savings due to missed high-similarity files and evaluating if the gains in bandwidth utilization and throughput outweigh this loss.
- Application-Specific Tuning: The paper suggests that for applications requiring all similar documents, one could query all partitions, preserving original recall at the cost of scalability. The current scheme is optimized for scenarios where top results are paramount.
Summary updated