中国科学院机构知识库网格
Chinese Academy of Sciences Institutional Repositories Grid
首页 机构 成果 学者
  
  1. CAS IR Grid
  2. 自动化研究所
  3. 中国科学院自动化研究所
  4. 智能感知与计算研究中心
A new fast search algorithm for exact k-nearest neighbors based on optimal triangle-inequality-based check strategy

文献类型：期刊论文

作者Pan, Yiwei1; Pan, Zhibin1; Wang, Yikun1; Wang, Wei2
刊名KNOWLEDGE-BASED SYSTEMS
出版日期2020-02-15
卷号189页码:11
ISSN号0950-7051
关键词Exact k-nearest neighbors Fast search algorithm Clustering Triangle inequality Optimal check strategy
DOI10.1016/j.knosys.2019.105088
通讯作者Pan, Zhibin(zbpan@mail.xjtu.edu.cn)
英文摘要The k-nearest neighbor (KNN) algorithm has been widely used in pattern recognition, regression, outlier detection and other data mining areas. However, it suffers from the large distance computation cost, especially when dealing with big data applications. In this paper, we propose a new fast search (FS) algorithm for exact k-nearest neighbors based on optimal triangle-inequality-based (OTI) check strategy. During the procedure of searching exact k-nearest neighbors for any query, the OTI check strategy can eliminate more redundant distance computations for the instances located in the marginal area of neighboring clusters compared with the original TI check strategy. Considering the large space complexity and extra time complexity of OTI, we also propose an efficient optimal triangle-inequality-based (EOTI) check strategy. The experimental results demonstrate that our proposed two algorithms (OTI and EOTI) achieve the best performance compared with other related KNN fast search algorithms, especially in the case of dealing with high-dimensional datasets. (C) 2019 Elsevier B.V. All rights reserved.
资助项目National Key Research and Development Program of China[2018YFC0603501] ; National Key Research and Development Program of China[2018YFC1504202] ; Open Project Program of the National Laboratory of Pattern Recognition (NLPR)[201800030]
WOS研究方向Computer Science
语种英语
出版者ELSEVIER
WOS记录号WOS:000510955100008
资助机构National Key Research and Development Program of China ; Open Project Program of the National Laboratory of Pattern Recognition (NLPR)
源URL[http://ir.ia.ac.cn/handle/173211/28568]  
专题自动化研究所_智能感知与计算研究中心
通讯作者Pan, Zhibin
作者单位1.Xi An Jiao Tong Univ, Sch Elect & Informat Engn, Xian 710049, Peoples R China
2.Chinese Acad Sci, Inst Automat, Natl Lab Pattern Recognit, Beijing 100190, Peoples R China
推荐引用方式
GB/T 7714		 Pan, Yiwei,Pan, Zhibin,Wang, Yikun,et al. A new fast search algorithm for exact k-nearest neighbors based on optimal triangle-inequality-based check strategy[J]. KNOWLEDGE-BASED SYSTEMS,2020,189:11.
APA Pan, Yiwei,Pan, Zhibin,Wang, Yikun,&Wang, Wei.(2020).A new fast search algorithm for exact k-nearest neighbors based on optimal triangle-inequality-based check strategy.KNOWLEDGE-BASED SYSTEMS,189,11.
MLA Pan, Yiwei,et al."A new fast search algorithm for exact k-nearest neighbors based on optimal triangle-inequality-based check strategy".KNOWLEDGE-BASED SYSTEMS 189(2020):11.

入库方式： OAI收割

来源：自动化研究所

浏览0
下载0
收藏0
其他版本

除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。