23-04-2014, 02:30 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.
INTRODUCTION
SEVERAL applications involve storing and querying large
volumes of data sequences. For instance, the recent
advances in the infrastructure of Geographic Information
Systems (GIS) and geodata services, and the proliferation
of GPS technology, have resulted in the abundance of user
or machine generated geodata in the form of point of
interest (POI) sequences. We refer to sets of such sequences
as route collections.
As an example, consider people visiting Athens, having
GPS-enabled devices to track their sightseeing and create
routes through interesting places. Fig. 1 shows two routes in
Athens. The first, r1 , starts from the National Technical
University of Athens and ends at the new Museum of
Acropolis. The second, r2 , starts from the Omonia Square
and ends at the Acropolis Entrance. Websites such as
ShareMyRoutes.com and TravelByGPS.com maintain a
huge collection of routes, like the above, with POIs from
all over the world, that are frequently updated as users
continuously share new interesting routes.
ROUTE TRAVERSAL SEARCH
This section revisits our work from [1] for evaluating PATH
queries over route collections. Section 3.1 presents the
R-Index on route collections and details the RTS algorithm.
Section 3.2 outlines the RTST algorithm that additionally
exploits information about the transitions among routes
stored in the T -Index structure. Section 3.3 presents a
detailed complexity analysis.
The Link Traversal Search Paradigm
Although the algorithms of Section 3 perform fewer
iterations than conventional depth-first search on the route
collection graph GR , they share three shortcomings. First,
they perform redundant iterations by visiting nonlinks. To
understand this, consider that the current search node nq is
not a link and belongs to a single route ri . Further, assume
that the algorithm has visited n‘ , which is the link
immediately before nq . Observe that if the termination
condition does not hold at n‘ , then it neither holds at nq . To
make matters worse, retrieving routes1⁄2nq is pointless as it
contains a single route ri in which all nodes after nq are
already in the stack.
CONCLUSIONS
We consider the problem of evaluating path queries on large
disk-resident routes collections that are frequently updated.
We introduced two generic search-based paradigms, route
traversal search and link traversal search, that exploit local
transitivity information to expedite path query evaluation.