Processing Incomplete k Nearest Neighbor Search

摘要: Given a set S of multidimensional objects and query object q , k nearest neighbor ( NN) finds from the closest to . This is fundamental problem in database, data mining, information retrieval research. It plays an important role wide spectrum real applications such as image recognition location-based services. However, due failure transmission devices, improper storage, accidental loss, incomplete exist widely those applications, where some dimensional values items are missing In this paper, we systematically study (I search which aims at NN for data. We formalize propose efficient lattice partition algorithm using our newly developed $L\alpha B$ index support exact I retrieval, with help two pruning heuristics, i.e., $\alpha $ value partial distance Furthermore, approximate algorithm, namely histogram improved efficiency guaranteed error bound. Extensive experiments both synthetic datasets demonstrate effectiveness designed indexes well performance presented algorithms under variety experimental settings.