{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:26:38Z","timestamp":1750307198093,"version":"3.41.0"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2012,2,1]],"date-time":"2012-02-01T00:00:00Z","timestamp":1328054400000},"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":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2012,2]]},"abstract":"<jats:p>\n            We introduce the proximity rank join problem, where we are given a set of relations whose tuples are equipped with a score and a real-valued feature vector. Given a target feature vector, the goal is to return the\n            <jats:italic>K<\/jats:italic>\n            combinations of tuples with high scores that are as close as possible to the target and to each other, according to some notion of distance or dissimilarity. The setting closely resembles that of traditional rank join, but the geometry of the vector space plays a distinctive role in the computation of the overall score of a combination. Also, the input relations typically return their results either by distance from the target or by score. Because of these aspects, it turns out that traditional rank join algorithms, such as the well-known\n            <jats:italic>HRJN<\/jats:italic>\n            , have shortcomings in solving the proximity rank join problem, as they may read more input than needed. To overcome this weakness, we define a tight bound (used as a stopping criterion) that guarantees instance optimality, that is, an I\/O cost is achieved that is always within a constant factor of optimal. The tight bound can also be used to drive an adaptive pulling strategy, deciding at each step which relation to access next. For practically relevant classes of problems, we show how to compute the tight bound efficiently. An extensive experimental study validates our results and demonstrates significant gains over existing solutions.\n          <\/jats:p>","DOI":"10.1145\/2109196.2109198","type":"journal-article","created":{"date-parts":[[2012,3,6]],"date-time":"2012-03-06T13:18:22Z","timestamp":1331039902000},"page":"1-46","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Proximity measures for rank join"],"prefix":"10.1145","volume":"37","author":[{"given":"Davide","family":"Martinenghi","sequence":"first","affiliation":[{"name":"Politecnico di Milano, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marco","family":"Tagliasacchi","sequence":"additional","affiliation":[{"name":"Politecnico di Milano, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,3,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.141"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.14778\/1453856.1453895"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1101\/gr.180801"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.datak.2003.08.007"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00026-6"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559890"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276326"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-004-0128-2"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391729.1391730"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bti538"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Mamoulis N. Theodoridis Y. and Papadias D. 2005. Spatial joins: Algorithms cost models and optimization techniques. In Spatial Databases 155--184.  Mamoulis N. Theodoridis Y. and Papadias D. 2005. Spatial joins: Algorithms cost models and optimization techniques. In Spatial Databases 155--184.","DOI":"10.4018\/978-1-59140-387-6.ch007"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.14778\/1920841.1920889"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxl002"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376916.1376924"},{"volume-title":"Proceedings of the International Conference on Very Large Database (VLDB). 902--913","author":"Schnaitter K.","key":"e_1_2_1_15_1"},{"volume-title":"Proceedings of the International Conference on Data Engineering (ICDE).","author":"Silva Y. N.","key":"e_1_2_1_16_1"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.61"},{"key":"e_1_2_1_18_1","unstructured":"YQL console. 2012. http:\/\/developer.yahoo.com\/yql\/console\/.  YQL console. 2012. http:\/\/developer.yahoo.com\/yql\/console\/."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2109196.2109198","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2109196.2109198","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T10:06:09Z","timestamp":1750241169000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2109196.2109198"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,2]]},"references-count":18,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,2]]}},"alternative-id":["10.1145\/2109196.2109198"],"URL":"https:\/\/doi.org\/10.1145\/2109196.2109198","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2012,2]]},"assertion":[{"value":"2011-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-03-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}