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

被引：12

作者：

Sayar, Ahmet ^{[1
]}

Eken, Suleyman ^{[1
]}

Ozturk, Okan ^{[1
]}

机构：

[1] Kocaeli Univ, Dept Comp Engn, TR-41380 Kocaeli, Turkey

来源：

FRONTIERS OF INFORMATION TECHNOLOGY & ELECTRONIC ENGINEERING | 2015年 / 16卷 / 02期

关键词：

Kd tree; Quad tree; Space partitioning; Spatial indexing; Range queries; Query optimization; SPATIAL DATA; PARALLEL; SYSTEMS;

D O I：

10.1631/FITEE.1400165

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

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.

引用

页码：98 / 108

页数：11

共 20 条

[1]

[Anonymous], 2009, GEOSTATISTICS MODELI

[2] MULTIDIMENSIONAL BINARY SEARCH TREES USED FOR ASSOCIATIVE SEARCHING [J].