{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T07:35:55Z","timestamp":1770968155990,"version":"3.50.1"},"reference-count":22,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Semantic Computing"],"published-print":{"date-parts":[[2015,9]]},"abstract":"<jats:p> Nearest neighbor search is a key technique used in hierarchical clustering and its computing complexity decides the performance of the hierarchical clustering algorithm. The time complexity of standard agglomerative hierarchical clustering is O(n<jats:sup>3<\/jats:sup>), while the time complexity of more advanced hierarchical clustering algorithms (such as nearest neighbor chain, SLINK and CLINK) is O(n<jats:sup>2<\/jats:sup>). This paper presents a new nearest neighbor search method called nearest neighbor boundary (NNB), which first divides a large dataset into independent subset and then finds nearest neighbor of each point in subset. When NNB is used, the time complexity of hierarchical clustering can be reduced to O(n log <jats:sup>2<\/jats:sup>n). Based on NNB, we propose a fast hierarchical clustering algorithm called nearest-neighbor boundary clustering (NBC), and the proposed algorithm can be adapted to the parallel and distributed computing framework. The experimental results demonstrate that our algorithm is practical for large datasets. <\/jats:p>","DOI":"10.1142\/s1793351x15400085","type":"journal-article","created":{"date-parts":[[2015,10,20]],"date-time":"2015-10-20T15:07:25Z","timestamp":1445353645000},"page":"307-331","source":"Crossref","is-referenced-by-count":2,"title":["NBC: An Efficient Hierarchical Clustering Algorithm for Large Datasets"],"prefix":"10.1142","volume":"09","author":[{"given":"Wei","family":"Zhang","sequence":"first","affiliation":[{"name":"School of Computer Science and Engineering, Nanjing University of Science and Technology, 200 XiaoLingWei Rd., Nanjing 210094, China"}]},{"given":"Gongxuan","family":"Zhang","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, Nanjing University of Science and Technology, 200 XiaoLingWei Rd., Nanjing 210094, China"}]},{"given":"Yongli","family":"Wang","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, Nanjing University of Science and Technology, 200 XiaoLingWei Rd., Nanjing 210094, China"}]},{"given":"Zhaomeng","family":"Zhu","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, Nanjing University of Science and Technology, 200 XiaoLingWei Rd., Nanjing 210094, China"}]},{"given":"Tao","family":"Li","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, Nanjing University of Science and Technology, 200 XiaoLingWei Rd., Nanjing 210094, China"}]}],"member":"219","published-online":{"date-parts":[[2015,10,20]]},"reference":[{"key":"rf1","unstructured":"P.\u00a0Tan, M.\u00a0Steinbach and V.\u00a0Kumar, Introduction to Data Mining (Addison-Wesley Longman, 2005)\u00a0pp. 516\u2013518."},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/26.4.354"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/16.1.30"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/20.4.364"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.88"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1007\/BF00288933"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04245-8_14"},{"key":"rf13","doi-asserted-by":"publisher","DOI":"10.1145\/282957.282966"},{"key":"rf14","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"rf17","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1967.1053964"},{"key":"rf18","doi-asserted-by":"publisher","DOI":"10.1145\/361002.361007"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1007\/BF01890115"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-72087-1_20"},{"key":"rf22","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/10.3.271"},{"key":"rf23","first-page":"352","volume":"3","author":"Bellman R.","year":"1966","journal-title":"Dynamic Programming \u2014ResearchGate"},{"key":"rf24","volume-title":"New York, Times Archived from the Original on","author":"Vance A.","year":"2010"},{"key":"rf25","first-page":"6","volume":"35","author":"Shvachko K. V.","year":"2010","journal-title":"LOGIN"},{"key":"rf28","doi-asserted-by":"publisher","DOI":"10.1111\/j.1469-1809.1936.tb02137.x"},{"key":"rf29","doi-asserted-by":"publisher","DOI":"10.2307\/2394164"},{"key":"rf30","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2012.08.009"},{"key":"rf31","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500845"},{"key":"rf32","volume":"1","author":"Li T.","year":"2008","journal-title":"MIJ"}],"container-title":["International Journal of Semantic Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793351X15400085","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T03:40:19Z","timestamp":1565149219000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793351X15400085"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9]]},"references-count":22,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2015,10,20]]},"published-print":{"date-parts":[[2015,9]]}},"alternative-id":["10.1142\/S1793351X15400085"],"URL":"https:\/\/doi.org\/10.1142\/s1793351x15400085","relation":{},"ISSN":["1793-351X","1793-7108"],"issn-type":[{"value":"1793-351X","type":"print"},{"value":"1793-7108","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,9]]}}}