What is K-Nearest Neighbor Query

Location-based services (LBSs) utilize consumer electronics, mobile communications, positioning technology, and traditional map information to provide mobile users with new kinds of online services. Examples include location-sensitive information services that identify points of interest that are in some sense nearest and of interest to their users and that offer travel directions to their users. Data management is a core aspect of the provisioning of LBSs. The diversity and complexity of LBSs demand novel and advanced data management techniques. The scenario of network-constrained movement is of particular interest to LBSs as a large amount of users of LBSs are car drivers and mobile users moving in vehicles. We term the transportation networks where LBS users are moving as spatial networks. The databases that manage the spatial network data as well as other relevant data are termed spatial network databases (SNDBs). Data management in SNDBs poses novel challenges to the database research community. Specifically, most existing discussions on spatial databases assume that objects can move arbitrarily in Euclidean space. The fundamental difference between network-constrained space and the Euclidean space is that the distance of two objects cannot be computed by their coordinates but by the shortest path on the network (Jensen, Kolár, Pedersen, & Timko, 2003). This makes it difficult to extend the existing data models, indexing structures, and query processing techniques from spatial databases to SNDBs.