On Trip Planning Queries in Spatial Databases

Feifei Li, Dihan Cheng, Marios Hadjieleftheriou, George Kollios and Shang-Hua Teng

In Proceedings of the 9th International Symposium on Spatial and Temporal Databases (SSTD '05) Angra dos Reis, Brazil, August 2005.

Abstract

In this paper we discuss a new type of query in Spatial Databases, called the Trip Planning Query (TPQ). Given a set of points of interest P in space, where each point belongs to a specific category, a starting point S and a destination point E, TPQ retrieves the best trip that starts at S, passes through at least one point from each category, and ends at E. For example, a driver traveling from Boston to Providence might want to stop to a gas station, a bank and a post office on his way, and the goal is to provide him with the best possible route (in terms of distance, traffic, road conditions, etc.). The difficulty of this query lies in the existence of multiple choices per category. In this paper, we study fast approximation algorithms for TPQ in a metric space. We provide a number of approximation algorithms with approximation ratios that depend on either the number of categories, the maximum number of points per category or both. Therefore, for different instances of the problem, we can choose the algorithm with the best approximation ratio, since they all run in polynomial time. Furthermore, we use some of the proposed algorithms to derive efficient heuristics for large datasets stored in external memory. Finally, we give an experimental evaluation of the proposed algorithms using both synthetic and real datasets.

Papers and Talks

Paper:

Talk:

Dataset

All datasets are real and they were originally in different formats.
For the points of interest, we have the real dataset for the California road network. For the rest, we generated the points of interest using different distributions on the respective road networks.

1. California Road Network and Category Points
California Road Network's Nodes (Node ID, Longitude, Latitude)
California Road Network's Edges (Edge ID, Start Node ID, End Node ID, L2 Distance)
California's Points of Interest With Original Category Name (Category Name, Longitude, Latitude)
California's Points of Interest (Longitude, Latitude, Category ID)
Merge Points of Interest with Road Network--Map Format
Map Format in Detail:
For each edge:
Start Node ID, End Node ID, Edge Length, Number of Points on This Edge
    For each point on this edge:
    Category ID, Distance of This Point to the Start Node of This Edge

Note: A. The road network is obtained from: Digital Chart of the World Server (http://www.maproom.psu.edu/dcw/)
           B. The category points are obtained from: U.S. Geological Survey (http://www.usgs.gov/)