{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T01:03:24Z","timestamp":1772845404534,"version":"3.50.1"},"reference-count":87,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2021,7]]},"abstract":"<jats:p>\n            We study theta-joins in general and join predicates with conjunctions and disjunctions of inequalities in particular, focusing on\n            <jats:italic>ranked enumeration<\/jats:italic>\n            where the answers are returned incrementally in an order dictated by a given ranking function. Our approach achieves strong time and space complexity properties: with\n            <jats:italic>n<\/jats:italic>\n            denoting the number of tuples in the database, we guarantee for acyclic full join queries with inequality conditions that for\n            <jats:italic>every<\/jats:italic>\n            value of\n            <jats:italic>k<\/jats:italic>\n            , the\n            <jats:italic>k<\/jats:italic>\n            top-ranked answers are returned in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            polylog\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>k<\/jats:italic>\n            log\n            <jats:italic>k<\/jats:italic>\n            ) time. This is within a polylogarithmic factor of\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>k<\/jats:italic>\n            log\n            <jats:italic>k<\/jats:italic>\n            ), i.e., the best known complexity for equi-joins, and even of\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            +\n            <jats:italic>k<\/jats:italic>\n            ), i.e., the time it takes to look at the input and return\n            <jats:italic>k<\/jats:italic>\n            answers in any order. Our guarantees extend to join queries with selections and many types of projections (namely those called \"free-connex\" queries and those that use bag semantics). Remarkably, they hold even when the number of join results is\n            <jats:italic>\n              n\n              <jats:sup>\u2113<\/jats:sup>\n            <\/jats:italic>\n            for a join of\n            <jats:italic>\u2113<\/jats:italic>\n            relations. The key ingredient is a novel\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            polylog\n            <jats:italic>n<\/jats:italic>\n            )-size\n            <jats:italic>factorized representation of the query output<\/jats:italic>\n            , which is constructed on-the-fly for a given query and database. In addition to providing the first nontrivial theoretical guarantees beyond equi-joins, we show in an experimental study that our ranked-enumeration approach is also memory-efficient and fast in practice, beating the running time of state-of-the-art database systems by orders of magnitude.\n          <\/jats:p>","DOI":"10.14778\/3476249.3476306","type":"journal-article","created":{"date-parts":[[2021,10,27]],"date-time":"2021-10-27T16:46:23Z","timestamp":1635353183000},"page":"2599-2612","source":"Crossref","is-referenced-by-count":13,"title":["Beyond equi-joins"],"prefix":"10.14778","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-8342-2177","authenticated-orcid":false,"given":"Nikolaos","family":"Tziavelis","sequence":"first","affiliation":[{"name":"Northeastern University"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9614-0504","authenticated-orcid":false,"given":"Wolfgang","family":"Gatterbauer","sequence":"additional","affiliation":[{"name":"Northeastern University"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6102-7472","authenticated-orcid":false,"given":"Mirek","family":"Riedewald","sequence":"additional","affiliation":[{"name":"Northeastern University"}]}],"member":"320","published-online":{"date-parts":[[2021,10,27]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.15468\/dl.d6u6tj"},{"key":"e_1_2_1_2_1","unstructured":"2021. TPC Benchmark H (Decision Support) Revision 3.0.0. http:\/\/tpc.org\/tpch\/  2021. TPC Benchmark H (Decision Support) Revision 3.0.0. http:\/\/tpc.org\/tpch\/"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319694"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196960"},{"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.1201\/9781315119601"},{"key":"e_1_2_1_7_1","volume-title":"Dynamic Enumeration of Similarity Joins. CoRR","author":"Agarwal Pankaj K","year":"2021"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"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.1007\/978-3-540-74915-8_18"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556579"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350242"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385634.3385636"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3034789"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2019.58"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2983573"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9734-3"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3294052.3319700"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-019-09937-9"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3452021.3458331"},{"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\/2735479.2735486"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335433"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217026"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14236\/ewic\/DBPL1995.6"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/1614191"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1182635.1164167"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-77974-2"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2021.5"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/645917.672320"},{"key":"e_1_2_1_32_1","unstructured":"Mengsu Ding Shimin Chen Nantia Makrynioti and Stefan Manegold. 2021. Progressive Join Algorithms Considering User Preference. In CIDR. https:\/\/ir.cwi.nl\/pub\/30501\/30501.pdf  Mengsu Ding Shimin Chen Nantia Makrynioti and Stefan Manegold. 2021. Progressive Join Algorithms Considering User Preference. In CIDR. https:\/\/ir.cwi.nl\/pub\/30501\/30501.pdf"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3389130"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007645"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00026-6"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559890"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-75450-5"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902309"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/5.1.10"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375690"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3371316.3371325"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00590-9"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-004-0128-2"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391729.1391730"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2019.21"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/2967101"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-016-0441-6"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-016-9684-2"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2723713"},{"key":"e_1_2_1_51_1","doi-asserted-by":"crossref","unstructured":"Srijan Kumar William L Hamilton Jure Leskovec and Dan Jurafsky. 2018. Community interaction and conflict on the web. https:\/\/snap.stanford.edu\/data\/soc-RedditHyperlinks.html. In WWW. 933--943.  Srijan Kumar William L Hamilton Jure Leskovec and Dan Jurafsky. 2018. Community interaction and conflict on the web. https:\/\/snap.stanford.edu\/data\/soc-RedditHyperlinks.html. In WWW. 933--943.","DOI":"10.1145\/3178876.3186141"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389750"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/MILCOM.2018.8599748"},{"key":"e_1_2_1_54_1","volume-title":"Towards a Dichotomy for Minimally Factorizing the Provenance of Self-Join Free Conjunctive Queries. CoRR abs\/2105.14307","author":"Makhija Neha","year":"2021"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272743.1272749"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535926"},{"key":"e_1_2_1_57_1","unstructured":"Apostol Natsev Yuan-Chi Chang John R Smith Chung-Sheng Li and Jeffrey Scott Vitter. 2001. Supporting incremental join queries on ranked inputs. In VLDB. 281--290. http:\/\/www.vldb.org\/conf\/2001\/P281.pdf  Apostol Natsev Yuan-Chi Chang John R Smith Chung-Sheng Li and Jeffrey Scott Vitter. 2001. Supporting incremental join queries on ranked inputs. In VLDB. 281--290. http:\/\/www.vldb.org\/conf\/2001\/P281.pdf"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICDT.2020.21"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196990"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2594538.2594547"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3180143"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/2590989.2590991"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87993-0_26"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559887"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.14778\/3007263.3007312"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/3003665.3003667"},{"key":"e_1_2_1_67_1","unstructured":"Dan Olteanu and Jakub Z\u00e1vodn\u00fd. 2011. On factorisation of provenance polynomials. In TaPP. https:\/\/www.usenix.org\/conference\/tapp11\/factorisation-provenance-polynomials  Dan Olteanu and Jakub Z\u00e1vodn\u00fd. 2011. On factorisation of provenance polynomials. In TaPP. https:\/\/www.usenix.org\/conference\/tapp11\/factorisation-provenance-polynomials"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/2274576.2274607"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/2656335"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380577"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1999.1626"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/3377330.3377332"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2882939"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783888.2783894"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213035"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2003.1260799"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397250"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3383132"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476306"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802186"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.5441\/002\/icdt.2014.13"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0012"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1848"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732939.2732945"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920951"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178876.3186115"},{"key":"e_1_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1145\/3214708.3214711"},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.5555\/1286831.1286840"},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1109\/CMPSAC.1979.762509"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3476249.3476306","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:13:10Z","timestamp":1672222390000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3476249.3476306"}},"subtitle":["ranking, enumeration and factorization"],"short-title":[],"issued":{"date-parts":[[2021,7]]},"references-count":87,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["10.14778\/3476249.3476306"],"URL":"https:\/\/doi.org\/10.14778\/3476249.3476306","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2021,7]]}}}