A Center-of-Gravity-based Distance Pruning Improvement for The Probabilistic k-Nearest-Neighbours Algorithm over Uncertain Data

摘要

Query for objects closest or most similar to a given target has been widely used in practice, particularly in areas such as location-based services and biological feature extraction where uncertain data pervail. Probabilistic k-nearest neighbour (PkNN) query is one of the effective approaches for uncertain objects. We present in this paper a center-of-gravity-based distance pruning algorithm which improves the computational efficiency of PkNN without sacrificing its accuracy. Experimental results are also provided to demonstrate its effectiveness.