research-article

Compressed spatial hierarchical bitmap (cSHB) indexes for efficiently processing spatial range query workloads

Editors: Chen Li, Volker Markl Authors:

Parth Nagarkar,

K. Selçuk Candan,

Aneesha BhatAuthors Info & Claims

Proceedings of the VLDB Endowment, Volume 8, Issue 12

Pages 1382 - 1393

https://doi.org/10.14778/2824032.2824038

Published: 01 August 2015 Publication History

Abstract

In most spatial data management applications, objects are represented in terms of their coordinates in a 2-dimensional space and search queries in this space are processed using spatial index structures. On the other hand, bitmap-based indexing, especially thanks to the compression opportunities bitmaps provide, has been shown to be highly effective for query processing workloads including selection and aggregation operations. In this paper, we show that bitmap-based indexing can also be highly effective for managing spatial data sets. More specifically, we propose a novel compressed spatial hierarchical bitmap (cSHB) index structure to support spatial range queries. We consider query workloads involving multiple range queries over spatial data and introduce and consider the problem of bitmap selection for identifying the appropriate subset of the bitmap files for processing the given spatial range query workload. We develop cost models for compressed domain range query processing and present query planning algorithms that not only select index nodes for query processing, but also associate appropriate bitwise logical operations to identify the data objects satisfying the range queries in the given workload. Experiment results confirm the efficiency and effectiveness of the proposed compressed spatial hierarchical bitmap (cSHB) index structure and the range query planning algorithms in supporting spatial range query workloads.

References

[1]

Apache Lucene. http://lucene.apache.org/core/4_6_0/spatial/org/apache/lucene/spatial/prefix/tree/SpatialPrefixTree.html

[2]

Using PostGIS: Data Management and Queries. http://postgis.net/docs/using_postgis_dbmanagement.html

[3]

OpenStreetMap. http://www.openstreetmap.org/

[4]

J. Leskovec and A. Krevl. SNAP Datasets: Stanford Large Network Dataset Collection. http://snap.stanford.edu/data

[5]

D. Abadi et al. Compression and Execution in Column-Oriented Database systems. SIGMOD 2006.

[6]

A. Aji et al. Hadoop-GIS: A High Performance Spatial Data Warehousing System over MapReduce. PVLDB 2013.

[7]

Rudolf Bayer. The Universal B-tree for Multidimensional Indexing: General concepts. WWCA 1997.

[8]

N. Beckmann et al. The R*-tree: An Efficient and Robust Access Method for Points and Rectangles. SIGMOD 1990.

[9]

A. Belussi and C. Faloutsos. Self-Spatial Join Selectivity Estimation Using Fractal Concepts. TOIS 1998.

[10]

J. Bercken et al. XXL - A Library Approach to Supporting Efficient Implementations of Advanced Database Queries. VLDB 2001.

[11]

A. R. Butz. Alternative Algorithm for Hilbert's Space-Filling Curve. TOC 1971.

[12]

A. Cary et al. Experiences on Processing Spatial Data with MapReduce. SSDBM 2009.

[13]

J. Chmiel et al. Dimension Hierarchies by means of Hierarchically Organized Bitmaps. DOLAP 2010.

[14]

P. Chovanec and M. Krátký. On the Efficiency of Multiple Range Query Processing in Multidimensional Data Structures. IDEAS 2013.

[15]

F. Deliège and T. Pedersen. Position List Word Aligned Hybrid: Optimizing Space and Performance for Compressed Bitmaps. EDBT 2010.

[16]

L. Gosink et al. HDF5-FastQuery: Accelerating Complex Queries on HDF Datasets using Fast Bitmap Indices. SSDM 2006.

[17]

David Hilbert. Ueber stetige abbildung einer linie auf ein flachenstuck. Mathematische Annalen 1891.

[18]

Y. Jing et al. An Empirical Study on Performance Comparison of Lucene and Relational Database. ICCSN 2009.

[19]

I. Kamel and C. Faloutsos. Hilbert R-tree: An Improved R-tree using Fractals. VLDB 1994

[20]

O. Kaser et al. Histogram-Aware Sorting for Enhanced Word-Aligned Compression in Bitmap Indexes. DOLAP 2008.

[21]

D. Lemire et al. Sorting improves Word-Aligned Bitmap Indexes. DKE 2010.

[22]

V. Markl et al. Improving OLAP Performance by Multidimensional Hierarchical Clustering. IDEAS 1999.

[23]

G. Morton. A Computer Oriented Geodetic Data Base and a New Technique in File Sequencing. IBM 1966.

[24]

M. Morzy et al. Scalable Indexing Technique for Set-Valued Attributes. ADBIS 2003.

[25]

P. Nagarkar and K. S. Candan. HCS: Hierarchical Cut Selection for Efficiently Processing Queries on Data Columns using Hierarchical Bitmap Indices. EDBT 2014.

[26]

M. A. Olma et al. BLOCK: Efficient Execution of Spatial Range Queries in Main-Memory. Technical report EPFL 2013.

[27]

A. N. Papadopoulos and Y. Manolopoulos. Multiple Range Query Optimization in Spatial Databases. ADBIS 1998.

[28]

H. Samet. Foundations of Multidimensional and Metric Data Structures, 2005.

[29]

R. Sinha and M. Winslett. Multi-Resolution Bitmap Indexes for Scientific Data. TODS 2007.

[30]

T. Siqueira et al. The SB-index and the HSB-index: Efficient Indices for Spatial Data Warehouses. Geoinformatica 2012.

[31]

T. Skopal et al. Algorithm for Universal B-trees. Inf. Syst. 2006.

[32]

K. Wu et al. On the Performance of Bitmap Indices for High Cardinality Attributes. VLDB 2004.

[33]

K. Wu et al. An Efficient Compression Scheme for Bitmap Indices. TODS 2004.

[34]

M. Zaker et al. An Adequate Design for Large Data Warehouse Systems: Bitmap Index versus B-tree Index. IJCC 2008.

[35]

Y. Zhong et al. Towards Parallel Spatial Query Processing for Big Spatial Data. IPDPSW 2012.

Cited By

Han SLiu XLi J(2022)Chunk-oriented dimension ordering for efficient range query processing on sparse multidimensional dataWorld Wide Web10.1007/s11280-022-01098-z26:4(1395-1433)Online publication date: 9-Sep-2022
https://dl.acm.org/doi/10.1007/s11280-022-01098-z
Krčál LHo SHolub J(2022)Hierarchical Bitmap Indexing for Range Queries on Multidimensional ArraysDatabase Systems for Advanced Applications10.1007/978-3-031-00123-9_40(509-525)Online publication date: 11-Apr-2022
https://dl.acm.org/doi/10.1007/978-3-031-00123-9_40
Nelson MSorenson ZMyre JSawin JChiu D(2020)Parallel acceleration of CPU and GPU range queries over large data setsJournal of Cloud Computing: Advances, Systems and Applications10.1186/s13677-020-00191-w9:1Online publication date: 5-Aug-2020
https://dl.acm.org/doi/10.1186/s13677-020-00191-w
Show More Cited By

Compressed spatial hierarchical bitmap (cSHB) indexes for efficiently processing spatial range query workloads
1. Information systems
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory

Recommendations

Efficient joins with compressed bitmap indexes
CIKM '09: Proceedings of the 18th ACM conference on Information and knowledge management

We present a new class of adaptive algorithms that use compressed bitmap indexes to speed up evaluation of the range join query in relational databases. We determine the best strategy to process a join query based on a fast sub-linear time computation ...
Compressed Hierarchical Bitmaps for Efficiently Processing Different Query Workloads
IC2E '15: Proceedings of the 2015 IEEE International Conference on Cloud Engineering

Today the amount of data that is being processed is growing manyfold. Fast and scalable data processing systems are the need of the hour because of the data deluge. Indexing is a very common mechanism used in data processing systems for fast and ...
Inverted indexes vs. bitmap indexes in decision support systems
CIKM '09: Proceedings of the 18th ACM conference on Information and knowledge management

Bitmap indexes are widely used in Decision Support Systems (DSSs) to improve query performance. In this paper, we evaluate the use of compressed inverted indexes with adapted query processing strategies from Information Retrieval as an alternative. In a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the VLDB Endowment

Proceedings of the VLDB Endowment Volume 8, Issue 12

Proceedings of the 41st International Conference on Very Large Data Bases, Kohala Coast, Hawaii

August 2015

728 pages

ISSN:2150-8097

Editors:
Chen Li
University of California, Irvine
,
Volker Markl
TU Berlin

Issue’s Table of Contents

Publisher

VLDB Endowment

Publication History

Published: 01 August 2015

Published in PVLDB Volume 8, Issue 12

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
163
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)0

Reflects downloads up to 26 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Han SLiu XLi J(2022)Chunk-oriented dimension ordering for efficient range query processing on sparse multidimensional dataWorld Wide Web10.1007/s11280-022-01098-z26:4(1395-1433)Online publication date: 9-Sep-2022
https://dl.acm.org/doi/10.1007/s11280-022-01098-z
Krčál LHo SHolub J(2022)Hierarchical Bitmap Indexing for Range Queries on Multidimensional ArraysDatabase Systems for Advanced Applications10.1007/978-3-031-00123-9_40(509-525)Online publication date: 11-Apr-2022
https://dl.acm.org/doi/10.1007/978-3-031-00123-9_40
Nelson MSorenson ZMyre JSawin JChiu D(2020)Parallel acceleration of CPU and GPU range queries over large data setsJournal of Cloud Computing: Advances, Systems and Applications10.1186/s13677-020-00191-w9:1Online publication date: 5-Aug-2020
https://dl.acm.org/doi/10.1186/s13677-020-00191-w
Kimata HXiaojun WTanida R(2020)Hierarchical and Compact Bitmap Based Data Structure of Human Dynamics Data for VisualizationProceedings of the 4th International Conference on Graphics and Signal Processing10.1145/3406971.3406980(98-102)Online publication date: 26-Jun-2020
https://dl.acm.org/doi/10.1145/3406971.3406980
Jafari OOssorgin JNagarkar PEl Saddik ADel Bimbo AZhang ZHauptmann ACandan KBertini MXie LWei X(2019)qwLSHProceedings of the 2019 on International Conference on Multimedia Retrieval10.1145/3323873.3325048(329-333)Online publication date: 5-Jun-2019
https://dl.acm.org/doi/10.1145/3323873.3325048
Park K(2019)A hierarchical binary quadtree index for spatial queriesWireless Networks10.1007/s11276-018-1661-z25:4(1913-1929)Online publication date: 1-May-2019
https://dl.acm.org/doi/10.1007/s11276-018-1661-z
Lemire DSsi-Yan-Kai GKaser O(2016)Consistently faster and smaller compressed bitmaps with RoaringSoftware—Practice & Experience10.1002/spe.240246:11(1547-1569)Online publication date: 1-Nov-2016
https://dl.acm.org/doi/10.1002/spe.2402

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents