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: 7205
Venue: SIGMOD
Year: 2025
Pagerank: 4.1905499e-05
Overall Rank: 10,481 | 27.16%
DOI: 10.1145/3725266

Incoming Non-self Citations Over Time

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

Authors

1. Jiwon Chang
2. Fatemeh Nargesian

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
8	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0015436578
72	Combining Fuzzy Information from Multiple Systems	1996	PODS	0.00058498396
763	A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search	2021	VLDB	0.00016963981
1,805	Top-k Query Evaluation with Probabilistic Guarantees	2004	VLDB	0.00010479371
1,884	Tuplex: Data Science in Python at Native Code Speed	2021	SIGMOD	0.00010206514
2,904	Evaluating End-to-End Optimization for Data Analytics Applications in Weld	2018	VLDB	7.9403097e-05
3,639	The Design of an LLM-powered Unstructured Analytics System	2025	CIDR	6.8886648e-05
3,649	One WITH RECURSIVE is Worth Many GOTOs	2021	SIGMOD	6.8764882e-05
4,813	Putting Pandas in a Box	2021	CIDR	5.8993009e-05
4,909	A Method for Optimizing Opaque Filter Queries	2020	SIGMOD	5.8354189e-05
5,386	Selective Data Acquisition in the Wild for Model Charging	2022	VLDB	5.5346315e-05
5,741	Babelfish: Efficient Execution of Polyglot Queries	2022	VLDB	5.3450701e-05
8,162	MONSOON: Multi-Step Optimization and Execution of Queries with Partially Obscured Predicates	2020	SIGMOD	4.5686903e-05
8,365	NeurDB: On the Design and Implementation of an AI-powered Autonomous Database	2025	CIDR	4.5305127e-05
8,580	Efficient Execution of User-Defined Functions in SQL Queries	2023	VLDB	4.4876382e-05
8,646	Optimizing Video Selection LIMIT Queries With Commonsense Knowledge	2024	VLDB	4.4720866e-05
8,651	ApproxML: Efficient Approximate Ad-Hoc ML Models Through Materialization and Reuse	2019	VLDB	4.4710004e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,809	Supporting Ad-hoc Ranking Aggregates	2006	SIGMOD	6.7413981e-05
11,219	Efficient Approximation Framework for Attribute Recommendation	2023	SIGMOD	4.1905499e-05
3,447	Towards Robust Indexing for Ranked Queries	2006	VLDB	7.082382e-05
6,085	Answering Top-k Representative Queries on Graph Databases	2014	SIGMOD	5.2165029e-05
7,273	Efficient and Generic Evaluation of Ranked Queries	2011	SIGMOD	4.775366e-05
3,190	Top-k Queries on Uncertain Data: On Score Distribution and Typical Answers	2009	SIGMOD	7.413338e-05
6,378	Exact Processing of Uncertain Top-k Queries in Multi-criteria Settings	2018	VLDB	5.0844506e-05
12,143	Answering Top-k Queries Over a Mixture of Attractive and Repulsive Dimensions	2012	VLDB	4.1905499e-05
7,966	Efficient Top-K Processing Over Query-Dependent Functions	2008	VLDB	4.6089395e-05
1,805	Top-k Query Evaluation with Probabilistic Guarantees	2004	VLDB	0.00010479371