Complexity and algorithms for composite retrieval

Sihem Amer-Yahia, Francesco Bonchi, Carlos Castillo, Esteban Feuerstein, Isabel Méndez-Díaz, Paula ZabalaWWW 2013 · DOI

TL;DR

This paper introduces "composite retrieval," a new paradigm for organizing search results into meaningful "bundles" of items that satisfy complementarity and budget constraints. They propose algorithms to find diverse and high-quality bundles, addressing a gap in traditional ranked lists by offering a more exploratory and improved user experience.

What Problem Does This Paper Address?

Online search has evolved beyond simple keyword queries. Users often need to gather information about multiple related items to complete a task, like planning a trip or finding restaurants in a new city. Current search engines typically return ranked lists of individual items, forcing users to manually sift through and synthesize information. This paper addresses the challenge of automatically organizing these results into coherent "bundles" that are both internally cohesive (items are compatible) and externally diverse (bundles cover different aspects of the user's need), while respecting constraints like budget or complementarity of attributes.

Methods

The authors formalize "composite retrieval" by defining the quality of a bundle based on the similarity of its items and the diversity of the overall set of bundles. They introduce two key concepts:

  • Complementarity: Ensures items within a bundle don't share the same value for a specific attribute (e.g., different cuisines for restaurants).
  • Budget: Limits the cost or size of a bundle.

The core problem is framed as finding a set of k bundles that maximizes a weighted combination of intra-bundle similarity and inter-bundle diversity. They prove this problem is NP-hard, leading them to develop approximation algorithms. Their algorithmic approaches include:

  • Produce-and-Choose (PAC): Generates many valid bundles first, then selects the best k.
  • Cluster-and-Pick (CAP): Clusters items based on compatibility, then picks a good bundle from each cluster.
  • Integer Linear Programming (ILP): An exact algorithm using a Branch-and-Cut approach.

Datasets

The authors evaluated their methods on a large dataset of user-generated restaurant reviews from Yahoo! Local, containing 38,530 restaurants across 149 US cities.

Key Insights and Ideas

  • Bundles Offer a Richer Experience: Moving beyond ranked lists to bundles can significantly improve exploratory search by providing pre-synthesized, contextually relevant information.
  • Balancing Quality and Diversity is Crucial: The effectiveness of composite retrieval hinges on finding the right trade-off between the internal quality of bundles and the diversity of the bundle set.
  • NP-Hardness Requires Approximation: The inherent complexity of finding optimal bundles necessitates efficient approximation algorithms.
  • Heuristics Can Be Highly Effective: Their PAC and CAP heuristics demonstrate competitive performance and significantly better efficiency compared to exact ILP methods.

Key Results

  • Efficiency: Heuristics (CAP and PAC) were an order of magnitude faster than the ILP implementation. CAP achieved a median running time of 2 seconds, while ILP took close to a minute.
  • Effectiveness: The performance of the methods was highly dependent on the scaling parameter γ that balances bundle quality and diversity.
  • When diversity was prioritized (small γ), CAP algorithms performed best.
  • When relevance was prioritized (large γ), PAC methods showed better results.
  • Comparison to ILP: Heuristics produced results comparable to the ILP implementation, with the ILP never achieving more than twice the objective function value of the best heuristic in median experiments.

Limitations and Future Work

  • Limitations: The paper acknowledges that the problem is NP-hard, meaning exact solutions are computationally expensive for large datasets. The effectiveness of heuristics is tied to parameter tuning (γ).
  • Future Work: The authors plan to explore personalized composite retrieval, where bundles are tailored to individual user interests or specific query constraints (e.g., finding bundles including a particular item). This extends the work towards item recommendation with a more flexible querying mechanism.

Summary updated

BibTeX
@inproceedings{ameryahia2013complexity,
  author = {Sihem Amer-Yahia and Francesco Bonchi and Carlos Castillo and Esteban Feuerstein and Isabel Méndez-Díaz and Paula Zabala},
  title = {{Complexity and algorithms for composite retrieval}},
  booktitle = {The Web Conference},
  year = {2013},
  doi = {10.1145/2487788.2487822},
}
Figure