Path $k\hbox{NN}$ Query Processing in Mobile Systems
Geng Zhao, Kefeng Xuan, David Taniar · IEEE Transactions on Industrial Electronics · 2011
Digital ecosystems which have been inspired by natural systems aim to address the complexity of digital world which is expected to have the capabilities to self-organize, is scalable, and is attainable. Spatial networks consisting of geospatial objects and paths that link the objects form a digital ecosystem in the context of geoinformatics. With the recent development of mobile devices using inexpensive wireless networks, applications to access interest objects and their paths in the spatial world are getting more in demand. In this paper, we introduce the concept of path-basedknearest neighbor (pkNN). Given a set of candidate interest objects, a query point, and the number of objectsk,pkNN finds the shortest path that goes through allkinterest objects with the minimum shortest distance among all possible paths.pkNN is useful when users would like to visit allkinterest objects one by one from the query point, in whichpkNN will give the users the shortest path. We have addressed the complexities of thepkNN method, covering various looping paths, U-turn, and the possibilities to encounter local minima. Our performance evaluations show thatpkNN performs well in respect to various object densities on the map due to our proposed pruning methods to reduce the search space.