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

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

doi:10.1631/FITEE.1400165

Your Location：

Home >

Browse articles >

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

计算机与自动化 | Updated：2022-06-06

- 不确定空间二维范围查询的Kd-树和四叉树分解
- Kd-tree and quad-tree decompositions for declustering of 2D range queries over uncertain space
- 信息与电子工程前沿（英文） 2015年16卷第2期页码：98-108
- Affiliations：
  
  Department of Computer Engineering, Kocaeli University, Kocaeli 41380, Turkey
- Author bio：
  
  ‡Corresponding Author
- Funds：
- DOI：10.1631/FITEE.1400165
  中图分类号：
- 收稿：2014-05-05，
  
  修回：2015-01-05，
  
  录用：2014-10-11，
  
  纸质出版：2015-02
- Accepted：
Scan QR Code
不确定空间二维范围查询的Kd-树和四叉树分解[J]. 信息与电子工程前沿（英文）, 2015,16(2):98-108.

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.
不确定空间二维范围查询的Kd-树和四叉树分解[J]. 信息与电子工程前沿（英文）, 2015,16(2):98-108. DOI： 10.1631/FITEE.1400165.

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 .

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

暂无数据