Title: On trip planning queries in spatial databases
Author: Feifei Li, Dihan Cheng
Date: July 1, 2004
Abstract:
In this paper we discuss a new type of query in Spatial
Databases, called Trip Planning Query (TPQ). Given a set
of points P in space, where each point belongs to a category,
and given two points s and e, TPQ asks for the best trip that
starts at s, passes through exactly one point from each category,
and ends at e. An example of a TPQ is when a user
wants to visit a set of different places and at the same time
minimize the total travelling cost, e.g. what is the shortest
travelling plan for me to visit an automobile shop, a CVS
pharmacy outlet, and a Best Buy shop along my trip from A to
B? The trip planning query is an extension of the well-known
TSP problem and therefore is NP-hard. The difficulty of this
query lies in the existence of multiple choices for each category.
In this paper, we first study fast approximation algorithms
for the trip planning query in a metric space, assuming
that the data set fits in main memory, and give the theory
analysis of their approximation bounds. Then, the trip planning
query is examined for data sets that do not fit in main
memory and must be stored on disk. For the disk-resident
data, we consider two cases. In one case, we assume that the
points are located in Euclidean space and indexed with an Rtree.
In the other case, we consider the problem of points that
lie on the edges of a spatial network (e.g. road network) and
the distance between two points is defined using the shortest
distance over the network. Finally, we give an experimental
evaluation of the proposed algorithms using synthetic data
sets generated on real road networks.