Efficient query processing on spatial networks

TitleEfficient query processing on spatial networks
Publication TypeConference Papers
Year of Publication2005
AuthorsSankaranarayanan J, Alborzi H, Samet H
Conference NameProceedings of the 13th annual ACM international workshop on Geographic information systems
Date Published2005///
Conference LocationNew York, NY, USA
ISBN Number1-59593-146-5
Keywordslocation-based services, path coherence, Query processing, SILC framework, Spatial databases, spatial networks

A framework for determining the shortest path and the distance between every pair of vertices on a spatial network is presented. The framework, termed SILC, uses path coherence between the shortest path and the spatial positions of vertices on the spatial network, thereby, resulting in an encoding that is compact in representation and fast in path and distance retrievals. Using this framework, a wide variety of spatial queries such as incremental nearest neighbor searches and spatial distance joins can be shown to work on datasets of locations residing on a spatial network of sufficiently large size. The suggested framework is suitable for both main memory and disk-resident datasets.