Font Size: a A A

Research On Continuous K Nearest Neighbour Queries In Road Network

Posted on:2009-07-04Degree:MasterType:Thesis
Country:ChinaCandidate:X L LiFull Text:PDF
GTID:2178360245986307Subject:Computer software and theory
Abstract/Summary:PDF Full Text Request
With the development of wireless network communications and global positioning technologies, there raises many kinds of related new applications, e.g. location-based services. One of the most important kinds of queries in spatial databases to support location-based services is the continuous k neighbour (CkNN) query. Given a spatial data set of points of interest and a moving query point q, a CkNN query in road network computes the k data points that lie closest to a given query point q.Most of the research in Spatial Databases (SDB) considers only the Euclidean space. Consequently, distance-based queries, like the k Nearest Neighbour query, use the Euclidean distance between object. However, in some applications, the objects'position and movement are constrained to network, for example roads, highways, railways etc. In these applications, the important distance measure is the network distance. For these network constrained spatial data, Spatial Network Databases (SNDB) are provided. Every conventional spatial query type (e.g. nearest neighbour query, range query, join query) has a counterpart in SNDB.The ability to support continuous queries from moving objects on road network is essential for a class of mobile applications. The paper considers a CkNN query which handles three types of objects: roads, moving objects, and static objects. In which moving objects (e.g. cars or people) run on road network, static objects (e.g. gas stations or restaurants) are located on road network. Moving objects are query points, static objects are data points.The paper has mainly finished the following research work: First, having improved the road network model and transformed it into the related chart. Secondly, having finished the continuous k nearest neighbour queries based on the chart and Dijkstra simple source shortest path algorithm, and renewed the database and the query result with the movement of the moving objects. The new query result will be sended to the client sides to realize the continuous k Nearest Neighbor query. Finally, having proved the accuracy and validity of the algorithms with experiments.
Keywords/Search Tags:Spatial Databases, Road Network, Continuous K-Nearest Neighbour, R-Tree
PDF Full Text Request
Related items