Abstract
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.
TopBackground
Due to the natural similarity between spatial networks and graphs, the study of SNDBs can be traced back to the study of graph models in databases (Gyssens, Paredaens, & Gucht, 1990). The graph models discussed in these works cannot be directly used for LBSs and many real-world aspects of networks, such as U-turns (U-turn means a complete reversal of travel direction) and one-way roads, are not considered. There are also past studies on shortest-path computation in large urban transportation networks (Shekhar, Kohli, & Coyle, 1993). Assuming that network data are stored in disk pages, these papers are focused on techniques that optimize the amount of disk accesses in the shortest-path search.
In the study of LBSs, spatial networks have several distinct differences from graphs. Specifically, the study of graph concentrates on the links between graph nodes, while in spatial networks, positions of nodes are of equal importance to links. Second, as an important element in LBSs, data on points of interest are represented in spatial networks using linear referencing. Next, data modeling of spatial networks often needs to consider the pragmatic constraints in real-world road networks, such as U-turns and one-way roads, which are not very common in the study of graphs. The study of moving-object databases is also relevant to our discussion as users of LBSs are often modeled as moving objects in networks.
We proceed to discuss relevant works in three categories, that is, data modeling of spatial networks and network-constrained moving objects, data structures of spatial networks, and spatial and spatiotemporal query processing in spatial networks.
Key Terms in this Chapter
Data Point: In location-based services, data points represent points of interest in the spatial network databases. A data point is often represented by linear referencing the edges where the data point can be accessed from. In location-based games where the location of other moving objects is of interest, data points can also be used to model moving objects.
K-Nearest Neighbor Query: Given a set of data points in space and a query point, a k-nearest neighbor query finds the k data points that are closest to the query point in terms of their distance to the query point. No other data points are closer to the query point than these k data points. The distance between a query point and a data point can be computed based on Euclidean distance metrics or network distance (if a spatial network is included).
Point of Interest: A point of interest is a geographical site that someone, such as a mobile phone user, may find useful or interesting. Typical points of interest are restaurants, hotels, tourist sites, and so forth.
Query Point: A query point is a location in a spatial network. It represents the current location of a mobile user in reality. Query points are often modeled by linear referencing the network edge where the current location is.
Location-Based Service: Location-based service is a type of mobile service offered by mobile phone companies or a third-party service provider to mobile phone subscribers. This service sends custom information to the mobile phone subscribers based on their current geographical location. A typical example is when the service sends information about the nearest gas station to a mobile phone user.
Spatial Network: A spatial network is a network of spatial elements. The instance of spatial network in location-based service is the transportation network, such as the road network. Elements of a spatial network are, for instance, edges that stand for road segments, nodes that stand for intersections of road segments, and points of interest.
Network Distance: For any two locations in a spatial network, their network distance is the length of the shortest path between these two locations along the network. The shortest path is computed based on the travel weight, such as travel distance or travel time, of network edges.
Spatial Network Database: A spatial network database is a collection of spatial element data of a spatial network. These data are logically represented by a network data model and physically stored in a network data structure. Database systems provide special data types and functions to support spatial network databases.