A Tree-Based Indexing Approach for Diverse Textual Similarity Search

Minghe Yu, Chengliang Chai, Ge Yu

Introduction

In the era of big data, finding "similar" text strings—such as identifying duplicate movie titles or searching for research papers by keywords—is a computationally expensive task. The standard approach is a "top-k" search, where the system returns the $k$ most similar records to a query. However, existing methods face two major hurdles: efficiency (slow real-time performance on large datasets) and flexibility (indexes are often locked to a specific similarity measure like Jaccard). This paper introduces a novel tree-based indexing approach designed to provide a high-performance, unified model capable of supporting diverse similarity measures without sacrificing speed.

Methodology

The proposed approach organizes data into a tree structure using three core pillars:

1. Offline Clustering

Instead of a flat list, records are grouped into branches using k-means clustering logic based on textual similarity. Each node in the tree stores a representative record, the maximum distance to any of its descendants ($d_{max}$), and a summary of all tokens found in its subtree.

2. Efficient Storage

To maintain memory efficiency, the index uses a hybrid storage model for token sets. Frequent tokens are stored in Hash Tables for rapid access, while less frequent ones are packed into Bloom Filters. This probabilistic approach allows the system to quickly verify if a branch might contain a match without the overhead of storing every word explicitly.

3. Dual Pruning Strategies

The system's speed is largely derived from its ability to "prune" or skip branches that cannot mathematically contain a top-k result. The authors implement two specific types:

  • Triangle Inequality Pruning: Leverages the geometric relationship between the query, the current node, and the node's $d_{max}$ to discard distant branches.
  • Token Bound Pruning: Calculates the minimum number of shared words required to exceed the current $k$-th best result. If a branch lacks sufficient overlapping tokens, it is discarded.
Evolution of the tree structure from initial to final fanout.

Experimental Evaluation

The researchers evaluated the index using three real-world datasets: DBLP (over 1 million publication records), IMDB (movie metadata), and PubMed (medical titles). These datasets provide a robust test of the method across varying record lengths and domains.

Key Insights

  • The "Goldilocks" Fanout: Performance is highly sensitive to "fanout" (the number of children per node). A fanout of approximately 400 was found to be the optimal "sweet spot"; smaller values lead to excessive tree depth, while larger values create bottlenecks at individual nodes.
  • Measure Independence: By clustering based on general similarity rather than a specific formula, the index remains effective even when switching between token-based (e.g., Jaccard) and character-based (e.g., Edit Distance) measures.

Results

The proposed algorithm was compared against the Flamingo (DivideSkip) baseline, a high-performing standard in the field.

  • Speed: On the DBLP dataset, the tree-based approach completed a top-5 search in 50.3 ms, significantly faster than Flamingo's 122.3 ms.
  • Scalability: The search time grew slowly as dataset size increased to 1 million records, demonstrating superior scalability for big data contexts.
  • Pruning Power: The combination of Triangle Inequality and Token Bound pruning reduced the number of accessed nodes by an order of magnitude compared to using either strategy in isolation.

Conclusion

This tree-based indexing approach offers a scalable and flexible solution for top-k textual similarity searches. Future work includes extending this structure to "similarity joins" (finding all similar pairs between two large datasets) and integrating human-in-the-loop crowdsourcing to handle edge cases that automated measures might miss.

Summary updated

BibTeX
@article{yu2021tree,
  author = {Minghe Yu and Chengliang Chai and Ge Yu},
  title = {{A Tree-Based Indexing Approach for Diverse Textual Similarity Search}},
  journal = {IEEE Access},
  year = {2021},
  doi = {10.1109/access.2020.3022057},
}
Figure