{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,16]],"date-time":"2025-10-16T10:10:13Z","timestamp":1760609413341,"version":"3.41.2"},"reference-count":38,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2021,11,29]],"date-time":"2021-11-29T00:00:00Z","timestamp":1638144000000},"content-version":"vor","delay-in-days":332,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Analytical Center for the Government of the Russian Federation","award":["70-2021-00143","IGK000000D730321P5Q0002"],"award-info":[{"award-number":["70-2021-00143","IGK000000D730321P5Q0002"]}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Complexity"],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>K\u2010nearest neighbours (kNN) is a very popular instance\u2010based classifier due to its simplicity and good empirical performance. However, large\u2010scale datasets are a big problem for building fast and compact neighbourhood\u2010based classifiers. This work presents the design and implementation of a classification algorithm with index data structures, which would allow us to build fast and scalable solutions for large multidimensional datasets. We propose a novel approach that uses navigable small\u2010world (NSW) proximity graph representation of large\u2010scale datasets. Our approach shows 2\u20134 times classification speedup for both average and 99th percentile time with asymptotically close classification accuracy compared to the 1\u2010NN method. We observe two orders of magnitude better classification time in cases when method uses swap memory. We show that NSW graph used in our method outperforms other proximity graphs in classification accuracy. Our results suggest that the algorithm can be used in large\u2010scale applications for fast and robust classification, especially when the search index is already constructed for the data.<\/jats:p>","DOI":"10.1155\/2021\/2011738","type":"journal-article","created":{"date-parts":[[2021,11,29]],"date-time":"2021-11-29T20:50:10Z","timestamp":1638219010000},"update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Using Proximity Graph Cut for Fast and Robust Instance\u2010Based Classification in Large Datasets"],"prefix":"10.1155","volume":"2021","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5404-2773","authenticated-orcid":false,"given":"Stanislav","family":"Protasov","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2220-8518","authenticated-orcid":false,"given":"Adil Mehmood","family":"Khan","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2021,11,29]]},"reference":[{"key":"e_1_2_11_1_2","unstructured":"LavalleS. M. Rapidly-exploring random trees: A new tool for path planning 1998 Iowa State University Ames Iowa Technical Report."},{"key":"e_1_2_11_2_2","doi-asserted-by":"crossref","unstructured":"Massagu\u00e9 RespallV. DevittD. andFedorenkoR. Unmanned aerial vehicle path planning for exploration mapping 2020 Innopolis University Innopolis Russia Technical Reporthttps:\/\/doi.org\/10.13140\/RG.2.2.11126.75841.","DOI":"10.1109\/NIR50484.2020.9290232"},{"key":"e_1_2_11_3_2","unstructured":"Carreira-Perpi\u00f1\u00e1nM. A.andZemelR. S. Proximity graphs for clustering and manifold learning Proceedings of the 17th International Conference on Neural Information Processing Systems NIPS\u201904 December 2004 Cambridge MA USA MIT Press 225\u2013232 https:\/\/doi.org\/10.5555\/2976040.2976069."},{"key":"e_1_2_11_4_2","first-page":"549","volume-title":"Instance-Based Learning","author":"Keogh E.","year":"2010"},{"key":"e_1_2_11_5_2","first-page":"4916","volume-title":"Advances in Neural Information Processing Systems","author":"Anava O.","year":"2016"},{"key":"e_1_2_11_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/3319532"},{"key":"e_1_2_11_7_2","first-page":"207","article-title":"Distance metric learning for large margin nearest neighbor classification","volume":"10","author":"Weinberger K. Q.","year":"2009","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_11_8_2","article-title":"Principal warps: thin-plate spline and decomposition of deformations","volume":"11","author":"Bookstein Fred L.","year":"1992","journal-title":"Transictions on pattern analysis and machine intelligence"},{"key":"e_1_2_11_9_2","unstructured":"SitawarinC.andW\u00e1gnerD. Defending against adversarial examples with k-nearest neighbor 2019 https:\/\/arxiv.org\/abs\/1906.09525."},{"key":"e_1_2_11_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/bf00337288"},{"key":"e_1_2_11_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97610-0_6"},{"volume-title":"Radial Basis Functions Multivariable Functional Interpolation and Adaptive Networks. No. RSRE-MEMO-4148","year":"1988","author":"Lowe D.","key":"e_1_2_11_12_2"},{"key":"e_1_2_11_13_2","doi-asserted-by":"publisher","DOI":"10.14569\/IJACSA.2017.080603"},{"key":"e_1_2_11_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/s41133-020-00032-0"},{"key":"e_1_2_11_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2013.10.006"},{"key":"e_1_2_11_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2018.2889473"},{"key":"e_1_2_11_17_2","unstructured":"DevlinJ. ChangM. LeeK. andToutanovaK. BERT: pre-training of deep bidirectional transformers for language understanding 2018 http:\/\/arxiv.org\/abs\/1810.04805."},{"key":"e_1_2_11_18_2","doi-asserted-by":"crossref","unstructured":"HuangP.-S. HeX. GaoJ. DengL. AceroA. andHeckL. Learning deep structured semantic models for web search using clickthrough data Proceedings of the 22nd ACM International Conference on Information and Knowledge Management CIKM \u201913 November 2013 California CA USA Association for Computing Machinery 2333\u20132338 https:\/\/doi.org\/10.1145\/2505515.2505665 2-s2.0-84889566627.","DOI":"10.1145\/2505515.2505665"},{"key":"e_1_2_11_19_2","unstructured":"MikolovT. ChenK. CorradoG. andDeanJ. Efficient estimation of word representations in vector space 2013 https:\/\/arxiv.org\/abs\/1301.3781."},{"key":"e_1_2_11_20_2","doi-asserted-by":"publisher","DOI":"10.1002\/cae.22253"},{"key":"e_1_2_11_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/bf00288933"},{"key":"e_1_2_11_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"e_1_2_11_23_2","doi-asserted-by":"publisher","DOI":"10.1090\/conm\/026\/737400"},{"key":"e_1_2_11_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/tpami.2014.2361319"},{"key":"e_1_2_11_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-01258-8_13"},{"key":"e_1_2_11_26_2","doi-asserted-by":"crossref","unstructured":"J\u00e9gouH. TavenardR. DouzeM. andAmsalegL. Searching in one billion vectors: re-rank with source coding 2011 https:\/\/arxiv.org\/abs\/1102.3828.","DOI":"10.1109\/ICASSP.2011.5946540"},{"key":"e_1_2_11_27_2","doi-asserted-by":"crossref","unstructured":"MathiesonL.andMoscatoP. An introduction to proximity graphs 2019 Springer International Publishing Cham Switzerland 213\u2013233 https:\/\/doi.org\/10.1007\/978-3-030-06222-4_4.","DOI":"10.1007\/978-3-030-06222-4_4"},{"key":"e_1_2_11_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31537-4_18"},{"key":"e_1_2_11_29_2","doi-asserted-by":"publisher","DOI":"10.1038\/30918"},{"key":"e_1_2_11_30_2","unstructured":"ProkhorenkovaL. Graph-based nearest neighbor search: From practice to theory 2019 http:\/\/arxiv.org\/abs\/1907.00845."},{"volume-title":"Computers and Pattern Recognition","year":"1966","author":"Arkadev A.","key":"e_1_2_11_31_2"},{"key":"e_1_2_11_32_2","first-page":"587","volume-title":"Cours d\u2019analyse de l\u2019\u00c9cole polytechnique","author":"Jordan C.","year":"1887"},{"volume-title":"Algebraic Topology","year":"1966","author":"Spanier E.","key":"e_1_2_11_33_2"},{"key":"e_1_2_11_34_2","doi-asserted-by":"publisher","DOI":"10.1023\/a:1007626913721"},{"key":"e_1_2_11_35_2","doi-asserted-by":"publisher","DOI":"10.17586\/2226-1494-2019-19-3-546-552"},{"key":"e_1_2_11_36_2","doi-asserted-by":"publisher","DOI":"10.1038\/ncomms5308"},{"key":"e_1_2_11_37_2","doi-asserted-by":"publisher","DOI":"10.1016\/s0168-1699(99)00046-0"},{"key":"e_1_2_11_38_2","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(80)90066-7"}],"container-title":["Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/journals\/complexity\/2021\/2011738.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/complexity\/2021\/2011738.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1155\/2021\/2011738","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,9]],"date-time":"2024-08-09T22:02:53Z","timestamp":1723240973000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1155\/2021\/2011738"}},"subtitle":[],"editor":[{"given":"Siew Ann","family":"Cheong","sequence":"additional","affiliation":[]}],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1155\/2021\/2011738"],"URL":"https:\/\/doi.org\/10.1155\/2021\/2011738","archive":["Portico"],"relation":{},"ISSN":["1076-2787","1099-0526"],"issn-type":[{"type":"print","value":"1076-2787"},{"type":"electronic","value":"1099-0526"}],"subject":[],"published":{"date-parts":[[2021,1]]},"assertion":[{"value":"2021-05-17","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-29","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-11-29","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"2011738"}}