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: hc9d95a731264fb39
Venue: SIGMOD
Year: 2024
Pagerank: 4.9769913e-05
Overall Rank: 11,532 | 22.50%
DOI: 10.1145/3654971
PDF: Download (CC BY-NC-SA 4.0)

Incoming Non-self Citations Over Time

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

Authors

1. Qichen Wang (Hong Kong Baptist University)
2. Qiyao Luo (Hong Kong University of Science and Technology)
3. Yilei Wang (Alibaba)

BibTeX Citation

@inproceedings{wang_sigmod24,
        title = {{Relational Algorithms for Top-k Query Evaluation}},
        author = {Wang, Qichen and Luo, Qiyao and Wang, Yilei},
        series = {{SIGMOD} '24},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3654971},
        url = {https://dl.acm.org/doi/10.1145/3654971},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,895	Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees	2025	SIGMOD	5.9534254e-05
10,512	Sketch-based Secure Query Processing for Streaming Data	2026	SIGMOD	4.9769913e-05
10,519	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD	4.9769913e-05
11,036	Instance-Optimal Acyclic Joins: From Theory to Systems	2026	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 29 of 29 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.0010679903
315	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021236408
357	FAQ: Questions Asked Frequently	2016	PODS	0.00020013731
507	Supporting Incremental Join Queries on Ranked Inputs	2001	VLDB	0.00017093562
524	Supporting Top-k Join Queries in Relational Databases	2003	VLDB	0.00016902116
813	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.00013722638
962	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD	0.00012818013
1,091	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00012068611
1,496	SMCQL: Secure Querying for Federated Databases	2017	VLDB	0.00010479934
1,570	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	0.0001020376
2,020	Shrinkwrap: Efficient SQL Query Processing in Differentially Private Data Federations	2019	VLDB	9.1714694e-05
2,076	Efficient Oblivious Database Joins	2020	VLDB	9.0798814e-05
2,302	On Functional Aggregate Queries with Additive Inequalities	2019	PODS	8.6687541e-05
2,310	Secure kNN Computation on Encrypted Databases	2009	SIGMOD	8.662463e-05
2,366	Hypertree Decompositions and Tractable Queries	1999	PODS	8.5614655e-05
2,517	On the Enumeration Complexity of Unions of Conjunctive Queries	2019	PODS	8.3550625e-05
2,593	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	8.2429717e-05
4,510	Conjunctive Queries with Comparisons	2022	SIGMOD	6.5673056e-05
4,745	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	6.4369578e-05
5,061	Change Propagation Without Joins	2023	VLDB	6.2897936e-05
5,124	Secure Query Processing with Data Interoperability in a Cloud Database Environment	2014	SIGMOD	6.2620601e-05
5,233	Robust and Efficient Algorithms for Rank Join Evaluation	2009	SIGMOD	6.2167391e-05
5,757	SDB: A Secure Query Processing System with Data Interoperability	2015	VLDB	6.0029557e-05
6,533	Query Evaluation by Circuits	2022	PODS	5.7519838e-05
6,547	Ranked Enumeration of Join Queries with Projections	2022	VLDB	5.7488764e-05
6,738	What Is the Price for Joining Securely? Benchmarking Equi-Joins in Trusted Execution Environments	2022	VLDB	5.6912817e-05
7,294	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD	5.5616228e-05
9,355	External Merge Sort for Top-K Queries: Eager input filtering guided by histograms	2020	SIGMOD	5.1876576e-05
10,157	Threshold Queries in Theory and in the Wild	2022	VLDB	5.0691578e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	524	Supporting Top-k Join Queries in Relational Databases	2003	VLDB
2	143	Optimization of Nonrecursive Queries	1986	VLDB
3	1,899	Querying Multiple Features of Groups in Relational Databases	1996	VLDB
4	6,198	Towards an Efficient Evaluation of General Queries: Quantifier and Disjunction Processing Revisited	1989	SIGMOD
5	7,294	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD
6	6,469	Output-sensitive Conjunctive Query Evaluation	2024	PODS
7	5,941	RankSQL: Supporting Ranking Queries in Relational Database Management Systems	2005	VLDB
8	7,621	Processing Top-k Join Queries	2010	VLDB
9	643	Evaluating Top-k Selection Queries	1999	VLDB
10	962	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD