A new fast search algorithm for exact k-nearest neighbors based on optimal triangle-inequality-based check strategy

doi:10.1016/j.knosys.2019.105088

CASIA OpenIR > 模式识别实验室

	A new fast search algorithm for exact k-nearest neighbors based on optimal triangle-inequality-based check strategy
	Pan, Yiwei 1; Pan, Zhibin 1; Wang, Yikun 1; Wang, Wei2
发表期刊	KNOWLEDGE-BASED SYSTEMS
ISSN	0950-7051
	2020-02-15
卷号	189 页码:11
通讯作者	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.
关键词	Exact k-nearest neighbors Fast search algorithm Clustering Triangle inequality Optimal check strategy
DOI	10.1016/j.knosys.2019.105088
收录类别	SCI
语种	英语
资助项目	Open Project Program of the National Laboratory of Pattern Recognition (NLPR)[201800030] ; National Key Research and Development Program of China[2018YFC1504202] ; National Key Research and Development Program of China[2018YFC0603501] ; 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]
项目资助者	National Key Research and Development Program of China ; Open Project Program of the National Laboratory of Pattern Recognition (NLPR)
WOS研究方向	Computer Science
WOS类目	Computer Science, Artificial Intelligence
WOS记录号	WOS:000510955100008
出版者	ELSEVIER
引用统计	被引频次：20[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://ir.ia.ac.cn/handle/173211/28569
专题	模式识别实验室
通讯作者	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.