Kd-tree and quad-tree decompositions for declustering of 2D range queries over uncertain space

2015, Volume 16, Issue 2

Abstract

Keywords

Related Research

Frontiers of Information Technology & Electronic Engineering >> 2015, Volume 16, Issue 2 doi: 10.1631/FITEE.1400165

Kd-tree and quad-tree decompositions for declustering of 2D range queries over uncertain space

Department of Computer Engineering, Kocaeli University, Kocaeli 41380, Turkey

Available online: 2015-03-05

HTML27 PDF 7 Collect 0

Next Previous

Abstract

We present a study to show the possibility of using two well-known space partitioning and indexing techniques, kd trees and quad trees, in declustering applications to increase input/output (I/O) parallelization and reduce spatial data processing times. This parallelization enables time-consuming computational geometry algorithms to be applied efficiently to big spatial data rendering and querying. The key challenge is how to balance the spatial processing load across a large number of worker nodes, given significant performance heterogeneity in nodes and processing skews in the workload.

Keywords

Kd tree ; Quad tree ; Space partitioning ; Spatial indexing ; Range queries ; Query optimization

Related Research