{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:53:33Z","timestamp":1773482013374,"version":"3.50.1"},"reference-count":70,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,5,29]],"date-time":"2024-05-29T00:00:00Z","timestamp":1716940800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by-nc-sa\/4.0\/"}],"funder":[{"name":"Hong Kong RGC Grants","award":["C2004-21GF, C2003-23Y"],"award-info":[{"award-number":["C2004-21GF, C2003-23Y"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,29]]},"abstract":"<jats:p>The evaluation of top-k conjunctive queries, a staple in business analysis, often requires evaluating the conjunctive query prior to filtering the top-k results, leading to a significant computational overhead within Database Management Systems (DBMSs). While efficient algorithms have been proposed, their integration into DBMSs remains arduous. We introduce relational algorithms, a paradigm where each algorithmic step is expressed by a relational operator. This allows the algorithm to be represented as a set of SQL queries, enabling easy deployment across different systems that support SQL. We introduce two novel relational algorithms, level-k and product-k, specifically designed for evaluating top-k conjunctive queries and demonstrate that level-k achieves optimal running time for top-k free-connex queries. Furthermore, these algorithms enable easy translation into an oblivious algorithm for secure query evaluations. The presented algorithms are not only theoretically optimal but also exhibit eminent efficiency in practice. The experiment results show significant improvements, with our rewritten SQL outperforming the baseline by up to 6 orders of magnitude. Moreover, our secure implementations not only achieve substantial speedup compared to the baseline with secure guarantees but even surpass those baselines that have no secure guarantees.<\/jats:p>","DOI":"10.1145\/3654971","type":"journal-article","created":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T09:44:53Z","timestamp":1717062293000},"page":"1-27","source":"Crossref","is-referenced-by-count":3,"title":["Relational Algorithms for Top-k Query Evaluation"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0959-5536","authenticated-orcid":false,"given":"Qichen","family":"Wang","sequence":"first","affiliation":[{"name":"Hong Kong Baptist University, Hong Kong SAR, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4167-8670","authenticated-orcid":false,"given":"Qiyao","family":"Luo","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong SAR, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7856-2527","authenticated-orcid":false,"given":"Yilei","family":"Wang","sequence":"additional","affiliation":[{"name":"Alibaba Cloud, Hangzhou, China"}]}],"member":"320","published-online":{"date-parts":[[2024,5,30]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"DuckDB. https:\/\/duckdb.org\/."},{"key":"e_1_2_1_2_1","unstructured":"PostgreSQL. https:\/\/www.postgre.org\/."},{"key":"e_1_2_1_3_1","unstructured":"Relational Algorithms for Top-k Query Evaluation Source Code Repository. https:\/\/github.com\/lambdaSQL\/TopK-CQ."},{"key":"e_1_2_1_4_1","unstructured":"SNAP. https:\/\/snap.stanford.edu\/snap\/."},{"key":"e_1_2_1_5_1","unstructured":"SparkSQL. https:\/\/spark.apache.org\/sql\/."},{"key":"e_1_2_1_6_1","volume-title":"Foundations of databases","author":"Abiteboul Serge","unstructured":"Serge Abiteboul, Richard Hull, and Victor Vianu. 1995. Foundations of databases. Addison-Wesley Longman Publishing Co., Inc."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056105"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3548606.3560670"},{"key":"e_1_2_1_10_1","volume-title":"Computer Science Logic","author":"Bagan Guillaume","unstructured":"Guillaume Bagan, Arnaud Durand, and Etienne Grandjean. 2007. On Acyclic Conjunctive Queries and Constant Delay Enumeration. In Computer Science Logic. Springer Berlin Heidelberg, Berlin, Heidelberg, 208--222."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/3055330.3055334"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/3291264.3291274"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322389"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62213"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/3510397.3510407"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s001459910006"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450263"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2014.2302434"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389729"},{"key":"e_1_2_1_20_1","unstructured":"T. H. Cormen C. E. Leiserson R. L. Rivest and C. Stein. 2009. Introduction to Algorithms (3rd ed.). The MIT Press."},{"key":"e_1_2_1_21_1","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms, 3rd Edition. MIT Press. http:\/\/mitpress.mit.edu\/books\/introduction-algorithms","edition":"3"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3555041.3589715"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3510397.3510401"},{"key":"e_1_2_1_24_1","volume-title":"Ranked Enumeration of Conjunctive Query Results. In 24th International Conference on Database Theory (ICDT","author":"Deep Shaleen","year":"2021","unstructured":"Shaleen Deep and Paraschos Koutris. 2021. Ranked Enumeration of Conjunctive Query Results. In 24th International Conference on Database Theory (ICDT 2021). Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/974121.974142"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"David Evans Vladimir Kolesnikov and Mike Rosulek. 2018. A Pragmatic Introduction to Secure Multi-Party Computation.","DOI":"10.1561\/9781680835090"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322390"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/375551.375567"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559890"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing. 218--229","author":"Goldreich O.","unstructured":"O. Goldreich, S. Micali, and A. Wigderson. 1987. How to Play ANY Mental Game. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing. 218--229."},{"key":"e_1_2_1_31_1","volume-title":"dioids and semirings: new models and algorithms","author":"Gondran Michel","unstructured":"Michel Gondran and Michel Minoux. 2008. Graphs, dioids and semirings: new models and algorithms. Vol. 41. Springer Science & Business Media."},{"key":"e_1_2_1_32_1","volume-title":"Cem Okulmus, Reinhard Pichler, and Alexander Selzer.","author":"Gottlob Georg","year":"2023","unstructured":"Georg Gottlob, Matthias Lanzinger, Davide Mario Longo, Cem Okulmus, Reinhard Pichler, and Alexander Selzer. 2023. Structure-Guided Query Evaluation: Towards Bridging the Gap from Theory to Practice. arXiv preprint arXiv:2303.02723 (2023)."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3457374"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303979"},{"key":"e_1_2_1_35_1","volume-title":"Information Security and Cryptology -- ICISC","author":"Hamada Koki","year":"2012","unstructured":"Koki Hamada, Ryo Kikuchi, Dai Ikarashi, Koji Chida, and Katsumi Takahashi. 2013. Practically Efficient Multi-party Sorting Protocols from Comparison Sort Algorithms. In Information Security and Cryptology -- ICISC 2012. 202--216."},{"key":"e_1_2_1_36_1","volume-title":"Scape: Scalable Collaborative Analytics System on Private Database with Malicious Security. In 2022 IEEE 38th International Conference on Data Engineering (ICDE). 1740--1753","author":"Han Feng","year":"2022","unstructured":"Feng Han, Lan Zhang, Hanwen Feng, Weiran Liu, and Xiangyang Li. 2022. Scape: Scalable Collaborative Analytics System on Private Database with Malicious Security. In 2022 IEEE 38th International Conference on Data Engineering (ICDE). 1740--1753."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/2824032.2824090"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589298"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064027"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 29th International Conference on Very Large Data Bases -","volume":"29","author":"Ilyas Ihab F.","unstructured":"Ihab F. Ilyas, Walid G. Aref, and Ahmed K. Elmagarmid. 2003. Supporting Top-K Join Queries in Relational Databases. In Proceedings of the 29th International Conference on Very Large Data Bases - Volume 29 (Berlin, Germany) (VLDB '03). VLDB Endowment, 754--765."},{"key":"e_1_2_1_41_1","volume-title":"Soliman","author":"Ilyas Ihab F.","year":"2008","unstructured":"Ihab F. Ilyas, George Beskales, and Mohamed A. Soliman. 2008. A Survey of Top-k Query Processing Techniques in Relational Database Systems. ACM Comput. Surv. 40, 4, Article 11 (oct 2008), 58 pages. https:\/\/doi.org\/10.1145\/ 1391729.1391730"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902293"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3426865"},{"key":"e_1_2_1_44_1","volume-title":"Answering Conjunctive Queries with Inequalities. In 18th International Conference on Database Theory (ICDT","author":"Koutris Paraschos","year":"2015","unstructured":"Paraschos Koutris, Tova Milo, Sudeepa Roy, and Dan Suciu. 2015. Answering Conjunctive Queries with Inequalities. In 18th International Conference on Database Theory (ICDT 2015). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407814"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066173"},{"key":"e_1_2_1_47_1","volume-title":"20th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2023","author":"Liagouris John","year":"2023","unstructured":"John Liagouris, Vasiliki Kalavri, Muhammad Faisal, and Mayank Varia. 2023. SECRECY: Secure collaborative analytics in untrusted clouds. In 20th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2023, Boston, MA, April 17--19, 2023, Mahesh Balakrishnan and Manya Ghobadi (Eds.). USENIX Association, 1031--1056. https: \/\/www.usenix.org\/conference\/nsdi23\/presentation\/liagouris"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.80"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/3494124.3494146"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272743.1272749"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00040"},{"key":"e_1_2_1_52_1","volume-title":"Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. Association for Computing Machinery, 35--52","author":"Mohassel Payman","year":"2018","unstructured":"Payman Mohassel and Peter Rindal. 2018. ABY3: A Mixed Protocol Framework for Machine Learning. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. Association for Computing Machinery, 35--52."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3372297.3423358"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/645927.672365"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3180143"},{"key":"e_1_2_1_56_1","volume-title":"Proceedings of the 30th Conference on USENIX Security Symposium.","author":"Poddar Rishabh","unstructured":"Rishabh Poddar, Sukrit Kalra, Avishay Yanai, Ryan Deng, Raluca Ada Popa, and Joseph M. Hellerstein. 2021. Senate: A Maliciously-Secure MPC Platform for Collaborative Analytics. In Proceedings of the 30th Conference on USENIX Security Symposium."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702405954"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397250"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3383132"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2187980.2188242"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.14778\/3579075.3579080"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517830"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/3604437.3604450"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/3517804.3524142"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559862"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2588572"},{"key":"e_1_2_1_67_1","first-page":"82","article-title":"Algorithms for acyclic database schemes","volume":"81","author":"Yannakakis Mihalis","year":"1981","unstructured":"Mihalis Yannakakis. 1981. Algorithms for acyclic database schemes. In VLDB, Vol. 81. 82--94.","journal-title":"VLDB"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.5555\/1382436.1382751"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544870"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/3269206.3271791"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654971","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3654971","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T14:37:24Z","timestamp":1755787044000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654971"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,29]]},"references-count":70,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,5,29]]}},"alternative-id":["10.1145\/3654971"],"URL":"https:\/\/doi.org\/10.1145\/3654971","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,29]]}}}