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.9605343e-05
Overall Rank: 11,581 | 22.38%
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,911	Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees	2025	SIGMOD	5.9338021e-05
10,578	Sketch-based Secure Query Processing for Streaming Data	2026	SIGMOD	4.9605343e-05
10,585	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD	4.9605343e-05
11,097	Instance-Optimal Acyclic Joins: From Theory to Systems	2026	VLDB	4.9605343e-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.0010688884
318	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021178303
357	FAQ: Questions Asked Frequently	2016	PODS	0.00020048899
505	Supporting Top-k Join Queries in Relational Databases	2003	VLDB	0.00017162373
511	Supporting Incremental Join Queries on Ranked Inputs	2001	VLDB	0.00017061618
815	The Dynamic Yannakakis Algorithm: Compact and Efficient Query Processing Under Updates	2017	SIGMOD	0.00013682594
941	RankSQL: Query Algebra and Optimization for Relational Top-k Queries	2005	SIGMOD	0.00012938573
1,096	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00012035761
1,499	SMCQL: Secure Querying for Federated Databases	2017	VLDB	0.00010445281
1,568	AJAR: Aggregations and Joins over Annotated Relations	2016	PODS	0.00010178045
2,032	Shrinkwrap: Efficient SQL Query Processing in Differentially Private Data Federations	2019	VLDB	9.1412376e-05
2,086	Efficient Oblivious Database Joins	2020	VLDB	9.0498577e-05
2,316	On Functional Aggregate Queries with Additive Inequalities	2019	PODS	8.6404062e-05
2,321	Secure kNN Computation on Encrypted Databases	2009	SIGMOD	8.6338201e-05
2,376	Hypertree Decompositions and Tractable Queries	1999	PODS	8.5345413e-05
2,526	On the Enumeration Complexity of Unions of Conjunctive Queries	2019	PODS	8.3274934e-05
2,602	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	8.2157154e-05
4,527	Conjunctive Queries with Comparisons	2022	SIGMOD	6.5466033e-05
4,730	Optimal Join Algorithms Meet Top-k	2020	SIGMOD	6.4313418e-05
5,080	Change Propagation Without Joins	2023	VLDB	6.2689958e-05
5,144	Secure Query Processing with Data Interoperability in a Cloud Database Environment	2014	SIGMOD	6.2413538e-05
5,254	Robust and Efficient Algorithms for Rank Join Evaluation	2009	SIGMOD	6.1964074e-05
5,769	SDB: A Secure Query Processing System with Data Interoperability	2015	VLDB	5.9831062e-05
6,545	Query Evaluation by Circuits	2022	PODS	5.7329641e-05
6,557	Ranked Enumeration of Join Queries with Projections	2022	VLDB	5.7298671e-05
6,757	What Is the Price for Joining Securely? Benchmarking Equi-Joins in Trusted Execution Environments	2022	VLDB	5.6724628e-05
7,311	Computing the Difference of Conjunctive Queries Efficiently	2023	SIGMOD	5.5432326e-05
9,381	External Merge Sort for Top-K Queries: Eager input filtering guided by histograms	2020	SIGMOD	5.170504e-05
10,192	Threshold Queries in Theory and in the Wild	2022	VLDB	5.052396e-05

Semantically Similar Papers

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