An Efficient Diversity-Aware Method for the Empty-Answer Problem

Yuto Ikeda, Chuan Xiao, Makoto OnizukaDOLAP 2024 · OpenReview

Introduction

In modern database systems, users often encounter the "empty-answer problem" when their search criteria are too restrictive. For instance, a query for a car that is "Red," "Under $10,000," and has "Less than 5,000 miles" may yield zero results. Traditional solutions involve query relaxation (dropping conditions) or ranking by similarity. However, these methods often fail to provide a diverse set of results, leading to a set of "near-misses" that are too similar to be useful for exploration. This paper proposes a high-speed, diversity-aware solution that achieves significant performance gains over traditional methods.

The Challenge of Diversity

Calculating diversity—ensuring that the results shown to a user are sufficiently different from one another—is computationally expensive, typically $O(nk^2)$. In large-scale databases, performing exhaustive pairwise comparisons to find the most diverse set of records is a major bottleneck. The goal is to provide diverse "near-miss" results instantly without sacrificing the relevance of the data.

Proposed Methodology: Query-Level MMR

The core innovation of this research is a two-stage approach centered on Maximal Marginal Relevance (MMR). MMR is a metric that balances relevance to the original query against the diversity of the result set.

Instead of applying MMR directly to millions of records, the authors propose Query-Level MMR. In this stage, the system treats relaxed queries (subsets of the original conditions) as proxies for the records themselves. By finding a diverse set of relaxed queries, the system naturally identifies diverse segments of the data.

Conceptual diagram of query-level relaxation and record-level MMR.

Following the selection of diverse queries, the system performs a final, smaller-scale record-level MMR pass to select the best $k$ results. To optimize this process, the authors utilize a greedy co-occurrence strategy to prioritize unused condition combinations and incorporate cardinality estimation (using tools like DeepDB) to avoid queries that would return no data.

Experimental Evaluation

The method was evaluated using the Cars dataset, a standard benchmark containing 128,443 records and 31 boolean columns. The test suite consisted of 167 queries with varying complexity (4 to 10 conjunctive conditions).

Results and Discussion

The proposed method demonstrated exceptional performance across two primary metrics: execution speed and result quality.

  • Efficiency: The "proposed base" method achieved a 100x to 300x speedup compared to the standard greedy search baseline. Furthermore, the execution time scaled linearly with the number of requested results ($k$), whereas traditional methods slowed down significantly.
  • Quality: Despite the massive increase in speed, the quality of the results—measured by the MMR score—remained high. The proposed method significantly outperformed random selection and closely approached the quality of the exhaustive greedy search.
Comparison of MMR scores across different recommendation sizes, showing the proposed methods maintain high quality relative to the greedy baseline.

While the "optimized" version utilizing DeepDB for cardinality estimation improved result reliability, it introduced a 3–7x overhead compared to the base version, suggesting a hybrid approach might be best for real-world applications.

Conclusion

By shifting the focus of diversity calculations from the record level to the query level, this research provides a scalable solution to the empty-answer problem. The approach allows database systems to provide diverse, relevant alternatives to users in real-time, even within large-scale datasets. Future work will look to extend this logic to more complex SQL operations, such as joins and non-conjunctive queries.

Summary updated

BibTeX
@inproceedings{ikeda2024efficient,
  author = {Yuto Ikeda and Chuan Xiao and Makoto Onizuka},
  title = {{An Efficient Diversity-Aware Method for the Empty-Answer Problem}},
  booktitle = {DOLAP},
  year = {2024},
  url = {https://openreview.net/forum?id=sOGB4Edk7G},
}
Figure