{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:10:32Z","timestamp":1750306232731,"version":"3.41.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,4,14]],"date-time":"2017-04-14T00:00:00Z","timestamp":1492128000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Center for Scientific Computing at CNSI\/MRL","award":["NSF DMR-1121053 and CNS-0960316"],"award-info":[{"award-number":["NSF DMR-1121053 and CNS-0960316"]}]},{"name":"Kuwait University Scholarship"},{"DOI":"10.13039\/100000001","name":"NSF","doi-asserted-by":"publisher","award":["IIS-1118106 and 1528041"],"award-info":[{"award-number":["IIS-1118106 and 1528041"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2017,8,31]]},"abstract":"<jats:p>All pairs similarity search (APSS) is used in many web search and data mining applications. Previous work has used techniques such as comparison filtering, inverted indexing, and parallel accumulation of partial results. However, shuffling intermediate results can incur significant communication overhead as data scales up. This paper studies a scalable two-phase approach called Partition-based Similarity Search (PSS). The first phase is to partition the data and group vectors that are potentially similar. The second phase is to run a set of tasks where each task compares a partition of vectors with other candidate partitions. Due to data sparsity and the presence of memory hierarchy, accessing feature vectors during the partition comparison phase incurs significant overhead. This paper introduces a cache-conscious design for data layout and traversal to reduce access time through size-controlled data splitting and vector coalescing, and it provides an analysis to guide the choice of optimization parameters. The evaluation results show that for the tested datasets, the proposed approach can lead to an early elimination of unnecessary I\/O and data communication while sustaining parallel efficiency with one order of magnitude of performance improvement and it can also be integrated with LSH for approximated APSS.<\/jats:p>","DOI":"10.1145\/3014060","type":"journal-article","created":{"date-parts":[[2017,4,14]],"date-time":"2017-04-14T12:18:48Z","timestamp":1492172328000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Partitioned Similarity Search with Cache-Conscious Data Traversal"],"prefix":"10.1145","volume":"11","author":[{"given":"Xun","family":"Tang","sequence":"first","affiliation":[{"name":"Yelp Inc. and University of California at Santa Barbara, Santa Barbara, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maha","family":"Alabduljalil","sequence":"additional","affiliation":[{"name":"Kuwait University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xin","family":"Jin","sequence":"additional","affiliation":[{"name":"University of California at Santa Barbara, Santa Barbara, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tao","family":"Yang","sequence":"additional","affiliation":[{"name":"University of California at Santa Barbara, Santa Barbara, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,4,14]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2507157.2507189"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484028.2484077"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2433396.2433422"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816700"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/1182635.1164206"},{"volume-title":"Modern Information Retrieval","author":"Baeza-Yates Ricardo","key":"e_1_2_1_6_1","unstructured":"Ricardo Baeza-Yates and Berthier Ribeiro-Neto . 1999. Modern Information Retrieval . Addison Wesley . Ricardo Baeza-Yates and Berthier Ribeiro-Neto. 1999. Modern Information Retrieval. Addison Wesley."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2010.70"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242591"},{"volume-title":"Proceedings of the 25th International Conference on Very Large Data Bases. 54--65","author":"Boncz Peter","key":"e_1_2_1_9_1","unstructured":"Peter Boncz , Data Distilleries B. V. , Stefan Manegold , and Martin L. Kersten . 1999. Database architecture optimized for the new bottleneck : Memory access . In Proceedings of the 25th International Conference on Very Large Data Bases. 54--65 Peter Boncz, Data Distilleries B. V., Stefan Manegold, and Martin L. Kersten. 1999. Database architecture optimized for the new bottleneck : Memory access. In Proceedings of the 25th International Conference on Very Large Data Bases. 54--65"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1921591.1921593"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/506309.506311"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/77626.79170"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/567806.567810"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/645925.671516"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835449.1835520"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1341531.1341560"},{"key":"e_1_2_1_18_1","volume-title":"MD\u2019s bulldozer microarchitecture.","author":"Kanter David","year":"2010","unstructured":"David Kanter . 2010. MD\u2019s bulldozer microarchitecture. Retrieved from http:\/\/www.realworldtech.com\/ ( 2010 ). David Kanter. 2010. MD\u2019s bulldozer microarchitecture. Retrieved from http:\/\/www.realworldtech.com\/ (2010)."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 605--610","author":"Kolcz Aleksander","year":"2004","unstructured":"Aleksander Kolcz , Abdur Chowdhury , and Joshua Alspector . 2004 . Improved robustness of signature-based near-replica detection via lexicon randomization . In Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 605--610 . Aleksander Kolcz, Abdur Chowdhury, and Joshua Alspector. 2004. Improved robustness of signature-based near-replica detection via lexicon randomization. In Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 605--610."},{"key":"e_1_2_1_20_1","volume-title":"Performance analysis guide for intel core i7 processor and intel xeon 5500 processors. Intel","author":"Levinthal David","year":"2009","unstructured":"David Levinthal . 2009. Performance analysis guide for intel core i7 processor and intel xeon 5500 processors. Intel ( 2009 ). https:\/\/software.intel.com\/sites\/products\/collateral\/hpc\/vtune\/performance_analysis_guide.pdf. David Levinthal. 2009. Performance analysis guide for intel core i7 processor and intel xeon 5500 processors. Intel (2009). https:\/\/software.intel.com\/sites\/products\/collateral\/hpc\/vtune\/performance_analysis_guide.pdf."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1571941.1571970"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-155860869-6\/50025-1"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242606"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212353"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 8th Workshop on LargeScale Distributed Systems for Information Retrieval","author":"Francisci Morales Gianmarco De","year":"2010","unstructured":"Gianmarco De Francisci Morales , Claudio Lucchese , and Ranieri Baraglia . 2010 . Scaling out all pairs similarity search with MapReduce . In Proceedings of the 8th Workshop on LargeScale Distributed Systems for Information Retrieval (2010). Gianmarco De Francisci Morales, Claudio Lucchese, and Ranieri Baraglia. 2010. Scaling out all pairs similarity search with MapReduce. In Proceedings of the 8th Workshop on LargeScale Distributed Systems for Information Retrieval (2010)."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1135777.1135834"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140440"},{"volume-title":"Proceedings of the 20th International Conference on Very Large Data Bases (VLDB\u201994)","author":"Shatdal Ambuj","key":"e_1_2_1_28_1","unstructured":"Ambuj Shatdal , Chander Kant , and Jeffrey F. Naughton . 1994. Cache conscious algorithms for relational query processing . In Proceedings of the 20th International Conference on Very Large Data Bases (VLDB\u201994) . Morgan Kaufmann Publishers Inc, 510--521. Ambuj Shatdal, Chander Kant, and Jeffrey F. Naughton. 1994. Cache conscious algorithms for relational query processing. In Proceedings of the 20th International Conference on Very Large Data Bases (VLDB\u201994). Morgan Kaufmann Publishers Inc, 510--521."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479898337385"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/226931.226961"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556574"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2600428.2609624"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390334.1390431"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2009916.2010042"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807222"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/SC.2002.10025"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487625"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367516"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2187980.2187992"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3014060","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3014060","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3014060","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:23:16Z","timestamp":1750220596000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3014060"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,4,14]]},"references-count":39,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,8,31]]}},"alternative-id":["10.1145\/3014060"],"URL":"https:\/\/doi.org\/10.1145\/3014060","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2017,4,14]]},"assertion":[{"value":"2015-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-04-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}