{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T22:17:18Z","timestamp":1772835438486,"version":"3.50.1"},"reference-count":53,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,11,8]],"date-time":"2024-11-08T00:00:00Z","timestamp":1731024000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGMOD Rec."],"published-print":{"date-parts":[[2024,11,8]]},"abstract":"<jats:p>Ranked enumeration is a query-answering paradigm where the query answers are returned incrementally in order of importance (instead of returning all answers at once). Importance is defined by a ranking function that can be specific to the application, but typically involves either a lexicographic order (e.g., \"ORDER BY R.A, S.B\" in SQL) or a weighted sum of attributes (e.g., \"ORDER BY 3*R.A + 2*S.B\"). Recent work has introduced any-k algorithms for (multi-way) join queries, which push ranking into joins and avoid materializing intermediate results until necessary. The top-ranked answers are returned asymptotically faster than the common join-then-rank approach of database systems, resulting in orders-of-magnitude speedup in practice.<\/jats:p>","DOI":"10.1145\/3703922.3703924","type":"journal-article","created":{"date-parts":[[2024,11,8]],"date-time":"2024-11-08T23:37:24Z","timestamp":1731109044000},"page":"6-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Ranked Enumeration for Database Queries"],"prefix":"10.1145","volume":"53","author":[{"given":"Nikolaos","family":"Tziavelis","sequence":"first","affiliation":[{"name":"UC Santa Cruz"}]},{"given":"Wolfgang","family":"Gatterbauer","sequence":"additional","affiliation":[{"name":"Northeastern University"}]},{"given":"Mirek","family":"Riedewald","sequence":"additional","affiliation":[{"name":"Northeastern University"}]}],"member":"320","published-online":{"date-parts":[[2024,11,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.53"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056105"},{"key":"e_1_2_1_4_1","first-page":"1","article-title":"Ranked Enumeration for MSO on Trees via Knowledge Compilation","volume":"290","author":"Amarilli A.","year":"2024","unstructured":"A. Amarilli, P. Bourhis, F. Capelli, and M. Monet. Ranked Enumeration for MSO on Trees via Knowledge Compilation. In ICDT, volume 290, 25:1--25:18, 2024. doi: 10 . 4230 \/ LIPIcs . ICDT . 2024.25.","journal-title":"ICDT"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/110859440"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3--540--74915--8_18"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556579"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3125644"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2402"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1954-09848-8"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385634.3385636"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2019.58"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322238"},{"key":"e_1_2_1_14_1","first-page":"738","volume-title":"AAAI","author":"Boddy M. S.","year":"1991","unstructured":"M. S. Boddy. Anytime problem solving using dynamic programming. In AAAI, pages 738--743, 1991. url: https:\/\/dl.acm.org\/doi\/abs\/10. 5555\/1865756.1865791."},{"issue":"3","key":"e_1_2_1_16_1","first-page":"10","article-title":"Hypergraph acyclicity revisited","volume":"49","author":"Brault-Baron J.","year":"2016","unstructured":"J. Brault-Baron. Hypergraph acyclicity revisited. ACM Comput. Surv., 49(3), Dec. 2016. doi: 10. 1145\/2983573.","journal-title":"ACM Comput. Surv."},{"key":"e_1_2_1_17_1","first-page":"10","article-title":"Tight fine-grained bounds for direct access on join queries","author":"Bringmann K.","year":"2022","unstructured":"K. Bringmann, N. Carmeli, and S. Mengel. Tight fine-grained bounds for direct access on join queries. In PODS, 427--436, 2022. doi: 10.1145\/ 3517804.3526234.","journal-title":"PODS, 427--436"},{"key":"e_1_2_1_18_1","volume-title":"Geometric Amortization of Enumeration Algorithms. In STACS 2023","volume":"254","author":"Capelli F.","year":"2023","unstructured":"F. Capelli and Y. Strozecki. Geometric Amortization of Enumeration Algorithms. In STACS 2023, volume 254, 18:1--18:22, 2023. doi: 10 . 4230 \/ LIPIcs.STACS.2023.18."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-019-09937--9"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450263"},{"issue":"1","key":"e_1_2_1_21_1","doi-asserted-by":"crossref","first-page":"10","DOI":"10.1145\/3578517","article-title":"Tractable orders for direct access to ranked answers of conjunctive queries","volume":"48","author":"Carmeli N.","year":"2023","unstructured":"N. Carmeli, N. Tziavelis, W. Gatterbauer, B. Kimelfeld, and M. Riedewald. Tractable orders for direct access to ranked answers of conjunctive queries. TODS, 48(1), 2023. doi: 10.1145\/ 3578517.","journal-title":"TODS"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387662"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/3510397"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2021"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2024.4"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0434--5"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902309"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00590-9"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391729.1391730"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/3--540--48318--7_4"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2019.21"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/11780991_13"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.18.7.401"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.80"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535926"},{"key":"e_1_2_1_36_1","first-page":"1","article-title":"Relational Algorithms for k-Means Clustering","volume":"198","author":"Moseley B.","year":"2021","unstructured":"B. Moseley, K. Pruhs, A. Samadian, and Y.Wang. Relational Algorithms for k-Means Clustering. In ICALP, volume 198, 97:1--97:21, 2021. doi: 10. 4230\/LIPIcs.ICALP.2021.97.","journal-title":"ICALP"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3003665.3003667"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2656335"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1626"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972863.16"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783888.2783894"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213035"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397250"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3584372.3588670"},{"key":"e_1_2_1_46_1","volume-title":"Any-k algorithms for enumerating ranked answers to conjunctive queries. CoRR, abs\/2205.05649","author":"Tziavelis N.","year":"2023","unstructured":"N. Tziavelis, W. Gatterbauer, and M. Riedewald. Any-k algorithms for enumerating ranked answers to conjunctive queries. CoRR, abs\/2205.05649, 2023. url: https:\/\/arxiv.org\/abs\/2205.05649."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476306"},{"key":"e_1_2_1_48_1","first-page":"2659","volume-title":"SIGMOD tutorials","author":"Tziavelis N.","year":"2020","unstructured":"N. Tziavelis, W. Gatterbauer, and M. Riedewald. Optimal join algorithms meet top-k. In SIGMOD tutorials, pages 2659--2665, 2020. doi: 10.1145\/ 3318464.3383132. url: https:\/\/northeasterndatalab. github.io\/topk-join-tutorial\/."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00299"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/42790"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802186"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517830"},{"key":"e_1_2_1_53_1","first-page":"489","volume-title":"WWW","author":"Yang X.","year":"2018","unstructured":"X. Yang, D. Ajwani, W. Gatterbauer, P. K. Nicholson, M. Riedewald, and A. Sala. Any-k: anytime top-k tree pattern retrieval in labeled graphs. In WWW, pages 489--498, 2018. doi: 10. 1145\/3178876.3186115."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3214708.3214711"},{"key":"e_1_2_1_55_1","first-page":"82","volume-title":"VLDB","author":"Yannakakis M.","year":"1981","unstructured":"M. Yannakakis. Algorithms for acyclic database schemes. In VLDB, pages 82--94, 1981. url: https:\/\/dl.acm.org\/doi\/10.5555\/1286831. 1286840."}],"container-title":["ACM SIGMOD Record"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3703922.3703924","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3703922.3703924","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:18:06Z","timestamp":1750295886000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3703922.3703924"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,8]]},"references-count":53,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,11,8]]}},"alternative-id":["10.1145\/3703922.3703924"],"URL":"https:\/\/doi.org\/10.1145\/3703922.3703924","relation":{},"ISSN":["0163-5808"],"issn-type":[{"value":"0163-5808","type":"print"}],"subject":[],"published":{"date-parts":[[2024,11,8]]},"assertion":[{"value":"2024-11-08","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}