KDT tree：Multi-dimensional index structure for spatial data

doi:10.3778/j.issn.1002-8331.2009.08.009

Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (8): 29-31.DOI: 10.3778/j.issn.1002-8331.2009.08.009

• 博士论坛 • Previous Articles Next Articles

KDT tree：Multi-dimensional index structure for spatial data

QIU Yong-hong^1,2,ZENG Yong-nian²,ZOU Bin²

1.College of Resources and Environment Science，Hunan Normal University，Changsha 410081，China
2.School of Info-physics and Geomatics Engineering，Central South University，Changsha 410083，China

Received:2008-11-07 Revised:2008-12-27 Online:2009-03-11 Published:2009-03-11
Contact: QIU Yong-hong

KDT树：一种多维空间数据索引结构

邱永红^1,2,曾永年²,邹滨²

1.湖南师范大学资源与环境科学学院，长沙 410081
2.中南大学信息物理工程学院，长沙 410083

通讯作者: 邱永红

Abstract

Abstract: Authors firstly propose an innovative multi-dimensional index structure for spatial data，namely KD Ternary tree（KDT），with the expansion of traditional KD-tree.Then，the data structure and algorithms of KDT are stated.Finally，the performance of KDT is tested and evaluated by comparing with R-tree which is currently the most popular spatial data index structure.The results reveal that，as a main memory index structure，KDT surpasses R tree over temporal efficiency，and this characteristic of KDT can be enhanced with the increasing data records indexed.In addition，the results also indicate that KDT has better capacity of indexing spatial data objects（i.e.line，area，volume，etc.） covering a certain space compared to KD tree.

Key words: KD tree, KDT tree, multi-dimensional spatial data, index structure

摘要： 通过扩展KD树索引结构，提出了一种新的多维空间数据索引结构——KDT树，给出了数据结构和算法描述，并通过与当前流行的空间数据索引结构——R树的对比，对其性能进行了测试与评估。实验表明，作为一种主存索引结构，KDT树在时间效率方面明显优于R树，并且此种优势随着索引记录数量的增多而越加明显。此外，KDT树亦能较好地解决常规KD树在索引占据一定空间范围的空间对象（如：线、面、体等）时存在的问题。

关键词: KD树, KDT树, 多维空间数据, 索引结构

QIU Yong-hong^1,2,ZENG Yong-nian²,ZOU Bin². KDT tree：Multi-dimensional index structure for spatial data[J]. Computer Engineering and Applications, 2009, 45(8): 29-31.

邱永红^1,2,曾永年²,邹滨². KDT树：一种多维空间数据索引结构[J]. 计算机工程与应用, 2009, 45(8): 29-31.

[1]	XU Hongbo1，2, YAO Nianmin2, HAN Qilong2, PAN Haiwei2. Index structure CB-tree supporting line query [J]. Computer Engineering and Applications, 2015, 51(11): 114-118.
[2]	ZHANG Debin¹，CAO Lijun²，LIANG Yongxin¹，ZHANG Zhongping¹. X*tree index structure for k nearest neighbor queries [J]. Computer Engineering and Applications, 2011, 47(5): 123-125.
[3]	LI Jin，YU Jianqiao. Research on technology of reverse nearest neighbor query for spatial objects [J]. Computer Engineering and Applications, 2011, 47(33): 146-148.
[4]	ZHENG Jiabin，JIANG Xiajun. Storage and indexing of moving objects XML database [J]. Computer Engineering and Applications, 2011, 47(20): 138-143.
[5]	SUN Jin-guang，WANG Shu-e. CKDB-Tree：Effective index structure in high-dimensional data spaces [J]. Computer Engineering and Applications, 2009, 45(30): 157-160.
[6]	LI Bo-han¹,HAO Zhong-xiao^1,2. Cost analysis for dynamic update of vector space partitioning strategy index [J]. Computer Engineering and Applications, 2009, 45(18): 18-21.
[7]	SONG Xiao-yu,SUN Ye-ting,SUN Huan-liang. K-nearest neighbor queries over moving objects for dynamic workload [J]. Computer Engineering and Applications, 2007, 43(27): 152-155.
[8]	QIU Ming-hua，YIN Li-hua，LI Bin. Anomaly detection technology based on multidimensional binary search tree [J]. Computer Engineering and Applications, 2007, 43(22): 122-125.
[9]	DONG Hong-wei. Study for cell grid methods finding k nearest neighbors [J]. Computer Engineering and Applications, 2007, 43(21): 52-56.
[10]	,. A RESEARCH On OVERSET MESH PRE-PROCESSING TECHNOLOGY [J]. Computer Engineering and Applications, 2006, 42(1期): 23-26.

KDT tree：Multi-dimensional index structure for spatial data

KDT树：一种多维空间数据索引结构

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 10

Recommended Articles

Metrics