Kd-tree and quad-tree decompositions for declustering of 2D range queries over uncertain space

Sayar Ahmet; Eken Süleyman; Öztürk Okan

doi:10.1631/FITEE.1400165

Your Location：

Home >

Browse articles >

Kd-tree and quad-tree decompositions for declustering of 2D range queries over uncertain space

Computer & Automation | Updated：2022-06-06

- Kd-tree and quad-tree decompositions for declustering of 2D range queries over uncertain space
- 不确定空间二维范围查询的Kd-树和四叉树分解
- Frontiers of Information Technology & Electronic Engineering Vol. 16, Issue 2, Pages: 98-108(2015)
- Affiliations：
  
  Department of Computer Engineering, Kocaeli University, Kocaeli 41380, Turkey
- Author bio：
  
  ‡Corresponding Author
- Funds：
- DOI：10.1631/FITEE.1400165
  CLC：
- Received：05 May 2014，
  
  Revised：2015-01-05，
  
  Accepted：11 October 2014，
  
  Published：2015-02
- Accepted：
Scan QR Code
Sayar Ahmet, Eken Süleyman, Öztürk Okan. Kd-tree and quad-tree decompositions for declustering of 2D range queries over uncertain space[J]. Frontiers of Information Technology & Electronic Engineering, 2015, 16(2): 98-108.
DOI：

Sayar Ahmet, Eken Süleyman, Öztürk Okan. Kd-tree and quad-tree decompositions for declustering of 2D range queries over uncertain space[J]. Frontiers of Information Technology & Electronic Engineering, 2015, 16(2): 98-108. DOI： 10.1631/FITEE.1400165.

摘要

目的

通过点数据二维范围查询性能测试评价空间划分方法（kd-树和四叉树）的可行性和有效性。

创新

基于不确定空间创建有效索引，将范围查询分解成多个等尺寸子范围求解。

方法

将数据集合定义为二维平面上的点，进行范围查询（窗口查询）。根据数据大小（相对大或相对小）及其分布（随机或偏斜）测试四种方案（图3-8）。相同的测试同时应用于真实数据（Turkey’s points of interest data，图9-11）。

结论

所提算法有助选取由索引表格创建的最佳划分组合，最小化给定查询响应时间。四叉树索引平行度更高，这很大程度上由于四叉树更清晰地揭示数据空间位置。

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.

关键词

Keywords

references

JL Bentley . Multidimensional binary search trees used for associative searching . Commun ACM , 1975 . 18 ( 9 ): 509 - 517 . DOI: 10.1145/361002.361007 http://doi.org/10.1145/361002.361007 .

M Beynon , C Chang , U Catalyurek , 等 . Processing large-scale multi-dimensional data in parallel and distributed environments . Parall Comput , 2002 . 28 ( 5 ): 827 - 859 . DOI: 10.1016/S0167-8191(02)00097-2 http://doi.org/10.1016/S0167-8191(02)00097-2 .

VP Chakka , AC Everspaugh , JM Patel . Indexing large trajectory data sets with SETI . 2003 . Proc. 1st Biennial Conf. on Innovative Data Systems Research . .

JP Chilès , P Delfiner . Geostatistics: Modeling Spatial Uncertainty , 2009 . : New York, USA John Wiley & Sons , .

TCK Chou , JA Abraham . Load balancing in distributed systems . IEEE Trans Softw Eng , 1982 . SE-8 ( 4 ): 401 - 412 . DOI: 10.1109/TSE.1982.235574 http://doi.org/10.1109/TSE.1982.235574 .

P Cudre-Mauroux , E Wu , S Madden . TrajStore: an adaptive storage system for very large trajectory data sets . 2010 . Proc. IEEE 26th Int. Conf. on Data Engineering . 109 - 120 . DOI: 10.1109/ICDE.2010.5447829 http://doi.org/10.1109/ICDE.2010.5447829 .

D DeWitt , J Gray . Parallel database systems: the future of high performance database systems . Commun ACM , 1992 . 35 ( 6 ): 85 - 98 . DOI: 10.1145/129888.129894 http://doi.org/10.1145/129888.129894 .

B Furht , A Escalante . Handbook of Data Intensive Computing , 2011 . : New York, USA Springer , .

R Li , B Bhanu , C Ravishankar , 等 . Uncertain spatial data handling: modeling, indexing and query . Comput Geosci , 2007 . 33 ( 1 ): 42 - 61 . DOI: 10.1016/j.cageo.2006.05.011 http://doi.org/10.1016/j.cageo.2006.05.011 .

B Moon , JH Saltz . Scalability analysis of declustering methods for multidimensional range queries . IEEE Trans Knowl Data Eng , 1998 . 10 ( 2 ): 310 - 327 . DOI: 10.1109/69.683759 http://doi.org/10.1109/69.683759 .

S Ray , B Simion , AD Brown , 等 . A parallel spatial data analysis infrastructure for the cloud . 2013 . Proc. 21st ACM SIGSPATIAL Int. Conf. on Advances in Geographic Information Systems . 284 - 293 . DOI: 10.1145/2525314.2525347 http://doi.org/10.1145/2525314.2525347 .

BJ Reich , HH Chang , MJ Strickland . Spatial health effects analysis with uncertain residential locations . Stat Methods Med Res , 2014 . 23 ( 2 ): 156 - 168 . DOI: 10.1177/0962280212447151 http://doi.org/10.1177/0962280212447151 .

H Samet . Foundations of Multidimensional and Metric Data Structures , 2006 . : San Francisco, USA Morgan Kaufmann , .

A Sayar . Fine-grained federation of geographic information services through metadata aggregation . Sci Res Essays , 2013 . 8 ( 46 ): 2242 - 2256 . .

A Sayar , P Marlon , FC Geoffrey . An adaptive range-query optimization technique with distributed replicas . J Cent South Univ , 2014 . 21 ( 1 ): 190 - 198 . DOI: 10.1007/s11771-014-1930-7 http://doi.org/10.1007/s11771-014-1930-7 .

R Sinha , S Samaddar , D Bhattacharyya , 等 . A tutorial on spatial data handling . Int J Database Theory Appl , 2010 . 3 ( 1 ): 1 - 12 . .

L Wang , P Wu , H Chen . Finding probabilistic prevalent colocations in spatially uncertain data sets . IEEE Trans Knowl Data Eng , 2013 . 25 ( 4 ): 790 - 804 . DOI: 10.1109/TKDE.2011.256 http://doi.org/10.1109/TKDE.2011.256 .

W Wei . Analysis of spatial database index technology . 2010 . Proc. 2nd Int. Conf. on Computer Engineering and Technology . 29 - 32 . DOI: 10.1109/ICCET.2010.5486363 http://doi.org/10.1109/ICCET.2010.5486363 .

Y Zhang , X Lin , W Zhang , 等 . Effectively indexing the uncertain space . IEEE Trans Knowl Data Eng , 2010 . 22 ( 9 ): 1247 - 1261 . DOI: 10.1109/TKDE.2010.77 http://doi.org/10.1109/TKDE.2010.77 .

Y Zhong , J Han , T Zhang , 等 . Towards parallel spatial query processing for big spatial data . 2012 . Proc. IEEE 26th Int. Parallel and Distributed Processing Symp. Workshops & PhD Forum . 2085 - 2094 . DOI: 10.1109/IPDPSW.2012.245 http://doi.org/10.1109/IPDPSW.2012.245 .

Views

Downloads

CSCD

Alert me when the article has been cited

Submit

Tools

Publicity Resources

No data

Related Author

No data

Related Institution

No data

Chat

Address：Zhejiang University Press, 148 Tianmushan Road, Hangzhou, China Postal code：310028
Tel：+86-571-88273162 Email：fitee@zju.edu.cn
It is recommended to read the content of this site in Chrome&IE9+. Please switch to extreme mode in browser 360.
Cookies We use cookies to help provide and enhance our service and tailor content. By continuing, you agree to the use of cookies.

⁰