An algorithm on probabilistic frequent nearest neighbor query over snapshots of uncertain database with locally correlation

Research on locally correlated spatial uncertain data recently gets more and more attentions in many practical applications. This paper proposes a novel probabilistic frequent nearest neighbor query over snapshots of uncertain database with locally correlation, which retrievals those objects which can be seen as the nearest neighbor of query point with a certain probability frequently. The existing methods of processing nearest neighbor query over traditional data or uncertain data cannot be used to process this kind of query because of the expensive time consuming. In order to solve this problem, we propose a generic framework, including several filters based on chernoff bound and the dynamic programme used to compute the probability mass function. We provide two filtering methods for two phases. The extended form of chernoff upper bound is used to filter lots of candidates objects at the first phase; while at the second phase, we use the standard form of chernoff bound. Then we also discuss the filters and dynamic programme used to process the extended LC-PFNN query. At last, we conduct experiments both on real and synthetic data set, and the results demonstrate that our method is effective enough, which lays a solid foundation for further research.