{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,30]],"date-time":"2025-09-30T04:09:25Z","timestamp":1759205365944},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"12","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2015,8]]},"abstract":"<jats:p>\n            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\n            <jats:italic>compressed spatial hierarchical bitmap (cSHB)<\/jats:italic>\n            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\n            <jats:italic>bitmap selection<\/jats:italic>\n            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\n            <jats:italic>compressed spatial hierarchical bitmap (cSHB)<\/jats:italic>\n            index structure and the range query planning algorithms in supporting spatial range query workloads.\n          <\/jats:p>","DOI":"10.14778\/2824032.2824038","type":"journal-article","created":{"date-parts":[[2015,9,16]],"date-time":"2015-09-16T12:18:17Z","timestamp":1442405897000},"page":"1382-1393","source":"Crossref","is-referenced-by-count":12,"title":["Compressed spatial hierarchical bitmap (cSHB) indexes for efficiently processing spatial range query workloads"],"prefix":"10.14778","volume":"8","author":[{"given":"Parth","family":"Nagarkar","sequence":"first","affiliation":[{"name":"Arizona State University, Tempe, AZ"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"K. Sel\u00e7uk","family":"Candan","sequence":"additional","affiliation":[{"name":"Arizona State University, Tempe, AZ"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aneesha","family":"Bhat","sequence":"additional","affiliation":[{"name":"Arizona State University, Tempe, AZ"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,8]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Apache Lucene. http:\/\/lucene.apache.org\/core\/4_6_0\/spatial\/org\/apache\/lucene\/spatial\/prefix\/tree\/SpatialPrefixTree.html  Apache Lucene. http:\/\/lucene.apache.org\/core\/4_6_0\/spatial\/org\/apache\/lucene\/spatial\/prefix\/tree\/SpatialPrefixTree.html"},{"key":"e_1_2_1_2_1","unstructured":"Using PostGIS: Data Management and Queries. http:\/\/postgis.net\/docs\/using_postgis_dbmanagement.html  Using PostGIS: Data Management and Queries. http:\/\/postgis.net\/docs\/using_postgis_dbmanagement.html"},{"key":"e_1_2_1_3_1","unstructured":"OpenStreetMap. http:\/\/www.openstreetmap.org\/  OpenStreetMap. http:\/\/www.openstreetmap.org\/"},{"key":"e_1_2_1_4_1","unstructured":"J. Leskovec and A. Krevl. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data  J. Leskovec and A. Krevl. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data"},{"key":"e_1_2_1_5_1","volume-title":"SIGMOD","author":"Abadi D.","year":"2006"},{"key":"e_1_2_1_6_1","volume-title":"PVLDB","author":"Aji A.","year":"2013"},{"key":"e_1_2_1_7_1","volume-title":"WWCA","year":"1997"},{"key":"e_1_2_1_8_1","volume-title":"SIGMOD","author":"Beckmann N.","year":"1990"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/279339.279342"},{"key":"e_1_2_1_10_1","volume-title":"Supporting Efficient Implementations of Advanced Database Queries. VLDB","author":"Bercken J.","year":"2001"},{"key":"e_1_2_1_11_1","volume-title":"TOC 1971","author":"Butz A. R.","year":"1971"},{"key":"e_1_2_1_12_1","volume-title":"Experiences on Processing Spatial Data with MapReduce. SSDBM","author":"Cary A.","year":"2009"},{"key":"e_1_2_1_13_1","volume-title":"DOLAP 2010","author":"Chmiel J.","year":"1871"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2513591.2513656"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","DOI":"10.1145\/1739041.1739071","volume-title":"Position List Word Aligned Hybrid: Optimizing Space and Performance for Compressed Bitmaps. EDBT","author":"Deli\u00e8ge F.","year":"2010"},{"key":"e_1_2_1_16_1","volume-title":"SSDM 2006","author":"Gosink L.","year":"2006"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"David Hilbert. Ueber stetige abbildung einer linie auf ein flachenstuck. Mathematische Annalen 1891.  David Hilbert. Ueber stetige abbildung einer linie auf ein flachenstuck. Mathematische Annalen 1891.","DOI":"10.1007\/BF01199431"},{"key":"e_1_2_1_18_1","volume-title":"An Empirical Study on Performance Comparison of Lucene and Relational Database. ICCSN 2009","author":"Jing Y.","year":"2009"},{"key":"e_1_2_1_19_1","unstructured":"I. Kamel and C. Faloutsos. Hilbert R-tree: An Improved R-tree using Fractals. VLDB 1994   I. Kamel and C. Faloutsos. Hilbert R-tree: An Improved R-tree using Fractals. VLDB 1994"},{"key":"e_1_2_1_20_1","volume-title":"Histogram-Aware Sorting for Enhanced Word-Aligned Compression in Bitmap Indexes. DOLAP","author":"Kaser O.","year":"2008"},{"key":"e_1_2_1_21_1","volume-title":"DKE 2010","author":"Lemire D.","year":"2009"},{"key":"e_1_2_1_22_1","volume-title":"IDEAS","author":"Markl V.","year":"1999"},{"key":"e_1_2_1_23_1","volume-title":"IBM","author":"Morton G.","year":"1966"},{"key":"e_1_2_1_24_1","volume-title":"Scalable Indexing Technique for Set-Valued Attributes. ADBIS","author":"Morzy M.","year":"2003"},{"key":"e_1_2_1_25_1","volume-title":"EDBT","author":"Nagarkar P.","year":"2014"},{"key":"e_1_2_1_26_1","unstructured":"M. A. Olma etal BLOCK: Efficient Execution of Spatial Range Queries in Main-Memory. Technical report EPFL 2013.  M. A. Olma et al. BLOCK: Efficient Execution of Spatial Range Queries in Main-Memory. Technical report EPFL 2013."},{"key":"e_1_2_1_27_1","volume-title":"Multiple Range Query Optimization in Spatial Databases. ADBIS","author":"Papadopoulos A. N.","year":"1998"},{"key":"e_1_2_1_28_1","unstructured":"H. Samet. Foundations of Multidimensional and Metric Data Structures 2005.   H. Samet. Foundations of Multidimensional and Metric Data Structures 2005."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272743.1272746"},{"key":"e_1_2_1_30_1","unstructured":"T. Siqueira etal The SB-index and the HSB-index: Efficient Indices for Spatial Data Warehouses. Geoinformatica 2012. 10.1007\/s10707-011-0128-5   T. Siqueira et al. The SB-index and the HSB-index: Efficient Indices for Spatial Data Warehouses. Geoinformatica 2012. 10.1007\/s10707-011-0128-5"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2004.12.001"},{"key":"e_1_2_1_32_1","volume-title":"On the Performance of Bitmap Indices for High Cardinality Attributes. VLDB","author":"Wu K.","year":"2004"},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","DOI":"10.2172\/841308","volume-title":"An Efficient Compression Scheme for Bitmap Indices. TODS","author":"Wu K.","year":"2004"},{"key":"e_1_2_1_34_1","volume-title":"IJCC","author":"Zaker M.","year":"2008"},{"key":"e_1_2_1_35_1","volume-title":"Towards Parallel Spatial Query Processing for Big Spatial Data. IPDPSW 2012","author":"Zhong Y.","year":"2012"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2824032.2824038","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:19:53Z","timestamp":1672222793000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2824032.2824038"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,8]]},"references-count":35,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2015,8]]}},"alternative-id":["10.14778\/2824032.2824038"],"URL":"https:\/\/doi.org\/10.14778\/2824032.2824038","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2015,8]]}}}