Please wait a minute...
FITEE
Front. Inform. Technol. Electron. Eng.  2015, Vol. 16 Issue (2): 98-108    DOI: 10.1631/FITEE.1400165
    
不确定空间二维范围查询的Kd-树和四叉树分解
Ahmet Sayar, Süleyman Eken, Okan ?ztürk
Department of Computer Engineering, Kocaeli University, Kocaeli 41380, Turkey
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
 全文: PDF 
摘要： 目的：通过点数据二维范围查询性能测试评价空间划分方法（kd-树和四叉树）的可行性和有效性。
创新：基于不确定空间创建有效索引，将范围查询分解成多个等尺寸子范围求解。
方法：将数据集合定义为二维平面上的点，进行范围查询（窗口查询）。根据数据大小（相对大或相对小）及其分布（随机或偏斜）测试四种方案（图3-8）。相同的测试同时应用于真实数据（Turkey’s points of interest data，图9-11）。
结论：所提算法有助选取由索引表格创建的最佳划分组合，最小化给定查询响应时间。四叉树索引平行度更高，这很大程度上由于四叉树更清晰地揭示数据空间位置。
关键词： Kd-树;  四叉树;  空间划分;  空间索引;  范围查询;  查询优化    
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
收稿日期: 2014-05-05 出版日期: 2015-01-29
CLC:  TP391  
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
Ahmet Sayar
Süleyman Eken
Okan ?ztürk

引用本文:

Ahmet Sayar, Süleyman Eken, Okan ?ztürk. Kd-tree and quad-tree decompositions for declustering of 2D range queries over uncertain space. Front. Inform. Technol. Electron. Eng., 2015, 16(2): 98-108.

链接本文:

http://www.zjujournals.com/xueshu/fitee/CN/10.1631/FITEE.1400165    或    http://www.zjujournals.com/xueshu/fitee/CN/Y2015/V16/I2/98

[1] Gopi Ram , Durbadal Mandal , Sakti Prasad Ghoshal , Rajib Kar . 使用猫群算法优化线性天线阵列的最佳阵因子辐射方向图：电磁仿真验证[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(4): 570-577.
[2] Yuan-ping Nie, Yi Han, Jiu-ming Huang, Bo Jiao, Ai-ping Li. 基于注意机制编码解码模型的答案选择方法[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(4): 535-544.
[3] Lin-bo Qiao, Bo-feng Zhang, Jin-shu Su, Xi-cheng Lu. 结构化稀疏学习综述[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(4): 445-463.
[4] Rong-Feng Zhang , Ting Deng , Gui-Hong Wang , Jing-Lun Shi , Quan-Sheng Guan . 基于可靠特征点分配算法的鲁棒性跟踪框架[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(4): 545-558.
[5] Wen-yan Xiao, Ming-wen Wang, Zhen Weng, Li-lin Zhang, Jia-li Zuo. 基于语料库的小学英语认识率及教材选词策略研究[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(3): 362-372.
[6] . 一种基于描述逻辑的体系质量需求建模与验证方法[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(3): 346-361.
[7] Ali Darvish Falehi, Ali Mosallanejad. 使用基于多目标粒子群算法多层自适应模糊推理系统晶闸管控制串联电容器补偿技术的互联多源电力系统动态稳定性增强器[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(3): 394-409.
[8] Li Weigang. 用于评估共同作者学术贡献的第一和其他合作者信用分配模式[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(2): 180-194.
[9] Jun-hong Zhang, Yu Liu. 应用完备集合固有时间尺度分解和混合差分进化和粒子群算法优化的最小二乘支持向量机对柴油机进行故障诊断[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(2): 272-286.
[10] Hui Chen, Bao-gang Wei, Yi-ming Li, Yong-huai Liu, Wen-hao Zhu. 一种易用的实体识别消歧系统评测框架[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(2): 195-205.
[11] Yong-hong Tian, Xi-lin Chen, Hong-kai Xiong, Hong-liang Li, Li-rong Dai, Jing Chen, Jun-liang Xing, Jing Chen, Xi-hong Wu, Wei-min Hu, Yu Hu, Tie-jun Huang, Wen Gao. AI2.0时代的类人与超人感知：研究综述与趋势展望[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(1): 58-67.
[12] Yu-xin Peng, Wen-wu Zhu, Yao Zhao, Chang-sheng Xu, Qing-ming Huang, Han-qing Lu, Qing-hua Zheng, Tie-jun Huang, Wen Gao. 跨媒体分析与推理：研究进展与发展方向[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(1): 44-57.
[13] Yue-ting Zhuang, Fei Wu, Chun Chen, Yun-he Pan. 挑战与希望：AI2.0时代从大数据到知识[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(1): 3-14.
[14] Bo-hu Li, Hui-yang Qu, Ting-yu Lin, Bao-cun Hou, Xiang Zhai, Guo-qiang Shi, Jun-hua Zhou, Chao Ruan. 基于综合集成研讨厅的群体智能设计研究[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(1): 149-152.
[15] Le-kui Zhou, Si-liang Tang, Jun Xiao, Fei Wu, Yue-ting Zhuang. 基于众包标签数据深度学习的命名实体消歧算法[J]. Frontiers of Information Technology & Electronic Engineering, 2017, 18(1): 97-106.