|
|
|
| Kd-tree and quad-tree decompositions for declustering of 2D range queries over uncertain space |
| Ahmet Sayar, Süleyman Eken, Okan ?ztürk |
| Department of Computer Engineering, Kocaeli University, Kocaeli 41380, Turkey |
|
|
|
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.
|
|
Received: 05 May 2014
Published: 29 January 2015
|
|
|
不确定空间二维范围查询的Kd-树和四叉树分解
目的：通过点数据二维范围查询性能测试评价空间划分方法（kd-树和四叉树）的可行性和有效性。
创新：基于不确定空间创建有效索引，将范围查询分解成多个等尺寸子范围求解。
方法：将数据集合定义为二维平面上的点，进行范围查询（窗口查询）。根据数据大小（相对大或相对小）及其分布（随机或偏斜）测试四种方案（图3-8）。相同的测试同时应用于真实数据（Turkey’s points of interest data，图9-11）。
结论：所提算法有助选取由索引表格创建的最佳划分组合，最小化给定查询响应时间。四叉树索引平行度更高，这很大程度上由于四叉树更清晰地揭示数据空间位置。
关键词：
Kd-树,
四叉树,
空间划分,
空间索引,
范围查询,
查询优化
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
