Probabilistic group nearest neighbor query optimization based on classification using ELM

摘要

AbstractTheprobabilistic group nearest neighbor(PGNN)query , which returns all the uncertain objects whose probabilities of being the group nearest neighbor (GNN) results exceed a user-specified threshold, is widely used in uncertain database. Most existing work for answering PGNN queries adopted a general framework which consist of three phases:spatial pruning, probabilistic pruning, refinement. In the probabilistic pruning phase, dividing the uncertain regions into many partitions to derive a tighter probabilities bounds is a common method. However, there is a tradeoff between the computational cost of probabilistic pruning phase and refinement phase controlled by the granularity of the partitions. In this paper, we study the problem of setting the optimal granularity of the partitions for uncertain objects, and propose a new framework for PGNN queries based on granularity classification using ELM such that the overall cost is minimized. In addition, to improve the accuracy of classification and make the classifier applicable to the dynamic environment, a plurality voting method and a dynamic classification strategy are proposed respectively. Extensive experiments shows that compared with the default granularities of the partitions, the granularities chosen by ELM classifiers are more proper, which further improves the performance of PGNN query algorithm. In addition, ELM outperforms SVM with regard to both the response time and classification accuracy.