Approximating Opaque Top-k Queries

Summary: Approximates opaque top-k queries with a task-agnostic hierarchical index and a bandit. Histogram-based modeling targets fat tails and yields a constant-factor approximation, with up to 10× speedups over exhaustive scan. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h8c9c52a8fd741011
Venue: SIGMOD
Year: 2025
Pagerank: 4.9605343e-05
Overall Rank: 11,245 | 24.63%
DOI: 10.1145/3725266
PDF: Download (CC BY 4.0)

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Jiwon Chang (University of Rochester)
2. Fatemeh Nargesian (University of Rochester)

BibTeX Citation

@inproceedings{chang_sigmod25,
        title = {{Approximating Opaque Top-k Queries}},
        author = {Chang, Jiwon and Nargesian, Fatemeh},
        series = {{SIGMOD} '25},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3725266},
        url = {https://dl.acm.org/doi/10.1145/3725266},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
5	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0010688884
170	Combining Fuzzy Information from Multiple Systems	1996	PODS	0.0002707332
335	A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search	2021	VLDB	0.0002067515
1,539	Top-k Query Evaluation with Probabilistic Guarantees	2004	VLDB	0.00010292787
1,812	Tuplex: Data Science in Python at Native Code Speed	2021	SIGMOD	9.5747668e-05
2,256	The Design of an LLM-powered Unstructured Analytics System	2025	CIDR	8.7418985e-05
2,258	Evaluating End-to-End Optimization for Data Analytics Applications in Weld	2018	VLDB	8.7387151e-05
3,190	One WITH RECURSIVE is Worth Many GOTOs	2021	SIGMOD	7.5364422e-05
3,397	Putting Pandas in a Box	2021	CIDR	7.3273688e-05
4,302	A Method for Optimizing Opaque Filter Queries	2020	SIGMOD	6.6614501e-05
4,890	Selective Data Acquisition in the Wild for Model Charging	2022	VLDB	6.3508492e-05
5,246	Babelfish: Efficient Execution of Polyglot Queries	2022	VLDB	6.1985833e-05
8,002	Efficient Execution of User-Defined Functions in SQL Queries	2023	VLDB	5.3927693e-05
8,050	NeurDB: On the Design and Implementation of an AI-powered Autonomous Database	2025	CIDR	5.3839177e-05
8,361	MONSOON: Multi-Step Optimization and Execution of Queries with Partially Obscured Predicates	2020	SIGMOD	5.3310744e-05
8,778	Optimizing Video Selection LIMIT Queries With Commonsense Knowledge	2024	VLDB	5.2652839e-05
8,831	ApproxML: Efficient Approximate Ad-Hoc ML Models Through Materialization and Reuse	2019	VLDB	5.2528897e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,793	Supporting Ad-hoc Ranking Aggregates	2006	SIGMOD
2	11,782	Efficient Approximation Framework for Attribute Recommendation	2023	SIGMOD
3	6,043	Answering Top-k Representative Queries on Graph Databases	2014	SIGMOD
4	3,078	Towards Robust Indexing for Ranked Queries	2006	VLDB
5	7,413	Efficient and Generic Evaluation of Ranked Queries	2011	SIGMOD
6	3,116	Top-k Queries on Uncertain Data: On Score Distribution and Typical Answers	2009	SIGMOD
7	6,191	Exact Processing of Uncertain Top-k Queries in Multi-criteria Settings	2018	VLDB
8	12,671	Answering Top-k Queries Over a Mixture of Attractive and Repulsive Dimensions	2012	VLDB
9	8,473	Efficient Top-K Processing Over Query-Dependent Functions	2008	VLDB
10	1,539	Top-k Query Evaluation with Probabilistic Guarantees	2004	VLDB