Optimal location queries in road network databases
Authors:
- 1 April 2011
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10636382,p. 804-815
Abstract
Optimal location (OL) queries are a type of spatial queries particularly useful for the strategic planning of resources. Given a set of existing facilities and a set of clients, an OL query asks for a location to build a new facility that optimizes a certain cost metric (defined based on the distances between the clients and the facilities). Several techniques have been proposed to address OL queries, assuming that all clients and facilities reside in an Lp space. In practice, however, movements between spatial locations are usually confined by the underlying road network, and hence, the actual distance between two locations can differ significantly from their Lp distance. Motivated by the deficiency of the existing techniques, this paper presents the first study on OL queries in road networks. We propose a unified framework that addresses three variants of OL queries that find important applications in practice, and we instantiate the framework with several novel query processing algorithms. We demonstrate the efficiency of our solutions through extensive experiments with real data.Keywords
This publication has 19 references indexed in Scilit:
- Path oracles for spatial networksProceedings of the VLDB Endowment, 2009
- Efficient method for maximizing bichromatic reverse nearest neighborProceedings of the VLDB Endowment, 2009
- Instance optimal query processing in spatial networksThe VLDB Journal, 2008
- Incremental algorithms for Facility Location and k-MedianTheoretical Computer Science, 2006
- The Optimal-Location Query2005
- Voronoi-Based K Nearest Neighbor Search for Spatial Network Databases2004
- Query Processing in Spatial Network Databases2003
- CCAM: a connectivity-clustered access method for networks and network computationsIEEE Transactions on Knowledge and Data Engineering, 1997
- Finding the upper envelope of n line segments in O(n log n) timeInformation Processing Letters, 1989
- A note on two problems in connexion with graphsNumerische Mathematik, 1959