{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T02:28:17Z","timestamp":1743042497787,"version":"3.40.3"},"publisher-location":"Cham","reference-count":37,"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_12","type":"book-chapter","created":{"date-parts":[[2019,9,24]],"date-time":"2019-09-24T05:07:22Z","timestamp":1569301642000},"page":"128-142","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Accurate and Fast Retrieval for Complex Non-metric Data via Neighborhood Graphs"],"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":"12_CR1","unstructured":"Arya, S., Mount, D.M.: Approximate nearest neighbor queries in fixed dimensions. In: SODA, vol. 93, pp. 271\u2013280 (1993)"},{"key":"12_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1007\/978-3-319-68474-1_3","volume-title":"Similarity Search and Applications","author":"M Aum\u00fcller","year":"2017","unstructured":"Aum\u00fcller, M., Bernhardsson, E., Faithfull, A.: ANN-benchmarks: a benchmarking tool for approximate nearest neighbor algorithms. In: Beecks, C., Borutta, F., Kr\u00f6ger, P., Seidl, T. (eds.) SISAP 2017. LNCS, vol. 10609, pp. 34\u201349. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-68474-1_3"},{"key":"12_CR3","unstructured":"Bellet, A., Habrard, A., Sebban, M.: A survey on metric learning for feature vectors and structured data. CoRR abs\/1306.6709 (2013)"},{"key":"12_CR4","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."},{"key":"12_CR5","unstructured":"Boytsov, L.: Efficient and accurate non-metric k-NN search with applications to text matching. Ph.D. thesis, Carnegie Mellon University (2017)"},{"key":"12_CR6","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"},{"key":"12_CR7","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)","DOI":"10.1145\/1390156.1390171"},{"issue":"3","key":"12_CR8","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."},{"key":"12_CR9","first-page":"1109","volume":"11","author":"G Chechik","year":"2010","unstructured":"Chechik, G., Sharma, V., Shalit, U., Bengio, S.: Large scale online learning of image similarity through ranking. J. Mach. Learn. Res. 11, 1109\u20131135 (2010)","journal-title":"J. Mach. Learn. Res."},{"key":"12_CR10","doi-asserted-by":"crossref","unstructured":"Davis, J.V., Kulis, B., Jain, P., Sra, S., Dhillon, I.S.: Information-theoretic metric learning. In: Proceedings of ICML 2007, pp. 209\u2013216. ACM (2007)","DOI":"10.1145\/1273496.1273523"},{"key":"12_CR11","doi-asserted-by":"crossref","unstructured":"Dong, W., Moses, C., Li, K.: Efficient k-nearest neighbor graph construction for generic similarity measures. In: Proceedings of WWW 2011, pp. 577\u2013586. ACM (2011)","DOI":"10.1145\/1963405.1963487"},{"key":"12_CR12","unstructured":"Hajebi, K., Abbasi-Yadkori, Y., Shahbazi, H., Zhang, H.: Fast approximate nearest-neighbor search with k-nearest neighbor graph. In: IJCAI\/AAAI 2011, pp. 1312\u20131317 (2011)"},{"key":"12_CR13","doi-asserted-by":"crossref","unstructured":"Harwood, B., Drummond, T.: FANNG: fast approximate nearest neighbour graphs. In: Proceedings of CVPR, pp. 5713\u20135722 (2016)","DOI":"10.1109\/CVPR.2016.616"},{"issue":"5","key":"12_CR14","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1109\/TPAMI.2003.1195989","volume":"25","author":"GR Hjaltason","year":"2003","unstructured":"Hjaltason, G.R., Samet, H.: Properties of embedding methods for similarity searching in metric spaces. IEEE Trans. Pattern Anal. Mach. Intell. 25(5), 530\u2013549 (2003)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"12_CR15","unstructured":"Houle, M.E., Sakuma, J.: Fast approximate similarity search in extremely high-dimensional data sets. In: ICDE 2005, pp. 619\u2013630 (2005)"},{"key":"12_CR16","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)"},{"issue":"6","key":"12_CR17","doi-asserted-by":"publisher","first-page":"583","DOI":"10.1109\/34.862197","volume":"22","author":"DW Jacobs","year":"2000","unstructured":"Jacobs, D.W., Weinshall, D., Gdalyahu, Y.: Classification with nonmetric distances: image retrieval and class representation. IEEE Trans. Pattern Anal. Mach. Intell. 22(6), 583\u2013600 (2000)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"1","key":"12_CR18","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. Statist. 22(1), 79\u201386 (1951)","journal-title":"Ann. Math. Statist."},{"key":"12_CR19","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":"12_CR20","unstructured":"Li, W., Zhang, Y., Sun, Y., Wang, W., Zhang, W., Lin, X.: Approximate nearest neighbor search on high dimensional data - experiments, analyses, and improvement (v1.0). CoRR abs\/1610.02455 (2016)"},{"key":"12_CR21","doi-asserted-by":"crossref","unstructured":"Liu, E.Y., Guo, Z., Zhang, X., Jojic, V., Wang, W.: Metric learning from relative comparisons by minimizing squared residual. In: IEEE ICDM 2012, pp. 978\u2013983. IEEE (2012)","DOI":"10.1109\/ICDM.2012.38"},{"key":"12_CR22","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/j.is.2013.10.006","volume":"45","author":"Y Malkov","year":"2014","unstructured":"Malkov, Y., Ponomarenko, A., Logvinov, A., Krylov, V.: Approximate nearest neighbor algorithm based on navigable small world graphs. Inf. Syst. 45, 61\u201368 (2014)","journal-title":"Inf. Syst."},{"key":"12_CR23","unstructured":"Malkov, Y.A., Yashunin, D.A.: Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. CoRR abs\/1603.09320 (2016)"},{"issue":"12","key":"12_CR24","first-page":"1618","volume":"8","author":"B Naidan","year":"2015","unstructured":"Naidan, B., Boytsov, L., Nyberg, E.: Permutation search methods are efficient, yet faster search is possible. PVLDB 8(12), 1618\u20131629 (2015)","journal-title":"PVLDB"},{"key":"12_CR25","unstructured":"Ponomarenko, A., Avrelin, N., Naidan, B., Boytsov, L.: Comparative analysis of data structures for approximate nearest neighbor search. In: DATA ANALYTICS 2014, The Third International Conference on Data Analytics, pp. 125\u2013130 (2014)"},{"key":"12_CR26","unstructured":"Qi, G., Tang, J., Zha, Z., Chua, T., Zhang, H.: An efficient sparse metric learning in high-dimensional space via l$${}_{\\text{1}}$$-penalized log-determinant regularization. In: ICML 2009, pp. 841\u2013848. ACM (2009)"},{"key":"12_CR27","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)"},{"issue":"5","key":"12_CR28","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1108\/00220410410560582","volume":"60","author":"S Robertson","year":"2004","unstructured":"Robertson, S.: Understanding inverse document frequency: on theoretical arguments for IDF. J. Doc. 60(5), 503\u2013520 (2004)","journal-title":"J. Doc."},{"key":"12_CR29","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":"12_CR30","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."},{"key":"12_CR31","unstructured":"Sutherland, D.J.: Scalable, flexible and active learning on distributions. Ph.D. thesis, Carnegie Mellon University (2016)"},{"key":"12_CR32","unstructured":"Tellez, E.S., Ruiz, G., Ch\u00e1vez, E., Graff, M.: Local search methods for fast near neighbor search. CoRR abs\/1705.10351 (2017). http:\/\/arxiv.org\/abs\/1705.10351"},{"issue":"4","key":"12_CR33","doi-asserted-by":"publisher","first-page":"261","DOI":"10.1016\/0031-3203(80)90066-7","volume":"12","author":"GT Toussaint","year":"1980","unstructured":"Toussaint, G.T.: The relative neighbourhood graph of a finite planar set. Pattern Recogn. 12(4), 261\u2013268 (1980)","journal-title":"Pattern Recogn."},{"key":"12_CR34","unstructured":"Wang, J., Shen, H.T., Song, J., Ji, J.: Hashing for similarity search: a survey. CoRR abs\/1408.2927 (2014)"},{"key":"12_CR35","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":"12_CR36","unstructured":"Weinberger, K.Q., Blitzer, J., Saul, L.K.: Distance metric learning for large margin nearest neighbor classification. In: NIPS 2005, pp. 1473\u20131480 (2005)"},{"key":"12_CR37","doi-asserted-by":"crossref","unstructured":"Xiong, C., Johnson, D.M., Xu, R., Corso, J.J.: Random forests for metric learning with implicit pairwise position dependence. In: KDD 2012, pp. 958\u2013966. ACM (2012)","DOI":"10.1145\/2339530.2339680"}],"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_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T10:45:15Z","timestamp":1710326715000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-32047-8_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030320461","9783030320478"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-32047-8_12","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)"}}]}}