Journal
IEEE TRANSACTIONS ON FUZZY SYSTEMS
Volume 24, Issue 6, Pages 1349-1363Publisher
IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC
DOI: 10.1109/TFUZZ.2016.2516562
Keywords
Incomplete data; k nearest neighbor search; query processing
Funding
- 973 Program [2015CB352502]
- National Natural Science Foundation of China [61522208, 61379033, 61472348]
- Fundamental Research Funds for the Central Universities
Ask authors/readers for more resources
Given a set S 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 kNNquery for incomplete data. We formalize this problem and propose an efficient lattice partition algorithm using our newly developed L alpha B index to support exact IkNN retrieval, with the help of two pruning heuristics, i.e., a 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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available