Relational Algorithms for Top-k Query Evaluation

Summary: Relational algorithms for top-k conjunctive queries: level-k/product-k express each step as relational operators, so the whole method compiles to portable SQL and even to oblivious secure evaluation. Level-k is optimal for top-k free-connex queries, with reported gains up to 10^6x over baselines. (summarized by gpt-5.4-mini on May 24 2026)

Paper ID: 6931
Venue: SIGMOD
Year: 2024
Pagerank: 4.1945683e-05
Overall Rank: 10,970 | 23.69%
DOI: 10.1145/3654971

Incoming Non-self Citations Over Time

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

Authors

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
7,467	Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees	2025	SIGMOD	4.7218691e-05

Outgoing Citations (Sorted by Pagerank)

Showing 28 of 28 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
7	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0015496097
552	Supporting Incremental Join Queries on Ranked Inputs	2001	VLDB	0.00020310903
583	FAQ: Questions Asked Frequently	2016	PODS	0.00019717214
674	Supporting Top-k Join Queries in Relational Databases	2003	VLDB	0.00018327585
1,056	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.0001441128
1,262	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD	0.00012986539
1,307	SMCQL: Secure Querying for Federated Databases	2017	VLDB	0.0001266709
1,442	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00011956109
2,169	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	9.3845975e-05
2,655	Secure kNN Computation on Encrypted Databases	2009	SIGMOD	8.3622816e-05
2,670	Efficient Oblivious Database Joins	2020	VLDB	8.3379158e-05
2,673	Shrinkwrap: Efficient SQL Query Processing in Differentially Private Data Federations	2019	VLDB	8.3333418e-05
2,796	Hypertree Decompositions and Tractable Queries	1999	PODS	8.1112658e-05
3,006	On Functional Aggregate Queries with Additive Inequalities	2019	PODS	7.7299363e-05
3,371	On the Enumeration Complexity of Unions of Conjunctive Queries	2019	PODS	7.1696145e-05
3,715	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	6.8220943e-05
5,302	Secure Query Processing with Data Interoperability in a Cloud Database Environment	2014	SIGMOD	5.5786331e-05
5,373	Robust and Efficient Algorithms for Rank Join Evaluation	2009	SIGMOD	5.5425231e-05
5,718	Conjunctive Queries with Comparisons	2022	SIGMOD	5.3552123e-05
5,784	What Is the Price for Joining Securely? Benchmarking Equi-Joins in Trusted Execution Environments	2022	VLDB	5.328804e-05
5,855	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	5.3006096e-05
5,920	SDB: A Secure Query Processing System with Data Interoperability	2015	VLDB	5.2727262e-05
5,967	Change Propagation Without Joins	2023	VLDB	5.250976e-05
7,017	Query Evaluation by Circuits	2022	PODS	4.8603097e-05
7,162	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD	4.8132423e-05
7,166	Ranked Enumeration of Join Queries with Projections	2022	VLDB	4.8124491e-05
9,123	External Merge Sort for Top-K Queries: Eager input filtering guided by histograms	2020	SIGMOD	4.3920263e-05
9,798	Threshold Queries in Theory and in the Wild	2022	VLDB	4.2818172e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
143	Optimization of Nonrecursive Queries	1986	VLDB	0.00041510555
674	Supporting Top-k Join Queries in Relational Databases	2003	VLDB	0.00018327585
1,754	Querying Multiple Features of Groups in Relational Databases	1996	VLDB	0.00010670609
6,090	Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited	1989	SIGMOD	5.2148332e-05
7,162	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD	4.8132423e-05
8,966	Output-sensitive Conjunctive Query Evaluation	2024	PODS	4.4193184e-05
6,882	RankSQL: Supporting Ranking Queries in Relational Database Management Systems	2005	VLDB	4.8963901e-05
7,692	Processing Top-k Join Queries	2010	VLDB	4.6761366e-05
805	Evaluating Top-k Selection Queries	1999	VLDB	0.00016437265
1,262	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD	0.00012986539