{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,23]],"date-time":"2026-10-23T07:52:37Z","timestamp":1792741957906,"version":"4.5.0"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T00:00:00Z","timestamp":1710201600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006374","name":"Agencia Nacional de Investigaci\u00f3n y Desarrollo","doi-asserted-by":"publisher","award":["CN17_002"],"award-info":[{"award-number":["CN17_002"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006374","name":"Agencia Nacional de Investigaci\u00f3n y Desarrollo","doi-asserted-by":"publisher","award":["Fondecyt 122192"],"award-info":[{"award-number":["Fondecyt 122192"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006374","name":"Agencia Nacional de Investigaci\u00f3n y Desarrollo","doi-asserted-by":"publisher","award":["fondecyt 1-230755"],"award-info":[{"award-number":["fondecyt 1-230755"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006374","name":"Agencia Nacional de Investigaci\u00f3n y Desarrollo","doi-asserted-by":"publisher","award":["fondecyt 1221799"],"award-info":[{"award-number":["fondecyt 1221799"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006374","name":"Ministerio de Ciencia e Innovaci\u00f3n","doi-asserted-by":"publisher","award":["MCIN\/AEI\/10.13039\/501100011033 TED2021-129245B-C21"],"award-info":[{"award-number":["MCIN\/AEI\/10.13039\/501100011033 TED2021-129245B-C21"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006374","name":"Ministerio de Ciencia e Innovaci\u00f3n","doi-asserted-by":"publisher","award":["EI\/10.13039\/5011000-11033: grant PID2020-114635RB-I00"],"award-info":[{"award-number":["EI\/10.13039\/5011000-11033: grant PID2020-114635RB-I00"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006374","name":"Ministerio de Ciencia e Innovaci\u00f3n","doi-asserted-by":"publisher","award":["A-EI\/10.13039\/501100011033 PID2022-141027NB- C21"],"award-info":[{"award-number":["A-EI\/10.13039\/501100011033 PID2022-141027NB- C21"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,3,12]]},"abstract":"<jats:p>We extend the concept of worst-case optimal equijoins in graph databases to the case where some nodes are required to be within the k-nearest neighbors (kNN) of others under some similarity function. We model the problem by superimposing the database graph with the kNN graph and show that a variant of Leapfrog TrieJoin (LTJ) implemented over a compact data structure called the Ring can be seamlessly extended to integrate similarity clauses with the equijoins in the LTJ query process, retaining worst-case optimality in many relevant cases. Our experiments on a benchmark that combines Wikidata and IMGpedia show that our enhanced LTJ algorithm outperforms by a considerable margin a baseline that first applies classic LTJ and then completes the query by applying the similarity predicates. The difference is more pronounced on queries where the similarity clauses are more densely connected to the query, becoming of an order of magnitude in some cases.<\/jats:p>","DOI":"10.1145\/3639294","type":"journal-article","created":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T18:51:32Z","timestamp":1711479092000},"page":"1-26","source":"Crossref","is-referenced-by-count":4,"title":["Worst-Case-Optimal Similarity Joins on Graph Databases"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2509-8097","authenticated-orcid":false,"given":"Diego","family":"Arroyuelo","sequence":"first","affiliation":[{"name":"DCC, Escuela de Ingenier\u00eda, Pontificia Universidad Cat\u00f3lica &amp; IMFD, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3955-361X","authenticated-orcid":false,"given":"Benjamin","family":"Bustos","sequence":"additional","affiliation":[{"name":"DCC, University of Chile &amp; IMFD, Santiago, Chile, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1216-2176","authenticated-orcid":false,"given":"Adri\u00e1n","family":"G\u00f3mez-Brand\u00f3n","sequence":"additional","affiliation":[{"name":"Universidade da Coru\u00f1a &amp; CITIC, La Coru\u00f1a, Spain"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9482-1982","authenticated-orcid":false,"given":"Aidan","family":"Hogan","sequence":"additional","affiliation":[{"name":"DCC, University of Chile &amp; IMFD, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2286-741X","authenticated-orcid":false,"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[{"name":"DCC, University of Chile &amp; IMFD, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2186-0312","authenticated-orcid":false,"given":"Juan","family":"Reutter","sequence":"additional","affiliation":[{"name":"DCC, Escuela de Ingenier\u00eda, Pontificia Universidad Cat\u00f3lica &amp; Instituto de Ingenier\u00eda Matem\u00e1tica y Computaci\u00f3nal, Pontificia Universidad Cat\u00f3lica, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,3,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902289"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056105"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/3199517.3199520"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3104031"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1322432.1322433"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457256"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514231"},{"key":"e_1_2_1_8_1","volume-title":"LinkedIn Engineering Blog, 2023","author":"Arsintescu B.","year":"2023","unstructured":"B. Arsintescu. How LIquid connects everything so our members can do anything. LinkedIn Engineering Blog, 2023. https:\/\/engineering.linkedin.com\/blog\/2023\/how-liquid-connects-everything-so-our-members-can-do-anything."},{"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.3233\/SW-2012-0065"},{"key":"e_1_2_1_11_1","volume-title":"Proc. ISWC Posters & Demonstrations","author":"Bebee B. R.","year":"2018","unstructured":"B. R. Bebee, D. Choi, A. Gupta, A. Gutmans, A. Khandelwal, Y. Kiran, S. Mallidi, B. McGaughy, M. Personick, K. Rajan, S. Rondelli, A. Ryazanov, M. Schmidt, K. Sengupta, B. B. Thompson, D. Vaidya, and S. Wang. Amazon Neptune: Graph data management in the Cloud. In Proc. ISWC Posters & Demonstrations, 2018."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313472"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.9"},{"key":"e_1_2_1_14_1","volume-title":"University of Waterloo","author":"Clark D.","year":"1996","unstructured":"D. Clark. Compact Pat Trees. PhD thesis, University of Waterloo, 1996."},{"key":"e_1_2_1_15_1","first-page":"169","volume-title":"Proc. 4th International Conference on Knowledge Discovery and Data Mining (KDD)","author":"Cohen W. W.","year":"1998","unstructured":"W. W. Cohen and H. Hirsh. Joins that generalize: Text classification using WHIRL. In Proc. 4th International Conference on Knowledge Discovery and Data Mining (KDD), pages 169--173, 1998."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.24432\/C5CC9H"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2948992.2949016"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0074113"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3526057"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0925-7721(95)00009-7"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963487"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-68204-4_8"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-62419-4_12"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407797"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3398682.3399162"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-67162-8_26"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07959-2_28"},{"key":"e_1_2_1_28_1","first-page":"841","volume-title":"Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Grossi R.","year":"2003","unstructured":"R. Grossi, A. Gupta, and J. Vitter. High-order entropy-compressed text indexes. In Proc. 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 841--850, 2003."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733004.2733010"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1080\/00031305.1998.10480559"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276326"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-30284-8_53"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-30793-6_15"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00247"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-76298-0_22"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.24432\/C50S4B"},{"key":"e_1_2_1_37_1","volume-title":"Multiclass classification of dry beans using computer vision and machine learning techniques. Computers and Electronics in Agriculture, 174:article 105507","author":"Koklu M.","year":"2020","unstructured":"M. Koklu and I. A. Ozkan. Multiclass classification of dry beans using computer vision and machine learning techniques. Computers and Electronics in Agriculture, 174:article 105507, 2020."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-00668-6_23"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3446980"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/3554821.3554894"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-62034-6_35"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2013.07.004"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196990"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3180143"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764947.2764948"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/11764298_8"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.3233\/SW-170285"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447873"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/1978802.1978813"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.14778\/3397230.3397250"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476306"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187718"},{"key":"e_1_2_1_53_1","first-page":"96","volume-title":"Proc. International Conference on Database Theory (ICDT)","author":"Veldhuizen T. L.","year":"2014","unstructured":"T. L. Veldhuizen. Triejoin: A simple, worst-case optimal join algorithm. In Proc. International Conference on Database Theory (ICDT), pages 96--106, 2014."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629489"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2012.6247790"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.1996.492202"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/0-387-29151-2"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/GEOINFORMATICS.2010.5567605"},{"key":"e_1_2_1_59_1","first-page":"660","volume-title":"Machine Learning and Knowledge Discovery in Databases","author":"Zhang Y.-M.","year":"2013","unstructured":"Y.-M. Zhang, K. Huang, G. Geng, and C.-L. Liu. Fast knn graph construction with locality sensitive hashing. In Machine Learning and Knowledge Discovery in Databases, pages 660--674. Springer, 2013."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639294","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3639294","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T15:17:35Z","timestamp":1755789455000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639294"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,12]]},"references-count":59,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,12]]}},"alternative-id":["10.1145\/3639294"],"URL":"https:\/\/doi.org\/10.1145\/3639294","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,12]]}}}