Please wait a minute...
FITEE
Front. Inform. Technol. Electron. Eng.  2015, Vol. 16 Issue (2): 98-108    DOI: 10.1631/FITEE.1400165
    
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
Download:   PDF(0KB)
Export: BibTeX | EndNote (RIS)      

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     
Received: 05 May 2014      Published: 29 January 2015
CLC:  TP391  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Ahmet Sayar
Süleyman Eken
Okan ?ztürk
Cite this article:

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.

URL:

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


不确定空间二维范围查询的Kd-树和四叉树分解

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

关键词： Kd-树,  四叉树,  空间划分,  空间索引,  范围查询,  查询优化 
[1] Gopi Ram , Durbadal Mandal , Sakti Prasad Ghoshal , Rajib Kar . Optimal array factor radiation pattern synthesis for linear antenna array using cat swarm optimization: validation by an electromagnetic simulator[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(4): 570-577.
[2] Lin-bo Qiao, Bo-feng Zhang, Jin-shu Su, Xi-cheng Lu. A systematic review of structured sparse learning[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(4): 445-463.
[3] Yuan-ping Nie, Yi Han, Jiu-ming Huang, Bo Jiao, Ai-ping Li. Attention-based encoder-decoder model for answer selection in question answering[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(4): 535-544.
[4] Rong-Feng Zhang , Ting Deng , Gui-Hong Wang , Jing-Lun Shi , Quan-Sheng Guan . A robust object tracking framework based on a reliable point assignment algorithm[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(4): 545-558.
[5] Wen-yan Xiao, Ming-wen Wang, Zhen Weng, Li-lin Zhang, Jia-li Zuo. Corpus-based research on English word recognition rates in primary school and word selection strategy[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(3): 362-372.
[6] . A quality requirements model and verification approach for system of systems based on description logic[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(3): 346-361.
[7] Ali Darvish Falehi, Ali Mosallanejad. Dynamic stability enhancement of interconnected multi-source power systems using hierarchical ANFIS controller-TCSC based on multi-objective PSO[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(3): 394-409.
[8] Jun-hong Zhang, Yu Liu. Application of complete ensemble intrinsic time-scale decomposition and least-square SVM optimized using hybrid DE and PSO to fault diagnosis of diesel engines[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(2): 272-286.
[9] Hui Chen, Bao-gang Wei, Yi-ming Li, Yong-huai Liu, Wen-hao Zhu. An easy-to-use evaluation framework for benchmarking entity recognition and disambiguation systems[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(2): 195-205.
[10] Li Weigang. First and Others credit-assignment schema for evaluating the academic contribution of coauthors[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(2): 180-194.
[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. Towards human-like and transhuman perception in AI 2.0: a review[J]. Front. Inform. Technol. Electron. Eng., 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. Cross-media analysis and reasoning: advances and directions[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(1): 44-57.
[13] Yue-ting Zhuang, Fei Wu, Chun Chen, Yun-he Pan. Challenges and opportunities: from big data to knowledge in AI 2.0[J]. Front. Inform. Technol. Electron. Eng., 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. A swarm intelligence design based on a workshop of meta-synthetic engineering[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(1): 149-152.
[15] Le-kui Zhou, Si-liang Tang, Jun Xiao, Fei Wu, Yue-ting Zhuang. Disambiguating named entities with deep supervised learning via crowd labels[J]. Front. Inform. Technol. Electron. Eng., 2017, 18(1): 97-106.