Related Research On K-nearest-neighbor Algorithm Over Uncertain Data

Uncertain data widely exists in real life, such as economic, military, logistics, financialservices and telecommunications fields, etc. With the development of tecnology and theunderstanding of data processing, there is a hot demand for query over uncertain data in variousapplication domains, and query for objects closest or most similar to a given target overuncertain data has been an important type of queries in these domains.In the field of uncertain data management,"possible world model" is a widely used andeffective model in that field. Data uncertainty is divided into tuple and attribute uncertainty, andthis paper focus on the attribute uncertainty and do some raleted rearch on the k-nearest-neighboralgorithm (PkNN) over uncertain data.In order to improve the efficiency of PkNN query, we present in this paper acenter-of-mass-based distance pruning algorithm which improves the computational efficiency ofPkNN without sacrificing its accuracy, especially the uncertain area of objects is in nonuniformdistribution. Experimental results are also provided to demonstrate its effectiveness.Traditional PkNN algorithms are mostly base on the euclidean space, yet in the applicationsuch as Local Based Service (LBS), queries are based on road networks, which are differentfrom the traditional types. Therefore, we research the PkNN (k=1) algorithm in road networksand make it more close to the actual situation.