{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T16:09:59Z","timestamp":1762272599508},"reference-count":94,"publisher":"Association for Computing Machinery (ACM)","issue":"9","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2020,5]]},"abstract":"<jats:p>\n            We study ranked enumeration of join-query results according to very general orders defined by selective dioids. Our main contribution is a framework for ranked enumeration over a class of dynamic programming problems that generalizes seemingly different problems that had been studied in isolation. To this end, we extend classic algorithms that find the\n            <jats:italic>k<\/jats:italic>\n            -shortest paths in a weighted graph. For full conjunctive queries, including cyclic ones, our approach is optimal in terms of the time to return the top result and the delay between results. These optimality properties are derived for the widely used notion of data complexity, which treats query size as a constant. By performing a careful cost analysis, we are able to uncover a previously unknown tradeoff between two incomparable enumeration approaches: one has lower complexity when the number of returned results is small, the other when the number is very large. We theoretically and empirically demonstrate the superiority of our techniques over batch algorithms, which produce the full result and then sort it. Our technique is not only faster for returning the first few results, but on some inputs beats the batch algorithm even when all results are produced.\n          <\/jats:p>","DOI":"10.14778\/3397230.3397250","type":"journal-article","created":{"date-parts":[[2020,6,29]],"date-time":"2020-06-29T11:46:24Z","timestamp":1593431184000},"page":"1582-1597","source":"Crossref","is-referenced-by-count":20,"title":["Optimal algorithms for ranked enumeration of answers to full conjunctive queries"],"prefix":"10.14778","volume":"13","author":[{"given":"Nikolaos","family":"Tziavelis","sequence":"first","affiliation":[{"name":"Northeastern University"}]},{"given":"Deepak","family":"Ajwani","sequence":"additional","affiliation":[{"name":"University College Dublin, Dublin, Ireland"}]},{"given":"Wolfgang","family":"Gatterbauer","sequence":"additional","affiliation":[{"name":"Northeastern University"}]},{"given":"Mirek","family":"Riedewald","sequence":"additional","affiliation":[{"name":"Northeastern University"}]},{"given":"Xiaofeng","family":"Yang","sequence":"additional","affiliation":[{"name":"VMware"}]}],"member":"320","published-online":{"date-parts":[[2020,6,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319694"},{"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\/2902251.2902289"},{"key":"e_1_2_1_4_1","volume-title":"What do shannon-type inequalities, submodular width, and disjunctive datalog have to do with one another? CoRR, abs\/1612.02503","author":"Khamis M. Abo","year":"2016","unstructured":"M. Abo Khamis , H. Q. Ngo , and D. Suciu . What do shannon-type inequalities, submodular width, and disjunctive datalog have to do with one another? CoRR, abs\/1612.02503 , 2016 . URL : http:\/\/arxiv.org\/abs\/1612.02503. M. Abo Khamis, H. Q. Ngo, and D. Suciu. What do shannon-type inequalities, submodular width, and disjunctive datalog have to do with one another? CoRR, abs\/1612.02503, 2016. URL: http:\/\/arxiv.org\/abs\/1612.02503."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056105"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.141"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2011.03.010"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523189"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/110859440"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(93)90095-5"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74915-8_18"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556579"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350242"},{"key":"e_1_2_1_14_1","first-page":"475","volume-title":"VLDB","author":"Bast H.","year":"2006","unstructured":"H. Bast , D. Majumdar , R. Schenkel , M. Theobald , and G. Weikum . IO-top-k: index-access optimized top-k query processing . In VLDB , pages 475 -- 486 , 2006 . URL: https:\/\/dl.acm.org\/doi\/10.5555\/1182635.1164169. H. Bast, D. Majumdar, R. Schenkel, M. Theobald, and G. Weikum. IO-top-k: index-access optimized top-k query processing. In VLDB, pages 475--486, 2006. URL: https:\/\/dl.acm.org\/doi\/10.5555\/1182635.1164169."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1090\/qam\/102435"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9904-1954-09848-8"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0108044"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3034789"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2019.58"},{"key":"e_1_2_1_20_1","volume-title":"Nonserial dynamic programming","author":"Bertele U.","year":"1972","unstructured":"U. Bertele and F. Brioschi . Nonserial dynamic programming . Academic Press , 1972 . URL: https:\/\/dl.acm.org\/doi\/book\/10.5555\/578817. U. Bertele and F. Brioschi. Nonserial dynamic programming. Academic Press, 1972. URL: https:\/\/dl.acm.org\/doi\/book\/10.5555\/578817."},{"key":"e_1_2_1_21_1","volume-title":"Dynamic Programming and Optimal Control","author":"Bertsekas D. P.","year":"2005","unstructured":"D. P. Bertsekas . Dynamic Programming and Optimal Control , volume I . Athena Scientific, 3 rd edition, 2005 . URL : http:\/\/www.athenasc.com\/dpbook.html. D. P. Bertsekas. Dynamic Programming and Optimal Control, volume I. Athena Scientific, 3rd edition, 2005. URL: http:\/\/www.athenasc.com\/dpbook.html.","edition":"3"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.4230\/DagRep.9.5.89"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(98)00110-X"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/568518.568519"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319700"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735479.2735486"},{"key":"e_1_2_1_27_1","first-page":"397","volume-title":"VLDB","author":"Chaudhuri S.","year":"1999","unstructured":"S. Chaudhuri and L. Gravano . Evaluating top-k selection queries . In VLDB , volume 99 , pages 397 -- 410 , 1999 . URL : https:\/\/dl.acm.org\/doi\/10.5555\/645925.671359. S. Chaudhuri and L. Gravano. Evaluating top-k selection queries. In VLDB, volume 99, pages 397--410, 1999. URL: https:\/\/dl.acm.org\/doi\/10.5555\/645925.671359."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02592101"},{"key":"e_1_2_1_29_1","volume-title":"Introduction to Algorithms","author":"Cormen T. H.","year":"2009","unstructured":"T. H. Cormen , C. E. Leiserson , R. L. Rivest , and C. Stein . Introduction to Algorithms . The MIT Press , 3 rd edition, 2009 . URL: https:\/\/dl.acm.org\/doi\/book\/10.5555\/1614191. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to Algorithms. The MIT Press, 3rd edition, 2009. URL: https:\/\/dl.acm.org\/doi\/book\/10.5555\/1614191.","edition":"3"},{"key":"e_1_2_1_30_1","volume-title":"Algorithms","author":"Dasgupta S.","year":"2008","unstructured":"S. Dasgupta , C. H. Papadimitriou , and U. V. Vazirani . Algorithms . McGraw-Hill Higher Education , 2008 . URL: https:\/\/dl.acm.org\/doi\/book\/10.5555\/1177299. S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani. Algorithms. McGraw-Hill Higher Education, 2008. URL: https:\/\/dl.acm.org\/doi\/book\/10.5555\/1177299."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(99)00059-4"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196979"},{"key":"e_1_2_1_33_1","volume-title":"Ranked enumeration of conjunctive query results. CoRR, abs\/1902.02698","author":"Deep S.","year":"2019","unstructured":"S. Deep and P. Koutris . Ranked enumeration of conjunctive query results. CoRR, abs\/1902.02698 , 2019 . URL : http:\/\/arxiv.org\/abs\/1902.02698. S. Deep and P. Koutris. Ranked enumeration of conjunctive query results. CoRR, abs\/1902.02698, 2019. URL: http:\/\/arxiv.org\/abs\/1902.02698."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.17.3.395"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795290477"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00026-6"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559890"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02780332"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-015-9333-5"},{"key":"e_1_2_1_40_1","volume-title":"Optimizing and parallelizing ranked enumeration. PVLDB, 4(11)","author":"Golenberg K.","year":"2011","unstructured":"K. Golenberg , B. Kimelfeld , and Y. Sagiv . Optimizing and parallelizing ranked enumeration. PVLDB, 4(11) , 2011 . URL : http:\/\/www.vldb.org\/pvldb\/vol4\/p1028-golenberg.pdf. K. Golenberg, B. Kimelfeld, and Y. Sagiv. Optimizing and parallelizing ranked enumeration. PVLDB, 4(11), 2011. URL: http:\/\/www.vldb.org\/pvldb\/vol4\/p1028-golenberg.pdf."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-75450-5"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/588058.588089"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902309"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2017.11.005"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2220357.2220363"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1809"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/375551.375579"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1568318.1568320"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2016.11.004"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-23786-7\\_27"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1090272"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2636918"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/320998.321004"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-004-0128-2"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391729.1391730"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44867-5_14"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48318-7_4"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2018.16"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230120406"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/11780991_13"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1713"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/3159652.3159729"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2016.0033"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973198.7"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.18.7.401"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272743.1272749"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10288-002-0010-2"},{"issue":"1","key":"e_1_2_1_68_1","first-page":"47","article-title":"A new improvement for a K shortest paths algorithm","volume":"21","author":"Martins E. Q. V.","year":"2001","unstructured":"E. Q. V. Martins , M. M. B. Pascoal , and J. L. E. Santos . A new improvement for a K shortest paths algorithm . Investiga\u00e7\u00e3o Operacional , 21 ( 1 ): 47 -- 60 , 2001 . URL: http:\/\/apdio.pt\/documents\/10180\/15407\/IOvol21n1.pdf. E. Q. V. Martins, M. M. B. Pascoal, and J. L. E. Santos. A new improvement for a K shortest paths algorithm. Investiga\u00e7\u00e3o Operacional, 21(1):47--60, 2001. URL: http:\/\/apdio.pt\/documents\/10180\/15407\/IOvol21n1.pdf.","journal-title":"Investiga\u00e7\u00e3o Operacional"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535926"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.16.3.682"},{"key":"e_1_2_1_71_1","first-page":"281","volume-title":"VLDB","author":"Natsev A.","year":"2001","unstructured":"A. Natsev , Y.-C. Chang , J. R. Smith , C.-S. Li , and J. S. Vitter . Supporting incremental join queries on ranked inputs . In VLDB , pages 281 -- 290 , 2001 . URL: http:\/\/www.vldb.org\/conf\/2001\/P281.pdf. A. Natsev, Y.-C. Chang, J. R. Smith, C.-S. Li, and J. S. Vitter. Supporting incremental join queries on ranked inputs. In VLDB, pages 281--290, 2001. URL: http:\/\/www.vldb.org\/conf\/2001\/P281.pdf."},{"key":"e_1_2_1_72_1","volume-title":"ICDT","author":"Navarro G.","year":"2020","unstructured":"G. Navarro , J. L. Reutter , and J. Rojas-Ledesma . Optimal joins using compact data structures . In ICDT , 2020 . URL : https:\/\/arxiv.org\/abs\/1908.01812. G. Navarro, J. L. Reutter, and J. Rojas-Ledesma. Optimal joins using compact data structures. In ICDT, 2020. URL: https:\/\/arxiv.org\/abs\/1908.01812."},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/3180143"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/2590989.2590991"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/3003665.3003667"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274607"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/2656335"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511662508.004"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90023-4"},{"key":"e_1_2_1_80_1","volume-title":"26th Italian Symposium on Advanced Database Systems","author":"Scarcello F.","year":"2018","unstructured":"F. Scarcello . From hypertree width to submodular width and data-dependent structural decompositions . In 26th Italian Symposium on Advanced Database Systems , 2018 . URL: http:\/\/ceur-ws.org\/Vol-2161\/paper24.pdf. F. Scarcello. From hypertree width to submodular width and data-dependent structural decompositions. In 26th Italian Symposium on Advanced Database Systems, 2018. URL: http:\/\/ceur-ws.org\/Vol-2161\/paper24.pdf."},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-05411-3_3"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-35514-2_32"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783888.2783894"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2017.20"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-007-0072-z"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2003.1260799"},{"key":"e_1_2_1_87_1","volume-title":"Optimal algorithms for ranked enumeration of answers to full conjunctive queries. CoRR, abs\/1911.05582","author":"Tziavelis N.","year":"2019","unstructured":"N. Tziavelis , D. Ajwani , W. Gatterbauer , M. Riedewald , and X. Yang . Optimal algorithms for ranked enumeration of answers to full conjunctive queries. CoRR, abs\/1911.05582 , 2019 . URL : https:\/\/arxiv.org\/abs\/1911.05582. N. Tziavelis, D. Ajwani, W. Gatterbauer, M. Riedewald, and X. Yang. Optimal algorithms for ranked enumeration of answers to full conjunctive queries. CoRR, abs\/1911.05582, 2019. URL: https:\/\/arxiv.org\/abs\/1911.05582."},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802186"},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.5441\/002\/icdt.2014.13"},{"key":"e_1_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178876.3186115"},{"key":"e_1_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.1145\/3214708.3214711"},{"key":"e_1_2_1_92_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. M. Yannakakis. Algorithms for acyclic database schemes. In VLDB, pages 82--94, 1981. URL: https:\/\/dl.acm.org\/doi\/10.5555\/1286831.1286840."},{"key":"e_1_2_1_93_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.17.11.712"},{"key":"e_1_2_1_94_1","volume-title":"Social computing data repository at ASU","author":"Zafarani R.","year":"2009","unstructured":"R. Zafarani and H. Liu . Social computing data repository at ASU , 2009 . URL : http:\/\/socialcomputing.asu.edu. (accessed on 09\/2019). R. Zafarani and H. Liu. Social computing data repository at ASU, 2009. URL: http:\/\/socialcomputing.asu.edu. (accessed on 09\/2019)."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3397230.3397250","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:25:13Z","timestamp":1672223113000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3397230.3397250"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5]]},"references-count":94,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2020,5]]}},"alternative-id":["10.14778\/3397230.3397250"],"URL":"https:\/\/doi.org\/10.14778\/3397230.3397250","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2020,5]]}}}