Research On Methods For Nearest Neighbor Query On Uncertain Data

Recently, query processing based on uncertain data is becoming research focus.Because the existing query methods on uncertain data are not very perfect and somequeries have not been studied, nearest neighbor query and Nearest Neighbor query withrange Constrained (CNN) on uncertain data are proposed in this paper.Firstly,because the existing nearest neighbor query methods on uncertain data cannot process the concentrated samples effectively, an improved algorithm of nearestneighbor query on uncertain data is proposed in this paper. We divide the samples set ofeach object into k clusters by applying the partitioning clustering algorithm k-means, andthen store these clustered objects in R-tree like index structures. Ranked instances list willbe retrieved through traversing R-tree, which could include samples, clusters, or objects.While unfolding the list, superseding graph G will be revealed gradually based on thesuperseding relationship. The final result sets will be retrieved through pruning andvalidating the superseding graph G.Secondly,Because CNN on precise data can not applied directly to resolve the samequery on uncertain data. CNN on uncertain data is proposed in this paper. To address thisquery, CNN-core is defined in this paper, and an efficient algorithm to find CNN-core isprovided in this paper. First, ranked instances list of the candidates is retrieved, and thensuperseding graph G of CNN will generate while unfolding the ranked instances listgradually. At last, CNN-core will be retrieved through pruning and validating thesuperseding graph G of CNN. Three effective pruning methods to computing thecandidates are proposed.Finally, the methods for two queries proposed above are tested by uniformdistribution and normal distribution data sets. The effectiveness and practicality of twomethods are verified through the experiment.