13-11-2012, 01:56 PM
Evaluating Path Queries over Frequently Updated Route Collections
Abstract
The recent advances in the infrastructure of Geographic
Information Systems (GIS), and the proliferation of GPS
technology, have resulted in the abundance of geodata in
the form of sequences of points of interest (POIs),
waypoints, etc. We refer to sets of such sequences as
route collections. In this work, we consider path queries
on frequently updated route
collections: given a route collection and two points ns
and nt, a path query returns a path, i.e., a sequence of
points, that connects ns to nt. We introduce two path
query evaluation paradigms that enjoy the benefits of
search algorithms (i.e., fast index maintenance) while
utilizing transitivity information to terminate the search
sooner. Efficient indexing
schemes and appropriate updating procedures are
introduced. An extensive experimental evaluation
verifies the advantages
of our methods compared to conventional graph-based
search.