{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,24]],"date-time":"2025-08-24T01:55:20Z","timestamp":1756000520087,"version":"3.41.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2018,10,22]],"date-time":"2018-10-22T00:00:00Z","timestamp":1540166400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2018,11,15]]},"abstract":"<jats:p>\n            Although many fast methods exist for constructing a\n            <jats:italic>k<\/jats:italic>\n            NN-graph for low-dimensional data, it is still an open question how to do it efficiently for high-dimensional data. We present a new method to construct an approximate\n            <jats:italic>k<\/jats:italic>\n            NN-graph for medium- to high-dimensional data. Our method uses one-dimensional mapping with a Z-order curve to construct an initial graph and then continues to improve this using neighborhood propagation. Experiments show that the method is faster than the compared methods with five different benchmark datasets, the dimensionality of which ranges from 14 to 784. Compared to a brute-force approach, the method provides a speedup between 12.7:1 and 414.2:1 depending on the dataset. We also show that errors in the approximate\n            <jats:italic>k<\/jats:italic>\n            NN-graph originate more likely from outlier points; and, it can be detected during runtime, which points are likely to have errors in their neighbors.\n          <\/jats:p>","DOI":"10.1145\/3274656","type":"journal-article","created":{"date-parts":[[2018,10,22]],"date-time":"2018-10-22T12:08:16Z","timestamp":1540210096000},"page":"1-21","source":"Crossref","is-referenced-by-count":8,"title":["Constructing a High-Dimensional\n            <i>k<\/i>\n            NN-Graph Using a Z-Order Curve"],"prefix":"10.1145","volume":"23","author":[{"given":"Sami","family":"Sieranoja","sequence":"first","affiliation":[{"name":"University of Eastern Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pasi","family":"Fr\u00e4nti","sequence":"additional","affiliation":[{"name":"University of Eastern Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,10,22]]},"reference":[{"volume-title":"Proceedings of the 8th International Conference on Database Theory (ICDT\u201901)","author":"Aggarwal Charu C.","key":"e_1_2_1_1_1","unstructured":"Charu C. Aggarwal , Alexander Hinneburg , and Daniel A. Keim . 2001. On the surprising behavior of distance metrics in high dimensional spaces . In Proceedings of the 8th International Conference on Database Theory (ICDT\u201901) . Springer-Verlag, London, UK, 422--434. Charu C. Aggarwal, Alexander Hinneburg, and Daniel A. Keim. 2001. On the surprising behavior of distance metrics in high dimensional spaces. In Proceedings of the 8th International Conference on Database Theory (ICDT\u201901). Springer-Verlag, London, UK, 422--434."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/060673096"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1162\/089976603321780317"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/645503.656271"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1969.1054385"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2010.5539852"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.eswa.2010.12.077"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2003.12.002"},{"key":"e_1_2_1_9_1","article-title":"Fast approximate k NN graph construction for high dimensional data via recursive Lanczos bisection","author":"Chen Jie","year":"2009","unstructured":"Jie Chen , Haw-ren Fang, and Yousef Saad . 2009 . Fast approximate k NN graph construction for high dimensional data via recursive Lanczos bisection . The Journal of Machine Learning Research 10 ( Sep. 2009), 1989--2012. http:\/\/www.jmlr.org\/papers\/v10\/. Jie Chen, Haw-ren Fang, and Yousef Saad. 2009. Fast approximate k NN graph construction for high dimensional data via recursive Lanczos bisection. The Journal of Machine Learning Research 10 (Sep. 2009), 1989--2012. http:\/\/www.jmlr.org\/papers\/v10\/.","journal-title":"The Journal of Machine Learning Research 10"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2010.9"},{"volume-title":"Computer Graphics Forum","author":"Dafner Revital","key":"e_1_2_1_11_1","unstructured":"Revital Dafner , Daniel Cohen-Or , and Yossi Matias . 2000. Context-based space filling curves . In Computer Graphics Forum , Vol. 19 . Wiley Online Library , 209--218. Revital Dafner, Daniel Cohen-Or, and Yossi Matias. 2000. Context-based space filling curves. In Computer Graphics Forum, Vol. 19. Wiley Online Library, 209--218."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963487"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 7th International Conference on Data Engineering. IEEE Computer Society, Washington, D.C., 152--159","author":"Faloutsos Christos","year":"1991","unstructured":"Christos Faloutsos and Yi Rong . 1991 . DOT: A spatial access method using fractals . In Proceedings of the 7th International Conference on Data Engineering. IEEE Computer Society, Washington, D.C., 152--159 . Christos Faloutsos and Yi Rong. 1991. DOT: A spatial access method using fractals. In Proceedings of the 7th International Conference on Data Engineering. IEEE Computer Society, Washington, D.C., 152--159."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/73721.73746"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/951949.952120"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2006.227"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/355744.355745"},{"key":"e_1_2_1_18_1","volume-title":"EFANNA: An extremely fast approximate nearest neighbor search algorithm based on kNN graph. CoRR abs\/1609.07228","author":"Fu Cong","year":"2016","unstructured":"Cong Fu and Deng Cai . 2016 . EFANNA: An extremely fast approximate nearest neighbor search algorithm based on kNN graph. CoRR abs\/1609.07228 (2016). Cong Fu and Deng Cai. 2016. EFANNA: An extremely fast approximate nearest neighbor search algorithm based on kNN graph. CoRR abs\/1609.07228 (2016)."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPRW.2008.4563100"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/358728.358741"},{"key":"e_1_2_1_21_1","volume-title":"IJCAI Proceedings-International Joint Conference on Artificial Intelligence","volume":"22","author":"Hajebi Kiana","year":"2011","unstructured":"Kiana Hajebi , Yasin Abbasi-Yadkori , Hossein Shahbazi , and Hong Zhang . 2011 . Fast approximate nearest-neighbor search with k-nearest neighbor graph . In IJCAI Proceedings-International Joint Conference on Artificial Intelligence , Vol. 22 . 1312. Kiana Hajebi, Yasin Abbasi-Yadkori, Hossein Shahbazi, and Hong Zhang. 2011. Fast approximate nearest-neighbor search with k-nearest neighbor graph. In IJCAI Proceedings-International Joint Conference on Artificial Intelligence, Vol. 22. 1312."},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Ville Hautam\u00e4ki Ismo K\u00e4rkk\u00e4inen and Pasi Fr\u00e4nti. 2004. Outlier detection using k-nearest neighbour graph. In ICPR (3). 430--433.   Ville Hautam\u00e4ki Ismo K\u00e4rkk\u00e4inen and Pasi Fr\u00e4nti. 2004. Outlier detection using k-nearest neighbour graph. In ICPR (3). 430--433.","DOI":"10.1109\/ICPR.2004.1334558"},{"key":"e_1_2_1_23_1","volume-title":"Recursive tilings and space-filling curves with little fragmentation. arXiv preprint arXiv:1002.1843","author":"Haverkort Herman","year":"2010","unstructured":"Herman Haverkort . 2010. Recursive tilings and space-filling curves with little fragmentation. arXiv preprint arXiv:1002.1843 ( 2010 ). Herman Haverkort. 2010. Recursive tilings and space-filling curves with little fragmentation. arXiv preprint arXiv:1002.1843 (2010)."},{"volume-title":"Proceedings of the 26th VLDB Conference, Cario, Egypt.","author":"Hinneburg Alexander","key":"e_1_2_1_24_1","unstructured":"Alexander Hinneburg , Charu C. Aggarwal , and Daniel A. Keim . 2000. What is the nearest neighbor in high dimensional spaces? In Proceedings of the 26th VLDB Conference, Cario, Egypt. Alexander Hinneburg, Charu C. Aggarwal, and Daniel A. Keim. 2000. What is the nearest neighbor in high dimensional spaces? In Proceedings of the 26th VLDB Conference, Cario, Egypt."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.726791"},{"volume-title":"Proceedings of the 17th International Conference on Data Engineering (ICDE\u201901)","author":"Liao Swanwa","key":"e_1_2_1_27_1","unstructured":"Swanwa Liao , Mario A. Lopez , and Scott T. Leutenegger . 2001. High dimensional similarity search with space filling curves . In Proceedings of the 17th International Conference on Data Engineering (ICDE\u201901) . 615--622. Swanwa Liao, Mario A. Lopez, and Scott T. Leutenegger. 2001. High dimensional similarity search with space filling curves. In Proceedings of the 17th International Conference on Data Engineering (ICDE\u201901). 615--622."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/850924.851523"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10619-010-7070-7"},{"volume-title":"A Computer Oriented Geodetic Data Base and a New Technique in File Sequencing","author":"Morton Guy M.","key":"e_1_2_1_30_1","unstructured":"Guy M. Morton . 1966. A Computer Oriented Geodetic Data Base and a New Technique in File Sequencing . International Business Machines Company . Guy M. Morton. 1966. A Computer Oriented Geodetic Data Base and a New Technique in File Sequencing. International Business Machines Company."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/588011.588037"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/82.257335"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2007.70814"},{"key":"e_1_2_1_34_1","first-page":"71","article-title":"Multidimensional range search in dynamically balanced trees","volume":"2","author":"Tropf Herbert","year":"1981","unstructured":"Herbert Tropf and H. Herzog . 1981 . Multidimensional range search in dynamically balanced trees . ANGEWANDTE INFO. 2 (1981), 71 -- 77 . Herbert Tropf and H. Herzog. 1981. Multidimensional range search in dynamically balanced trees. ANGEWANDTE INFO. 2 (1981), 71--77.","journal-title":"ANGEWANDTE INFO."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/2354409.2354854"},{"key":"e_1_2_1_36_1","unstructured":"Jens-Michael Wierum. 2002. Logarithmic path-length in space-filling curves. In CCCG. 22--26.  Jens-Michael Wierum. 2002. Logarithmic path-length in space-filling curves. In CCCG. 22--26."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447837"},{"volume-title":"Machine Learning and Knowledge Discovery in Databases","author":"Zhang Yan-Ming","key":"e_1_2_1_38_1","unstructured":"Yan-Ming Zhang , Kaizhu Huang , Guanggang Geng , and Cheng-Lin Liu . 2013. Fast kNN graph construction with locality sensitive hashing . In Machine Learning and Knowledge Discovery in Databases . Springer , 660--674. Yan-Ming Zhang, Kaizhu Huang, Guanggang Geng, and Cheng-Lin Liu. 2013. Fast kNN graph construction with locality sensitive hashing. In Machine Learning and Knowledge Discovery in Databases. Springer, 660--674."}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3274656","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3274656","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:57:56Z","timestamp":1750208276000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3274656"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10,22]]},"references-count":38,"alternative-id":["10.1145\/3274656"],"URL":"https:\/\/doi.org\/10.1145\/3274656","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2018,10,22]]}}}