Processing Incomplete k Nearest Neighbor Search
Processing Incomplete k Nearest Neighbor Search
复制标题
DOI：
10.1109/tfuzz.2016.2516562
复制
发表时间：
2016-12
影响因子：
11.9
通讯作者：
Xiaoye Miao;Yunjun Gao;Gang Chen;Baihua Zheng;Huiyong Cui
中科院分区：
文献类型：
--
作者：
Xiaoye Miao;Yunjun Gao;Gang Chen;Baihua Zheng;Huiyong Cui
给定多维对象的集合S和查询对象q，k最近邻（kNN）查询从S找到与q最接近的k个对象。这种查询是数据库、数据挖掘和信息检索研究中的一个基本问题。它在诸如图像识别和基于位置的服务等广泛的真实的应用中起着重要的作用。然而，由于数据传输设备的故障、存储不当、意外丢失等原因，不完整数据广泛存在于那些数据项的维值缺失的应用中。本文针对不完全数据的k近邻查询，系统地研究了不完全k近邻搜索。我们形式化了这个问题，并提出了一个有效的格划分算法，使用我们新开发的LαB索引，以支持精确的IkNN检索，在两个修剪算法的帮助下，即，α值剪枝和部分距离剪枝。此外，我们提出了一种近似算法，即直方图近似，以支持近似IkNN搜索，提高搜索效率和保证误差界。使用真实的和合成数据集的大量实验证明了新设计的索引和修剪算法的有效性，以及我们提出的算法在各种实验设置下的性能。
Given a setS of multidimensional objects and a query object q, a k nearest neighbor (kNN) query finds from S the k closest objects to q. This query is a fundamental problem in database, data mining, and information retrieval research. It plays an important role in a wide spectrum of real applications such as image recognition and location-based services. However, due to the failure of data transmission devices, improper storage, and accidental loss, incomplete data exist widely in those applications, where some dimensional values of data items are missing. In this paper, we systematically study incomplete k nearest neighbor (IkNN) search, which aims at the kNN query for incomplete data. We formalize this problem and propose an efficient lattice partition algorithm using our newly developed LαB index to support exact IkNN retrieval, with the help of two pruning heuristics, i.e., α value pruning and partial distance pruning. Furthermore, we propose an approximate algorithm, namely histogram approximate, to support approximate IkNN search with improved search efficiency and guaranteed error bound. Extensive experiments using both real and synthetic datasets demonstrate the effectiveness of newly designed indexes and pruning heuristics, as well as the performance of our presented algorithms under a variety of experimental settings.