Algorithm for Computing Region Inclusion Relations          Based on QR-tree Index

doi:10.3969/j.issn.1000-3428.2010.21.013

Computer Engineering ›› 2010, Vol. 36 ›› Issue (21): 37-39.

• Networks and Communications • Previous Articles Next Articles

Algorithm for Computing Region Inclusion Relations Based on QR-tree Index

SUN Xiao-ming1,2, JI Gen-lin1,2

(1. School of Computer Science and Technology, Nanjing Normal University, Nanjing 210097, China; 2. Jiangsu Research Center of Information Security & Privacy Technology, Nanjing 210097, China)

Online:2010-11-05 Published:2010-11-03

基于QR树索引的面包含关系求解算法

孙晓明1,2，吉根林1,2

(1. 南京师范大学计算机科学与技术学院，南京 210097；2. 江苏省信息安全保密技术工程研究中心，南京 210097)

作者简介:孙晓明(1986－)，女，硕士研究生，主研方向：数据挖掘；吉根林，教授、博士、博士生导师
基金资助:
国家自然科学基金资助项目(40871176)

Abstract

Abstract: In order to improve the efficiency of computing region inclusion relations, this paper proposes an algorithm for computing region inclusion relations based on QR-tree index. The algorithm builds a QR-tree index according to the information of spatial objects and queries all spatial objects including the region on the QR-tree. The algorithm is applied to spatial clustering in GML data based on line-region inclusion relations. Experimental results show that the algorithm is effective and efficient.

Key words: region inclusion relations, spatial index, R-tree, QR-tree

摘要： 为提高空间拓扑计算中求解面包含关系的效率，提出一种基于QR树索引的面包含关系求解算法。根据空间对象的几何信息建立QR树索引，利用QR树查找面包含的空间对象，并将该算法应用于基于线面包含关系的GML空间聚类。实验结果表明该算法能有效提高计算面包含关系的时间效率。

关键词: 面包含关系, 空间索引, R树, QR树

CLC Number:

TP301.6

SUN Xiao-Meng, JI Gen-Lin. Algorithm for Computing Region Inclusion Relations Based on QR-tree Index[J]. Computer Engineering, 2010, 36(21): 37-39.

孙晓明, 吉根林. 基于QR树索引的面包含关系求解算法[J]. 计算机工程, 2010, 36(21): 37-39.

/ Recommend / Download Citations

URL:

https://www.ecice06.com/EN/Y2010/V36/I21/37

References

[1] Robinson J T. The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Index[C]//Proc. of ACM SIGMOD International Conference on Management of Data. New York, USA: ACM Press, 1981: 10-18. [2] Henrich A, Six H, Widmayer P. The LSD Tree: Spatial Access to Multidimensional Point and Nonpoint Objects[C]//Proc. of the 15th International Conference on Very Large Data Bases. San Francisco, USA: Morgan Kaufmann Publishers Inc., 1989: 45-53. [3] Guttman A. R-trees: A Dynamic Index Structures for Spatial Searching[C]//Proc. of ACM SIGMOD International Conference on Management of Data. New York, USA: ACM Press, 1984: 47-57. [4] Bechman N, Kriegel H P, Schneider R, et al. The R*-tree: An Efficient and Robust Access Method for Points and Rectangles[C]// Proc. of ACM SIGMOD International Conference on Management of Data. New York, USA: ACM Press, 1990: 322-331. [5] Fu Yuchen, Hu Zhiyong, Guo Wei, et al. QR-Tree: A Hybrid Spatial Index Structure[C]//Proc. of International Conference on Machine Learning and Cybernetics. Xi’an, China: [s. n.], 2003: 459-463. [6] Nievergelt J, Hinterberger H, Sevcik K C. The Grid File: An Adaptable Symmetric Multikey File Structure[J]. ACM Trans. on Database Systems, 1984, 9(1): 38-71. [7] Zhang Mingbo, Lu Feng, Chen Changxiu, et al. A Forced Transplant Algorithm for Dynamic R-tree Implementation[C]//Lecture Notes in Computer Science. [S. l.]: Springer, 2006: 459-466. [8] Zhang Donghui, Xia Tian. A Novel Improvement to the R*-tree Spatial Index Using Gain/Loss Metrics[C]//Proc. of the 12th Annual ACM International Workshop on Geographic Information Systems. New York, USA: ACM Press, 2004: 204-213. [9] 张明波, 陆锋, 申排伟, 等. R树家族的演变和发展[J]. 计算机学报, 2005, 28(3): 289-300. [10] 张丽, 吉根林. 一种基于线面包含关系的GML空间聚类算法[J]. 山东大学学报: 工学版, 2009, 39(2): 21-25.

[1]	TANG Wenlin, XIE Kai, WEN Chang, HE Jianbiao. Fast 3D Visualization of Massive Seismic Data in Deep Clustering Index [J]. Computer Engineering, 2022, 48(11): 275-283.
[2]	TANG Hongcheng, WEN Chang, FENG Wenxiang, XIE Kai, FANG Wenqing. Rapid Display Method of Massive Data Based on Intelligent Clustering Model [J]. Computer Engineering, 2019, 45(8): 53-59.
[3]	ZENG Mengqi, MA Weiyin, LI Li. Efficient Image Retrieval Scheme Based on Hybrid Similarity [J]. Computer Engineering, 2019, 45(11): 262-268.
[4]	YI Xiantian,XU Zhan,GUO Chengjun,LIU Dan,ZHANG Ke. Spatial Index Structure Based on Patricia Tree [J]. Computer Engineering, 2015, 41(12): 69-74.
[5]	LI Song,ZHANG Li-ping,LIU Yan,HAO Xiao-hong,YANG He-yu. Dynamic Simple Continues Near Neighbor Chain Query with Obstacles [J]. Computer Engineering, 2014, 40(8): 52-57.
[6]	WU Yong, LUO Teng-yuan, WANG Mei-zhen. Research on Acquisition and Retrieval Method of Locatable Image [J]. Computer Engineering, 2014, 40(7): 207-211,220.
[7]	ZHAO Long, MIN Shi-ping, DAI Qiang-ling. 3D Geological Section Generating Algorithm Based on Octree [J]. Computer Engineering, 2014, 40(2): 250-255.
[8]	ZHAO Jingchang,BAI Runcai,LIU Guangwei,LIU Wei. TIN Intersection Algorithm Based on Spatial Index and Collision Detection [J]. Computer Engineering, 2014, 40(12): 296-301.
[9]	GAO Jun, HAO Zhong-Xiao. Point Nearest Neighbor Query of Spatial Database Plane Curve [J]. Computer Engineering, 2012, 38(15): 46-49.
[10]	LI Guang-Shi, MENG Xiang-Ru. Vector Data Safety Protection Method in Oracle [J]. Computer Engineering, 2012, 38(10): 102-104.
[11]	XIE Chuan. Improved Cluster-Tree Routing Algorithm in ZigBee [J]. Computer Engineering, 2011, 37(7): 115-117.
[12]	DIAO Yan-Wei, CHENG Zhen-Lin, DONG Hui, FANG Jin-Yun. Grid Index Technology Applied in Web Map [J]. Computer Engineering, 2011, 37(2): 27-29.
[13]	JU Zhi-Wen, BI Hong-Zhe, LI Gen. Multi-scale Index Tree of Spatial Data Based on Clustering [J]. Computer Engineering, 2011, 37(14): 56-58.
[14]	CA Yue, YUAN Jin-Sheng. Text Clustering Based on Improved DBSCAN Algorithm [J]. Computer Engineering, 2011, 37(12): 50-52.
[15]	LI Jian-Xun, CHEN Bing, JIANG Ren-Gui, CHEN Tian-Qiang. Quadtree Spatial Index Algorithm Oriented to Image Pyramid [J]. Computer Engineering, 2011, 37(10): 11-13.

Please choose a citation manager

Content to export

Algorithm for Computing Region Inclusion Relations Based on QR-tree Index

基于QR树索引的面包含关系求解算法

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

模态框（Modal）标题

Please choose a citation manager

Content to export

Algorithm for Computing Region Inclusion Relations Based on QR-tree Index

基于QR树索引的面包含关系求解算法

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments