{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:56:11Z","timestamp":1775638571624,"version":"3.50.1"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"12","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2015,8]]},"abstract":"<jats:p>\n            We survey permutation-based methods for approximate\n            <jats:italic>k<\/jats:italic>\n            -nearest neighbor search. In these methods, every data point is represented by a ranked list of pivots sorted by the distance to this point. Such ranked lists are called\n            <jats:italic>permutations.<\/jats:italic>\n            The underpinning assumption is that, for both metric and non-metric spaces, the distance between permutations is a good proxy for the distance between original points. Thus, it should be possible to efficiently retrieve most true nearest neighbors by examining only a tiny subset of data points whose permutations are similar to the permutation of a query. We further test this assumption by carrying out an extensive experimental evaluation where permutation methods are pitted against state-of-the art benchmarks (the multi-probe LSH, the VP-tree, and proximity-graph based retrieval) on a variety of realistically large data set from the image and textual domain. The focus is on the high-accuracy retrieval methods for generic spaces. Additionally, we assume that both data and indices are stored in main memory. We find permutation methods to be reasonably efficient and describe a setup where these methods are most useful. To ease reproducibility, we make our software and data sets publicly available.\n          <\/jats:p>","DOI":"10.14778\/2824032.2824059","type":"journal-article","created":{"date-parts":[[2015,9,16]],"date-time":"2015-09-16T12:18:17Z","timestamp":1442405897000},"page":"1618-1629","source":"Crossref","is-referenced-by-count":27,"title":["Permutation search methods are efficient, yet faster search is possible"],"prefix":"10.14778","volume":"8","author":[{"given":"Bilegsaikhan","family":"Naidan","sequence":"first","affiliation":[{"name":"Norwegian University of Science and Technology, Trondheim, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leonid","family":"Boytsov","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eric","family":"Nyberg","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/2261250.2261255","volume-title":"Proceedings of the twenty-eighth annual symposium on Computational geometry","author":"Abdullah A.","year":"2012"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"G. Amato C. Gennaro and P. Savino. MI-file: using inverted files for scalable approximate similarity search. Multimedia tools and applications 71(3):1333--1362 2014. 10.1007\/s11042-012-1271-1   G. Amato C. Gennaro and P. Savino. MI-file: using inverted files for scalable approximate similarity search. Multimedia tools and applications 71(3):1333--1362 2014. 10.1007\/s11042-012-1271-1","DOI":"10.1007\/s11042-012-1271-1"},{"key":"e_1_2_1_3_1","first-page":"1","volume-title":"Proceedings of the 3rd international conference on Scalable information systems, InfoScale '08","author":"Amato G.","year":"2008"},{"key":"e_1_2_1_4_1","unstructured":"C. Beecks. Distance based similarity models for content based multimedia retrieval. PhD thesis 2013.  C. Beecks. Distance based similarity models for content based multimedia retrieval. PhD thesis 2013."},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1145\/502512.502546","volume-title":"Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining","author":"Bingham E.","year":"2001"},{"key":"e_1_2_1_6_1","unstructured":"D. M. Blei A. Y. Ng and M. I. Jordan. Latent dirichlet allocation. the Journal of machine Learning research 3: 993--1022 2003.   D. M. Blei A. Y. Ng and M. I. Jordan. Latent dirichlet allocation. the Journal of machine Learning research 3: 993--1022 2003."},{"key":"e_1_2_1_7_1","unstructured":"P. Bolettieri A. Esuli F. Falchi C. Lucchese R. Perego T. Piccioli and F. Rabitti. CoPhIR: a test collection for content-based image retrieval. CoRR abs\/0905.4627v2 2009.  P. Bolettieri A. Esuli F. Falchi C. Lucchese R. Perego T. Piccioli and F. Rabitti. CoPhIR: a test collection for content-based image retrieval. CoRR abs\/0905.4627v2 2009."},{"key":"e_1_2_1_8_1","first-page":"280","volume-title":"SISAP","author":"Boytsov L.","year":"2013"},{"key":"e_1_2_1_9_1","first-page":"1574","volume-title":"NIPS","author":"Boytsov L.","year":"2013"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1145\/1390156.1390171","volume-title":"ICML","author":"Cayton L.","year":"2008"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2015.02.001"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"E. Ch\u00e1vez G. Navarro R. Baeza-Yates and J. L. Marroqu\u00edn. Searching in metric spaces. ACM computing surveys (CSUR) 33(3):273--321 2001. 10.1145\/502807.502808   E. Ch\u00e1vez G. Navarro R. Baeza-Yates and J. L. Marroqu\u00edn. Searching in metric spaces. ACM computing surveys (CSUR) 33(3):273--321 2001. 10.1145\/502807.502808","DOI":"10.1145\/502807.502808"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.190700"},{"key":"e_1_2_1_14_1","first-page":"192","volume-title":"Lecture Notes-Monograph Series","author":"Diaconis P.","year":"1988"},{"key":"e_1_2_1_15_1","volume-title":"Princeton University","author":"Dong W.","year":"2011"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","first-page":"577","DOI":"10.1145\/1963405.1963487","volume-title":"Proceedings of the 20th international conference on World wide web","author":"Dong W.","year":"2011"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1145\/1458082.1458172","volume-title":"Proceedings of the 17th ACM conference on Information and knowledge management, CIKM '08","author":"Dong W.","year":"2008"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2003.813506"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of LSDS-IR, 2009","author":"Esuli A.","year":"2009"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1145\/872757.872795","volume-title":"Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, SIGMOD '03","author":"Fagin R.","year":"2003"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.232083"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1109\/SISAP.2009.12","volume-title":"Proceedings of the 2009 Second International Workshop on Similarity Search and Applications","author":"Figueroa K.","year":"2009"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","first-page":"466","DOI":"10.1145\/641007.641107","volume-title":"Proceedings of the tenth ACM international conference on Multimedia","author":"Goh K.-S.","year":"2002"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2007.70815"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.862197"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","first-page":"861","DOI":"10.1109\/ICASSP.2011.5946540","volume-title":"Speech and Signal Processing (ICASSP), 2011 IEEE International Conference on","author":"J\u00e9gou H.","year":"2011"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454211"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732939.2732947"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/j.is.2013.10.006","article-title":"Approximate nearest neighbor algorithm based on navigable small world graphs","volume":"45","author":"Malkov Y.","year":"2014","journal-title":"Information Systems"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/11764298_8"},{"key":"e_1_2_1_31_1","unstructured":"V. Pestov. Indexability concentration and {VC} theory. Journal of Discrete Algorithms 13(0): 2--18 2012. Best Papers from the 3rd International Conference on Similarity Search and Applications (SISAP 2010). 10.1016\/j.jda.2011.10.002   V. Pestov. Indexability concentration and {VC} theory. Journal of Discrete Algorithms 13(0): 2--18 2012. Best Papers from the 3rd International Conference on Similarity Search and Applications (SISAP 2010). 10.1016\/j.jda.2011.10.002"},{"key":"e_1_2_1_32_1","first-page":"45","volume-title":"Proceedings of the LREC 2010 Workshop on New Challenges for NLP Frameworks","author":"Rehurek R.","year":"2010"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"O. Russakovsky J. Deng H. Su J. Krause S. Satheesh S. Ma Z. Huang A. Karpathy A. Khosla M. Bernstein A. C. Berg and L. Fei-Fei. ImageNet Large Scale Visual Recognition Challenge 2014.  O. Russakovsky J. Deng H. Su J. Krause S. Satheesh S. Ma Z. Huang A. Karpathy A. Khosla M. Bernstein A. C. Berg and L. Fei-Fei. ImageNet Large Scale Visual Recognition Challenge 2014.","DOI":"10.1007\/s11263-015-0816-y"},{"key":"e_1_2_1_34_1","volume-title":"Morgan Kaufmann Publishers Inc.","author":"Samet H.","year":"2005"},{"key":"e_1_2_1_35_1","first-page":"1","volume-title":"ADMS@ VLDB","author":"Schlegel B.","year":"2011"},{"key":"e_1_2_1_36_1","first-page":"291","volume-title":"Pattern Recognition, 2002. Proceedings. 16th International Conference on","volume":"3","author":"Sebastian T. B.","year":"2002"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1292609.1292619"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10268-4_62"},{"issue":"7","key":"e_1_2_1_39_1","doi-asserted-by":"crossref","first-page":"1019","DOI":"10.1016\/j.is.2012.06.005","article-title":"Succinct nearest neighbor search","volume":"38","author":"Tellez E. S.","year":"2013","journal-title":"Information Systems"},{"key":"e_1_2_1_40_1","doi-asserted-by":"crossref","unstructured":"J. K. Uhlmann. Satisfying general proximity\/similarity queries with metric trees. Information processing letters 40(4):175--179 1991.  J. K. Uhlmann. Satisfying general proximity\/similarity queries with metric trees. Information processing letters 40(4):175--179 1991.","DOI":"10.1016\/0020-0190(91)90074-R"},{"key":"e_1_2_1_41_1","unstructured":"S. Van Dongen and A. J. Enright. Metric distances derived from cosine similarity and pearson and spearman correlations. arXiv preprint arXiv: 1208.3145 2012.  S. Van Dongen and A. J. Enright. Metric distances derived from cosine similarity and pearson and spearman correlations. arXiv preprint arXiv: 1208.3145 2012."},{"key":"e_1_2_1_42_1","first-page":"194","volume-title":"Proceedings of the 24th International Conference on Very Large Data Bases","author":"Weber R.","year":"1998"},{"key":"e_1_2_1_43_1","first-page":"311","volume-title":"SODA","volume":"93","author":"Yianilos P. N.","year":"1993"},{"key":"e_1_2_1_44_1","volume-title":"Inc.","author":"Zezula P.","year":"2005"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2824032.2824059","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:13:47Z","timestamp":1672222427000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2824032.2824059"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,8]]},"references-count":44,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2015,8]]}},"alternative-id":["10.14778\/2824032.2824059"],"URL":"https:\/\/doi.org\/10.14778\/2824032.2824059","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2015,8]]}}}