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: 6993
Venue: SIGMOD
Year: 2024
Pagerank: 5.093636e-05
Overall Rank: 11,183 | 23.28%
DOI: 10.1145/3654971

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 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,434	Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees	2025	SIGMOD	5.8799421e-05
10,289	Sketch-based Secure Query Processing for Streaming Data	2026	SIGMOD	5.093636e-05
10,296	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD	5.093636e-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.0010828372
321	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021283186
358	FAQ: Questions Asked Frequently	2016	PODS	0.00020243592
499	Supporting Incremental Join Queries on Ranked Inputs	2001	VLDB	0.00017431827
509	Supporting Top-k Join Queries in Relational Databases	2003	VLDB	0.00017220967
816	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.00013827772
973	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD	0.00012874284
1,109	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00012142685
1,459	SMCQL: Secure Querying for Federated Databases	2017	VLDB	0.00010717725
1,549	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	0.00010390168
1,984	Shrinkwrap: Efficient SQL Query Processing in Differentially Private Data Federations	2019	VLDB	9.3540912e-05
2,045	Efficient Oblivious Database Joins	2020	VLDB	9.2632279e-05
2,266	On Functional Aggregate Queries with Additive Inequalities	2019	PODS	8.8391372e-05
2,319	Secure kNN Computation on Encrypted Databases	2009	SIGMOD	8.7577497e-05
2,330	Hypertree Decompositions and Tractable Queries	1999	PODS	8.7447066e-05
2,468	On the Enumeration Complexity of Unions of Conjunctive Queries	2019	PODS	8.5358494e-05
2,745	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	8.1747954e-05
4,575	Conjunctive Queries with Comparisons	2022	SIGMOD	6.6223692e-05
4,985	Change Propagation Without Joins	2023	VLDB	6.412102e-05
4,997	Secure Query Processing with Data Interoperability in a Cloud Database Environment	2014	SIGMOD	6.4080849e-05
5,138	Robust and Efficient Algorithms for Rank Join Evaluation	2009	SIGMOD	6.3495536e-05
5,601	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	6.1540123e-05
5,629	SDB: A Secure Query Processing System with Data Interoperability	2015	VLDB	6.1429079e-05
6,398	Query Evaluation by Circuits	2022	PODS	5.8867918e-05
6,412	Ranked Enumeration of Join Queries with Projections	2022	VLDB	5.8836116e-05
6,601	What Is the Price for Joining Securely? Benchmarking Equi-Joins in Trusted Execution Environments	2022	VLDB	5.8246671e-05
7,161	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD	5.6852987e-05
9,172	External Merge Sort for Top-K Queries: Eager input filtering guided by histograms	2020	SIGMOD	5.3092396e-05
9,961	Threshold Queries in Theory and in the Wild	2022	VLDB	5.1879626e-05

Semantically Similar Papers

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