NDLI: Distance Oracles for Spatial Networks

Content Provider	IEEE Xplore Digital Library
Author	Sankaranarayanan, J. Samet, H.
Copyright Year	2009
Abstract	The popularity of location-based services and the need to do real-time processing on them has led to an interest in performing queries on transportation networks, such as finding shortest paths and finding nearest neighbors. The challenge is that these operations involve the computation of distance along a spatial network rather than "as the crow flies." In many applications an estimate of the distance is sufficient, which can be achieved by use of an oracle. An approximate distance oracle is proposed for spatial networks that exploits the coherence between the spatial position of vertices and the network distance between them. Using this observation, a distance oracle is introduced that is able to obtain the epsilon-approximate network distance between two vertices of the spatial network. The network distance between every pair of vertices in the spatial network is efficiently represented by adapting the well-separated pair technique to spatial networks. Initially, use is made of an epsilon-approximate distance oracle of size O( n / epsilon^d ) that is capable of retrieving the approximate network distance in O(logn) time using a B-tree. The retrieval time can be theoretically reduced further to O(1) time by proposing another e-approximate distance oracle of size O(n log n / epsilon^d) that uses a hash table. Experimental results indicate that the proposed technique is scalable and can be applied to sufficiently large road networks. A 10%-approximate oracle (epsilon = 0.1) on a large network yielded an average error of 0.9% with 90% of the answers making an error of 2% or less and an average retrieval timeof 68µ seconds. Finally, a strategy for the integration of the distance oracle into any relational database system as well as using it to perform a variety of spatial queries such as region search, k-nearest neighbor search, and spatial joins on spatial networks is discussed.
Starting Page	652
Ending Page	663
File Size	624537
Page Count	12
File Format	PDF
ISBN	9781424434220
ISSN	10844627
DOI	10.1109/ICDE.2009.53
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2009-03-29
Publisher Place	China
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Computer networks Spatial coherence Data engineering Automation Computer science Educational institutions Transportation Nearest neighbor searches Roads Relational databases relational databases distance oracles spatial networks road networks network distance nearest neighbors distance joins
Content Type	Text
Resource Type	Article
Subject	Signal Processing Information Systems Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Enabling Query Processing on Spatial Networks

Query Processing Using Distance Oracles for Spatial Networks

Moving Continuous K Nearest Neighbor Queries in Spatial Network Databases

Efficient Evaluation of k-Range Nearest Neighbor Queries in Road Networks

Intelligent Path Finder for Goal Directed Queries in Spatial Networks

An Efficient Technique for Continuous K-Nearest Neighbor Query Processing on Moving Objects in a Road Network

All-nearest-neighbors queries in spatial databases

Materialization-based query processing algorithms on road networks

Reverse Furthest Neighbors in Spatial Databases

Distance Oracles for Spatial Networks

Similar Documents

Enabling Query Processing on Spatial Networks

Query Processing Using Distance Oracles for Spatial Networks

Moving Continuous K Nearest Neighbor Queries in Spatial Network Databases

Efficient Evaluation of k-Range Nearest Neighbor Queries in Road Networks

Intelligent Path Finder for Goal Directed Queries in Spatial Networks

An Efficient Technique for Continuous K-Nearest Neighbor Query Processing on Moving Objects in a Road Network

All-nearest-neighbors queries in spatial databases

Materialization-based query processing algorithms on road networks

Reverse Furthest Neighbors in Spatial Databases

Distance Oracles for Spatial Networks