Advanced Search
    Zhang Liping, Liu Lei, Hao Xiaohong, Li Song, Hao Zhongxiao. Voronoi-Based Group Reverse k Nearest Neighbor Query in Obstructed Space[J]. Journal of Computer Research and Development, 2017, 54(4): 861-871. DOI: 10.7544/issn1000-1239.2017.20151111
    Citation: Zhang Liping, Liu Lei, Hao Xiaohong, Li Song, Hao Zhongxiao. Voronoi-Based Group Reverse k Nearest Neighbor Query in Obstructed Space[J]. Journal of Computer Research and Development, 2017, 54(4): 861-871. DOI: 10.7544/issn1000-1239.2017.20151111

    Voronoi-Based Group Reverse k Nearest Neighbor Query in Obstructed Space

    • In order to solve the problem that the existing methods can not deal with the group reverse k nearest neighbor (GRkNN) query in obstructed space, the group reverse k nearest neighbor query method (OGRkNN) in obstructed space based on Voronoi diagram is put forward. The method finds data points that take any point in the query objects set as one of their obstacle k nearest neighbors. In the practical application, OGRkNN query can be used to evaluate the influence of a group of query objects. According to the changes of the obstacle set, the OGRkNN query in static obstacle environment (STA_OGRkNN query) and the OGRkNN query in dynamic obstacle environment (DYN_OGRkNN query) are given. The STA_OGRkNN query method greatly reduces the number of non-candidates by the properties of Voronoi diagram in pruning stage, and reduces the searching ranges quickly, which improves query efficiency. It also improves the accuracy of the algorithm in refining stage. Then three DYN_OGRkNN query algorithms are given. They are the OGRkNN query algorithm under the condition of dynamically increasing obstacles, the OGRkNN query algorithm under the condition of dynamically reducing obstacles and the OGRkNN query algorithm under the condition of dynamically moving obstacles. Theoretical study and experiments show that the proposed algorithms have extremely high efficiency.
    • loading

    Catalog

      Turn off MathJax
      Article Contents

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return