Indoor Space Reverse K-Nearest Neighbor Query Algorithm And Demonstration System

A large part of people's modern life lives indoors,such as homes,offices,shopping malls,universities,libraries and airports.However,many existing location-based services are only designed for outdoor spaces,mainly because positioning technologies such as GPS cannot accurately identify the location of indoor venues.However,breakthroughs in indoor positioning technology in recent years have begun to gradually overcome this dilemma,bringing huge future opportunities for research institutions,government agencies,technology giants and enterprising start-ups,the use of indoor location-based services.Therefore,indoor data management has received great research attention in the past few years,and location-based services in indoor spaces have great prospects in the next few years,such as emergency services,in-store advertising,shopping,tracking,tour guides,and more.The reverse k-nearest neighbor query of indoor space is one of the important applications of location-based services,which can be used to approximate the influence calculation of spatial objects and has broad applications in indoor facility location and indoor marketing.The reverse k-nearest neighbor query has been studied extensively in outdoor spaces.However,due to the fundamental difference between indoor and outdoor space,the outdoor techniques can not be applied for indoor space.First,the indoor space is characterized by entities such as doors,rooms,and corridors.These entities greatly restrict the movement of objects in the indoor space.Therefore,outdoor spatial distance metrics such as Euclidean distance and road network distances can not be used to measure indoor distances.Second,the topology of indoor space is usually complicated.The complicated topology of indoor space provide challenges of data modelling and query processing.In this paper,we give a problem definition for reverse k-nearest neighbor query in indoor environments,and we design a series of efficient pruning strategies to reduce computational cost by studying the properties of indoor environments.Based on these pruning strategies,we propose the IRV(Indoor Reverse k Nearest Neighbor based on VIP Tree)algorithm to efficiently handle indoor reverse k Nearest Neighbor queries.The IRV algorithm adopts the algorithm framework of pruning first and then verification,and is based on the most advanced indoor index structure VIP Tree.In addition,we optimize the basic pruning method to reduce the consumption in the pruning process.The experiment results on both real and synthetic data sets show our proposed method outperforms the baseline algorithm.And we designed a new indoor spatial data management demonstration system,IndoorViz,which integrates VIP Tree and KP Tree index structures and a variety of well-designed query processing algorithms and 3D visualization functions.The IndoorViz system can support indoor spatial object indexing,efficient query processing and interactive 3D display.