Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue
Summary: Ultrametric framework for diverse query-answer subsets; with d and delta, yields polynomial-time diversity algorithms under broad conditions. Lower bounds clarify tractability; applied to acyclic conjunctive queries with attribute-order diversity. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
- 1. Marcelo Arenas (Pontifical Catholic University of Chile; RelationalAI)
- 2. Timo Camillo Merkl (Vienna University of Technology)
- 3. Reinhard Pichler (Vienna University of Technology)
- 4. Cristian Riveros (Pontifical Catholic University of Chile)
BibTeX Citation
@inproceedings{arenas_pods24,
address = {New York, NY, USA},
series = {{PODS} '24},
title = {{Towards Tractability of the Diversity of Query Answers: Ultrametrics to the Rescue}},
url = {https://dl.acm.org/doi/10.1145/3695833},
doi = {10.1145/3695833},
booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
publisher = {Association for Computing Machinery},
author = {Arenas, Marcelo and Merkl, Timo Camillo and Pichler, Reinhard and Riveros, Cristian},
year = {2024}
}Incoming Citations (Sorted by Pagerank)
Showing 6 of 6 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 8,728 | Computing A Well-Representative Summary of Conjunctive Query Results | 2024 | PODS | 5.3766157e-05 |
| 9,719 | Subset Sampling over Joins | 2026 | PODS | 5.2319816e-05 |
| 10,153 | Faster Relational Algorithms Using Geometric Data Structures | 2026 | PODS | 5.093636e-05 |
| 10,176 | Clustering with Set Outliers and Applications in Relational Clustering | 2026 | PODS | 5.093636e-05 |
| 10,180 | Query Answering Under Volume-Based Diversity Functions | 2026 | PODS | 5.093636e-05 |
| 11,144 | Improved Approximation Algorithms for Relational Clustering | 2024 | PODS | 5.093636e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 6 of 6 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 362 | Storing and Querying Ordered XML Using a Relational Database System | 2002 | SIGMOD | 0.00020125068 |
| 814 | Hypertree Decompositions: Questions and Answers | 2016 | PODS | 0.00013841737 |
| 2,379 | Structured Search Result Differentiation | 2009 | VLDB | 8.666326e-05 |
| 3,596 | On the Complexity of Query Result Diversification | 2013 | VLDB | 7.2722683e-05 |
| 4,781 | Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries | 2021 | PODS | 6.5116536e-05 |
| 4,967 | DivDB: A System for Diversifying Query Results | 2011 | VLDB | 6.4214182e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| # | Overall Rank | Paper | Year | Venue |
|---|---|---|---|---|
| 1 | 11,523 | The Complexity of Conjunctive Queries with Degree 2 | 2022 | PODS |
| 2 | 7,119 | RC-Index: Diversifying Answers to Range Queries | 2018 | VLDB |
| 3 | 298 | Answering Queries Using Templates With Binding Patterns (Extended Abstract) | 1995 | PODS |
| 4 | 4,781 | Tractable Orders for Direct Access to Ranked Answers of Conjunctive Queries | 2021 | PODS |
| 5 | 12,331 | Answering Top-k Queries Over a Mixture of Attractive and Repulsive Dimensions | 2012 | VLDB |
| 6 | 8,728 | Computing A Well-Representative Summary of Conjunctive Query Results | 2024 | PODS |
| 7 | 6,293 | Query Refinement for Diversity Constraint Satisfaction | 2024 | VLDB |
| 8 | 1,807 | DisC Diversity: Result Diversification based on Dissimilarity and Coverage | 2013 | VLDB |
| 9 | 3,596 | On the Complexity of Query Result Diversification | 2013 | VLDB |
| 10 | 10,180 | Query Answering Under Volume-Based Diversity Functions | 2026 | PODS |