New lower and upper bounds for shortest distance queries on terrains

Kaul, Manohar and Wong, Raymond Chi-Wing and Jensen, Christian S (2015) New lower and upper bounds for shortest distance queries on terrains. In: Proceedings of Very Large Databases (PVLDB), 2015.

Full text not available from this repository. (Request a copy)


The increasing availability of massive and accurate laser data enables the processing of spatial queries on terrains. As shortest-path computation, an integral element of query processing, is inherently expensive on terrains, a key approach to enabling efficient query processing is to reduce the need for exact shortest-path computation in query processing. We develop new lower and upper bounds on terrain shortest distances that are provably tighter than any existing bounds. Unlike existing bounds, the new bounds do not rely on the quality of the triangulation. We show how use of the new bounds speeds up query processing by reducing the need for exact distance computations. Speedups of of nearly an order of magnitude are demonstrated empirically for well-known spatial queries.

[error in script]
IITH Creators:
IITH CreatorsORCiD
Item Type: Conference or Workshop Item (Paper)
Subjects: Computer science
Divisions: Department of Computer Science & Engineering
Depositing User: Team Library
Date Deposited: 19 Jun 2019 10:55
Last Modified: 19 Jun 2019 10:55
Publisher URL:
Related URLs:

Actions (login required)

View Item View Item
Statistics for RAIITH ePrint 5515 Statistics for this ePrint Item