Path $khbox{NN}$ Query Processing in Mobile Systems

摘要

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-based $k$ nearest neighbor $(pkhbox{NN})$. Given a set of candidate interest objects, a query point, and the number of objects $k$, $pkhbox{NN}$ finds the shortest path that goes through all $k$ interest objects with the minimum shortest distance among all possible paths. $pkhbox{NN}$ is useful when users would like to visit all $k$ interest objects one by one from the query point, in which $pkhbox{NN}$ will give the users the shortest path. We have addressed the complexities of the $pkhbox{NN}$ method, covering various looping paths, U-turn, and the possibilities to encounter local minima. Our performance evaluations show that $pkhbox{NN}$ performs well in respect to various object densities on the map due to our proposed pruning methods to r- duce the search space.