Relaxation in text search using taxonomies

Marcus Fontoura, Vanja Josifovski, Ravi Kumar, Christopher Olston, Andrew Tomkins, Sergei Vassilvitskii

TL;DR

This paper introduces a novel document retrieval model that augments traditional text search with multi-dimensional "taxonomy restrictions." These restrictions, representing hierarchical metadata like categories or locations, can be relaxed at a cost to improve recall, offering a more flexible search experience. The authors propose efficient algorithms for indexing and querying this model, demonstrating significant performance improvements over baseline methods.

What Problem Does This Paper Address?

Traditional information retrieval (IR) systems excel at finding documents based on keywords. However, many real-world search scenarios require more nuanced filtering based on structured metadata. Examples include local search (finding restaurants near a specific location, with flexibility to consider nearby areas) and product search (finding items within specific categories, with the ability to broaden the search to related categories). Existing IR models struggle to incorporate these hierarchical constraints and their inherent "relaxation" (e.g., searching for "pizza parlors" but accepting "Italian restaurants" if necessary). This paper addresses the challenge of efficiently searching documents that are annotated with multiple hierarchical taxonomies, allowing for flexible relaxation of these constraints to balance precision and recall.

Methods

The core of the paper is a new document retrieval model that combines text search with multi-dimensional taxonomy restrictions. Key methodological contributions include:

  • Scoring Function: A new scoring function is introduced that incorporates a static document importance score, a text-based relevance score, and a "taxonomy score." The taxonomy score is calculated as the sum of relaxation costs across multiple taxonomies, where relaxation cost is defined by the distance in the taxonomy tree from the document's assigned node to the query's specified node.
  • Indexing: The authors extend traditional inverted indexes by creating a posting list for each node in each taxonomy. This allows for efficient Boolean queries on taxonomy nodes.
  • Query Processing Algorithms: They decompose query processing into two sub-problems:
  • Online Search for Relaxation Level: Algorithms (bottom-up, top-down, binary search) are proposed to efficiently find the appropriate level of relaxation that yields at least k results while minimizing cost. These algorithms iteratively adjust the search space based on the number of results found.
  • Budgeted Relaxation Search: For a given relaxation budget, algorithms are developed to find all documents within that budget at minimal retrieval cost. This involves query planning to select the most efficient set of underlying index queries to cover the desired search space. For two taxonomies, this problem is solvable exactly using dynamic programming; for three or more, it becomes NP-hard, but efficient approximation algorithms are provided.

Datasets

  • Synthetic Data: Used to control taxonomy characteristics (depth, fanout, multiplicity) and keyword selectivity, allowing for systematic evaluation of algorithm performance.
  • Real-World Data: The Reuters dataset (RCV1) was used, containing 810K English news articles. Documents were classified into two taxonomies: "industry" (996 leaf nodes, depth 7) and "date" (1140 leaf nodes). Queries were generated by selecting pairs of nodes from these taxonomies.

Key Insights and Ideas

  • Taxonomy as a First-Class Citizen: The paper elevates taxonomies from simple metadata to a core component of the search model, enabling flexible and cost-aware retrieval.
  • Cost-Based Relaxation: The explicit modeling of relaxation cost allows for a principled trade-off between finding more relevant documents and incurring higher computational or conceptual costs.
  • Algorithmic Decomposition: Breaking down the problem into finding the right relaxation level and then efficiently retrieving documents within that level is crucial for scalability.
  • Query Planning for Multi-Dimensionality: The challenge of covering a multi-dimensional simplex (representing relaxed constraints) with efficient index queries is a significant contribution, especially the NP-hardness result for more than two dimensions and the provision of approximation algorithms.
  • Performance Gains: The proposed algorithms offer substantial improvements over baseline methods, particularly in scenarios with multiple taxonomy restrictions, highlighting the value of exploiting hierarchical structure.

Key Results

  • Orders of Magnitude Improvement: The proposed algorithms (top-down, binary search) consistently outperform the baseline method (text search followed by post-processing) by orders of magnitude in terms of cursor movements (a proxy for computational cost) on synthetic datasets, especially when multiple taxonomy restrictions are involved.
  • Top-Down and Binary Search Robustness: Top-down search never performs worse than the baseline and often significantly better. Binary search is also highly effective and potentially more robust for deeper taxonomies.
  • Impact of Keyword Selectivity: When keywords are highly selective, the baseline can perform well. However, for less selective keywords, the proposed methods show significant advantages.
  • Benefit of Multiple Queries per Level: Using multiple, more specific queries to cover a relaxation level (rather than a single broad query) dramatically improves performance, especially in high-fanout taxonomies.
  • Real-World Performance: Experiments on the Reuters dataset confirmed the significant performance gains of the proposed algorithms over the baseline, demonstrating their practical applicability.

Limitations and Future Work

  • Taxonomy and Weight Provision: The current framework assumes that taxonomies and their weights are provided as input. The paper acknowledges that learning taxonomies and defining reasonable weights are interesting research questions themselves.
  • Aggressive Search Methods: The paper focuses on conservative search methods for finding the right relaxation level. Investigating aggressive search methods that might abandon a level early based on statistical evidence is suggested as future work.
  • Generalization of Query Planning: While exact solutions are provided for two taxonomies, the NP-hardness for more than two necessitates approximation. Further research into more efficient or tighter approximation algorithms for the general case is implied.
  • Integration of Static Scores: The experimental evaluation primarily focused on keyword and taxonomy restrictions, with static scores being mentioned but not extensively evaluated. Further work could explore the interplay of all three score components.

Summary updated

BibTeX
@article{fontoura2008relaxation,
  author = {Marcus Fontoura and Vanja Josifovski and Ravi Kumar and Christopher Olston and Andrew Tomkins and Sergei Vassilvitskii},
  title = {{Relaxation in text search using taxonomies}},
  journal = {Proc. VLDB Endow.},
  year = {2008},
  url = {https://openreview.net/forum?id=KNttp2POufU},
}
Figure