Polygon-Based Query Evaluation over Geospatial Data Using Distributed Hash Tables
Authors:
- Matthew MalensekMMMatthew Malensek
- Sangmi PallickaraSPSangmi Pallickara
- Shrideep PallickaraSPShrideep Pallickara
- 1 December 2013
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 219-226
Abstract
Data volumes in the geosciences and related domains have grown significantly as sensing equipment designed to continuously gather readings and produce data streams for geographic regions have proliferated. The storage requirements imposed by these datasets vastly outstrip the capabilities of a single computing resource, leading to the use and development of distributed storage frameworks composed of commodity hardware. In this paper, we explore the challenges associated with supporting geospatial retrievals constrained by arbitrary polygonal bounds on a distributed hash table architecture. Our solution involves novel distribution and partitioning of these voluminous datasets, thus enabling the use of a lightweight, distributed spatial indexing structure, the geoavailability grid. Geoavailability grids provide global, coarse-grained representations of the spatial information stored within these ever-expanding datasets, allowing the search space of distributed queries to be reduced by eliminating storage resources that do not hold relevant information. This results in improved response times and more effective utilization of available resources. Geoavailability grids are also applicable in non-distributed settings for local lookup functionality, performing competitively with other leading spatial indexing technology.Keywords
This publication has 13 references indexed in Scilit:
- Autonomously improving query evaluations over multidimensional data in distributed hash tables2013
- Expressive Query Support for Multidimensional Data in Distributed Hash Tables2012
- Concise: Compressed ‘n’ Composable Integer SetInformation Processing Letters, 2010
- CassandraACM SIGOPS Operating Systems Review, 2010
- Sorting improves word-aligned bitmap indexesData & Knowledge Engineering, 2010
- A spatial bitmap-based index for geographical data warehouses2009
- SD-Rtree: A Scalable Distributed Rtree2007
- Bitmap index design and evaluationACM SIGMOD Record, 1998
- R-trees1984
- Quad trees a data structure for retrieval on composite keysActa Informatica, 1974