Two-Layer Space-Oriented Partitioning for Non-Point Data
- 24 July 2023
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Knowledge and Data Engineering
- Vol. 36 (3) , 1341-1355
Abstract
Non-point spatial objects (e.g., polygons, linestrings, etc.) are ubiquitous. We study the problem of indexing non-point objects in memory for range queries and spatial intersection joins. We propose a secondary partitioning technique for space-oriented partitioning indices (e.g., grids), which improves their performance significantly, by avoiding the generation and elimination of duplicate results. Our approach is easy to implement and can be used by any space-partitioning index to significantly reduce the cost of range queries and intersection joins. In addition, the secondary partitions can be processed independently, which makes our method appropriate for distributed and parallel indexing. Experiments on real datasets confirm the advantage of our approach against alternative duplicate elimination techniques and data-oriented state-of-the-art spatial indices. We also show that our partitioning technique, paired with optimized partition-to-partition join algorithms, typically reduces the cost of spatial joins by around 50%.Keywords
All Related Versions
This publication has 45 references indexed in Scilit:
- Spatial data management in apache spark: the GeoSpark perspective and beyondGeoInformatica, 2018
- A crowd enabled approach for processing nearest neighbor and range queries in incomplete databases with accuracy guaranteePervasive and Mobile Computing, 2017
- Configuring Spatial Grids for Efficient Main Memory Joins2015
- Experiences on Processing Spatial Data with MapReduce2009
- Main Memory Evaluation of Monitoring Queries Over Moving ObjectsDistributed and Parallel Databases, 2004
- STR: a simple and efficient algorithm for R-tree packing2002
- Data redundancy and duplicate detection in spatial join processing2002
- Computational Geometry1985
- The Quad-CIF Tree: A Data Structure for Hierarchical On-Line Algorithms1982
- Quad trees a data structure for retrieval on composite keysActa Informatica, 1974