|
|
Frontiers of Information Technology & Electronic Engineering
ISSN 2095-9184 (print), ISSN 2095-9230 (online)
2015 Vol.16 No.2 P.98-108
Kd-tree and quad-tree decompositions for declustering of 2D range queries over uncertain space
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.
Key words: Kd tree, Quad tree, Space partitioning, Spatial indexing, Range queries, Query optimization
创新：基于不确定空间创建有效索引，将范围查询分解成多个等尺寸子范围求解。
方法：将数据集合定义为二维平面上的点，进行范围查询（窗口查询）。根据数据大小（相对大或相对小）及其分布（随机或偏斜）测试四种方案（图3-8）。相同的测试同时应用于真实数据（Turkey’s points of interest data，图9-11）。
结论：所提算法有助选取由索引表格创建的最佳划分组合，最小化给定查询响应时间。四叉树索引平行度更高，这很大程度上由于四叉树更清晰地揭示数据空间位置。
关键词组：
References:
Open peer comments: Debate/Discuss/Question/Opinion
<1>
DOI:
10.1631/FITEE.1400165
CLC number:
TP391
Download Full Text:
Downloaded:
2759
Download summary:
<Click Here>Downloaded:
1685Clicked:
6436
Cited:
4
On-line Access:
2015-01-29
Received:
2014-05-05
Revision Accepted:
2014-10-11
Crosschecked:
2015-01-05