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: 6932
Venue: SIGMOD
Year: 2024
Pagerank: 4.1905499e-05
Overall Rank: 10,973 | 23.74%
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,465	Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees	2025	SIGMOD	4.7186055e-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
8	Optimal Aggregation Algorithms for Middleware [Extended Abstract]	2001	PODS	0.0015436578
551	Supporting Incremental Join Queries on Ranked Inputs	2001	VLDB	0.00020310856
564	FAQ: Questions Asked Frequently	2016	PODS	0.00020002796
673	Supporting Top-k Join Queries in Relational Databases	2003	VLDB	0.00018325667
1,054	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.00014397587
1,207	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD	0.0001327437
1,291	SMCQL: Secure Querying for Federated Databases	2017	VLDB	0.00012771034
1,452	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00011922523
2,173	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	9.3767985e-05
2,549	Efficient Oblivious Database Joins	2020	VLDB	8.5572389e-05
2,650	Secure kNN Computation on Encrypted Databases	2009	SIGMOD	8.3691955e-05
2,651	Shrinkwrap: Efficient SQL Query Processing in Differentially Private Data Federations	2019	VLDB	8.3680222e-05
2,804	Hypertree Decompositions and Tractable Queries	1999	PODS	8.1039107e-05
3,009	On Functional Aggregate Queries with Additive Inequalities	2019	PODS	7.7230513e-05
3,374	On the Enumeration Complexity of Unions of Conjunctive Queries	2019	PODS	7.1631303e-05
3,702	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	6.8251643e-05
5,287	Secure Query Processing with Data Interoperability in a Cloud Database Environment	2014	SIGMOD	5.5805942e-05
5,379	Robust and Efficient Algorithms for Rank Join Evaluation	2009	SIGMOD	5.5375923e-05
5,728	Conjunctive Queries with Comparisons	2022	SIGMOD	5.350072e-05
5,795	What Is the Price for Joining Securely? Benchmarking Equi-Joins in Trusted Execution Environments	2022	VLDB	5.3236883e-05
5,845	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	5.3057391e-05
5,904	SDB: A Secure Query Processing System with Data Interoperability	2015	VLDB	5.2749823e-05
5,973	Change Propagation Without Joins	2023	VLDB	5.2459364e-05
7,017	Query Evaluation by Circuits	2022	PODS	4.8556471e-05
7,161	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD	4.8086254e-05
7,165	Ranked Enumeration of Join Queries with Projections	2022	VLDB	4.807833e-05
9,121	External Merge Sort for Top-K Queries: Eager input filtering guided by histograms	2020	SIGMOD	4.3878169e-05
9,801	Threshold Queries in Theory and in the Wild	2022	VLDB	4.2777144e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
144	Optimization of Nonrecursive Queries	1986	VLDB	0.00041430126
673	Supporting Top-k Join Queries in Relational Databases	2003	VLDB	0.00018325667
1,754	Querying Multiple Features of Groups in Relational Databases	1996	VLDB	0.00010663123
6,094	Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited	1989	SIGMOD	5.2099705e-05
7,161	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD	4.8086254e-05
8,972	Output-sensitive Conjunctive Query Evaluation	2024	PODS	4.4150824e-05
6,136	RankSQL: Supporting Ranking Queries in Relational Database Management Systems	2005	VLDB	5.1906626e-05
7,660	Processing Top-k Join Queries	2010	VLDB	4.6814547e-05
802	Evaluating Top-k Selection Queries	1999	VLDB	0.00016440813
1,207	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD	0.0001327437