{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T23:28:44Z","timestamp":1743031724779,"version":"3.40.3"},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030320461"},{"type":"electronic","value":"9783030320478"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-32047-8_7","type":"book-chapter","created":{"date-parts":[[2019,9,24]],"date-time":"2019-09-24T05:07:22Z","timestamp":1569301642000},"page":"72-85","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Pruning Algorithms for Low-Dimensional Non-metric k-NN Search: A Case Study"],"prefix":"10.1007","author":[{"given":"Leonid","family":"Boytsov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Eric","family":"Nyberg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,9,23]]},"reference":[{"key":"7_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/3-540-49257-7_15","volume-title":"Database Theory \u2014 ICDT\u201999","author":"KS Beyer","year":"1999","unstructured":"Beyer, K.S., Goldstein, J., Ramakrishnan, R., Shaft, U.: When is \u201cnearest neighbor\u201d meaningful? In: Beeri, C., Buneman, P. (eds.) ICDT 1999. LNCS, vol. 1540, pp. 217\u2013235. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/3-540-49257-7_15"},{"key":"7_CR2","first-page":"993","volume":"3","author":"DM Blei","year":"2003","unstructured":"Blei, D.M., Ng, A.Y., Jordan, M.I.: Latent dirichlet allocation. J. Mach. Learn. Res. 3, 993\u20131022 (2003)","journal-title":"J. Mach. Learn. Res."},{"unstructured":"Boytsov, L.: Efficient and accurate non-metric k-NN search with applications to text matching. Ph.D. thesis, Carnegie Mellon University (2017)","key":"7_CR3"},{"key":"7_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1007\/978-3-642-41062-8_28","volume-title":"Similarity Search and Applications","author":"L Boytsov","year":"2013","unstructured":"Boytsov, L., Naidan, B.: Engineering efficient and effective non-metric space library. In: Brisaboa, N., Pedreira, O., Zezula, P. (eds.) SISAP 2013. LNCS, vol. 8199, pp. 280\u2013293. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-41062-8_28"},{"unstructured":"Boytsov, L., Naidan, B.: Learning to prune in metric and non-metric spaces. In: Proceedings of NIPS 2013, pp. 1574\u20131582 (2013)","key":"7_CR5"},{"issue":"3","key":"7_CR6","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1145\/328939.328959","volume":"24","author":"T Bozkaya","year":"1999","unstructured":"Bozkaya, T., \u00d6zsoyoglu, Z.M.: Indexing large metric spaces for similarity search queries. ACM Trans. Database Syst. 24(3), 361\u2013404 (1999). https:\/\/doi.org\/10.1145\/328939.328959","journal-title":"ACM Trans. Database Syst."},{"issue":"3","key":"7_CR7","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1016\/0041-5553(67)90040-7","volume":"7","author":"L Bregman","year":"1967","unstructured":"Bregman, L.: The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR Comput. Math. Math. Phys. 7(3), 200\u2013217 (1967)","journal-title":"USSR Comput. Math. Math. Phys."},{"doi-asserted-by":"crossref","unstructured":"Cayton, L.: Fast nearest neighbor retrieval for bregman divergences. In: Proceedings of the 25th International Conference on Machine Learning, pp. 112\u2013119. ACM (2008)","key":"7_CR8","DOI":"10.1145\/1390156.1390171"},{"issue":"1","key":"7_CR9","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0020-0190(02)00344-7","volume":"85","author":"E Ch\u00e1vez","year":"2003","unstructured":"Ch\u00e1vez, E., Navarro, G.: Probabilistic proximity search: fighting the curse of dimensionality in metric spaces. Inf. Process. Lett. 85(1), 39\u201346 (2003)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"7_CR10","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1145\/502807.502808","volume":"33","author":"E Ch\u00e1vez","year":"2001","unstructured":"Ch\u00e1vez, E., Navarro, G., Baeza-Yates, R.A., Marroqu\u00edn, J.L.: Searching in metric spaces. ACM Comput. Surv. 33(3), 273\u2013321 (2001)","journal-title":"ACM Comput. Surv."},{"unstructured":"Fog, A.: Instruction tables: Lists of instruction latencies, throughputs and micro-operation breakdowns for intel, AMD and VIA CPUs (2011)","key":"7_CR11"},{"issue":"7","key":"7_CR12","doi-asserted-by":"publisher","first-page":"989","DOI":"10.1016\/j.is.2012.05.011","volume":"38","author":"ML Hetland","year":"2013","unstructured":"Hetland, M.L., Skopal, T., Loko\u010d, J., Beecks, C.: Ptolemaic access methods: challenging the reign of the metric space model. Inf. Syst. 38(7), 989\u20131006 (2013)","journal-title":"Inf. Syst."},{"unstructured":"Itakura, F., Saito, S.: Analysis synthesis telephony based on the maximum likelihood method. In: Proceedings of the 6th International Congress on Acoustics, pp. C17\u2013C20 (1968)","key":"7_CR13"},{"unstructured":"Knuth, D.E.: The Art of Computer Programming: Volume 3: Sorting and Searching. Atmospheric Chemistry & Physics (1973)","key":"7_CR14"},{"issue":"1","key":"7_CR15","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1214\/aoms\/1177729694","volume":"22","author":"S Kullback","year":"1951","unstructured":"Kullback, S., Leibler, R.A.: On information and sufficiency. Ann. Math. Stat. 22(1), 79\u201386 (1951)","journal-title":"Ann. Math. Stat."},{"key":"7_CR16","first-page":"361","volume":"5","author":"DD Lewis","year":"2004","unstructured":"Lewis, D.D., Yang, Y., Rose, T.G., Li, F.: RCV1: a new benchmark collection for text categorization research. J. Mach. Learn. Res. 5, 361\u2013397 (2004)","journal-title":"J. Mach. Learn. Res."},{"key":"7_CR17","series-title":"ICSA Book Series in Statistics","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-319-69416-0_1","volume-title":"New Advances in Statistics and Data Science","author":"M Markatou","year":"2017","unstructured":"Markatou, M., Chen, Y., Afendras, G., Lindsay, B.G.: Statistical distances and their role in robustness. In: Chen, D.-G., Jin, Z., Li, G., Li, Y., Liu, A., Zhao, Y. (eds.) New Advances in Statistics and Data Science. IBSS, pp. 3\u201326. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-69416-0_1"},{"issue":"1","key":"7_CR18","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1007\/s007780200060","volume":"11","author":"G Navarro","year":"2002","unstructured":"Navarro, G.: Searching in metric spaces by spatial approximation. VLDB J. 11(1), 28\u201346 (2002)","journal-title":"VLDB J."},{"unstructured":"Omohundro, S.M.: Five balltree construction algorithms (1989). iCSI Technical Report TR-89-063. http:\/\/www.icsi.berkeley.edu\/icsi\/publication_details?ID=000562","key":"7_CR19"},{"unstructured":"R\u00e9nyi, A.: On measures of entropy and information. In: Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, vol. 1, pp. 547\u2013561 (1961)","key":"7_CR20"},{"key":"7_CR21","volume-title":"Foundations of Multidimensional and Metric Data Structures","author":"H Samet","year":"2005","unstructured":"Samet, H.: Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann Publishers Inc., San Francisco (2005)"},{"issue":"4","key":"7_CR22","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1145\/1292609.1292619","volume":"32","author":"T Skopal","year":"2007","unstructured":"Skopal, T.: Unified framework for fast exact and approximate search in dissimilarity spaces. ACM Trans. Database Syst. 32(4), 29 (2007)","journal-title":"ACM Trans. Database Syst."},{"issue":"4","key":"7_CR23","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1145\/1978802.1978813","volume":"43","author":"T Skopal","year":"2011","unstructured":"Skopal, T., Bustos, B.: On nonmetric similarity search problems in complex domains. ACM Comput. Surv. 43(4), 34 (2011)","journal-title":"ACM Comput. Surv."},{"issue":"4","key":"7_CR24","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/0020-0190(91)90074-R","volume":"40","author":"JK Uhlmann","year":"1991","unstructured":"Uhlmann, J.K.: Satisfying general proximity\/similarity queries with metric trees. Inf. Process. Lett. 40(4), 175\u2013179 (1991)","journal-title":"Inf. Process. Lett."},{"unstructured":"Weber, R., Schek, H.J., Blott, S.: A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. In: VLDB, vol. 98, pp. 194\u2013205 (1998)","key":"7_CR25"},{"unstructured":"Yianilos, P.N.: Data structures and algorithms for nearest neighbor search in general metric spaces. In: Proceedings of ACM\/SIGACT-SIAM 1993, pp. 311\u2013321 (1993)","key":"7_CR26"},{"issue":"1","key":"7_CR27","first-page":"13","volume":"2","author":"Z Zhang","year":"2009","unstructured":"Zhang, Z., Ooi, B.C., Parthasarathy, S., Tung, A.K.H.: Similarity search on Bregman divergence: towards non-metric indexing. PVLDB 2(1), 13\u201324 (2009)","journal-title":"PVLDB"}],"container-title":["Lecture Notes in Computer Science","Similarity Search and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-32047-8_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T10:44:27Z","timestamp":1710326667000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-32047-8_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030320461","9783030320478"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-32047-8_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"23 September 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SISAP","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Similarity Search and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Newark, NJ","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 October 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 October 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sisap2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.sisap.org\/2019\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"42","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"12","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"18","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"29% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"2.88","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"1-92","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}