School of
Information Technology and Electrical Engineering

Adaptive Indexing and Query Processing in Spatial Networks

Ms Jiping WangFri, 08/11/2013 - 11:00
Prof Xiaofang Zhou

The prevalence of GPS-enabled mobile devices and wireless communication have given rise to a wide range of location-based services(e.g. Foursquare, Google Maps). These services constantly require efficient processing of spatial queries such as k nearest neighbour and range queries. For example, an user may want to find the nearest five restaurants while visiting an unfamiliar city, which invokes a k-nearest neighbour query. Meanwhile in most applications, the movements of objects are often constrained to existed spatial networks(e.g. road networks). In the context of spatial networks, the distance between two objects is measured by the length of shortest path between them along the network, in which case the processing of spatial queries is quite different from that in Euclidean space.

This project focuses on providing an indexing structure that supports efficient spatial query processing. Traditional and most classic solution to evaluate queries in spatial networks is Dijkstra's algorithm and its variations. But they are quite inefficient for large scale spatial networks since it requires traversing a large portion of the network when objects are not densely distributed on network. A plethora of techniques have been proposed to solve this kind of problem. Some of them have achieved great efficiency by incorporating pre-computed information to query processing, but may require huge space and preprocessing cost. On the other hand, the topologies of networks and objects distribution are seldom considered at the same time. This motivated us to create an indexing that takes advantage of both network topologies and objects distribution over the network, as the topologies decide the shortest path computation and objects distribution speaks for the query occurrence probabilities. To achieve this goal, we construct our indexing based on hierarchical graph partitioning and incorporate a cost model to the partition process to adjust the influence of object distribution. We also propose an efficient dynamic programming algorithm to solve shortest path queries utilizing this indexing and give a thorough evaluation for query processing on large spatial networks.


Jiping Wang is currently an MPhil candidate in DKE group, School of ITEE at the University of Queensland. She obtained her Bachelor degree in Department of Computer Science and Technology from Tsinghua University in 2010. Her research interests include efficient spatial data indexing and query processing.

Seminar Type: 

MPhil Confirmation Seminar