摘要
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） paraUelization 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.
研究目的:通过点数据二维范围查询性能测试评价空间划分方法(kd-树和四叉树)的可行性和有效性。创新要点:基于不确定空间创建有效索引,将范围查询分解成多个等尺寸子范围求解。研究方法:将数据集合定义为二维平面上的点,进行范围查询(窗口查询)。根据数据大小(相对大或相对小)及其分布(随机或偏斜)测试四种方案(图3-8)。相同的测试同时应用于真实数据(Turkey’s points of interest data,图9-11)。重要结论:所提算法有助选取由索引表格创建的最佳划分组合,最小化给定查询响应时间。四叉树索引平行度更高,这很大程度上由于四叉树更清晰地揭示数据空间位置。
