基于多重近似索引的空间距离半连接

林伟华; 谈晓军; 余艳; 毛典辉

doi:10.3799/dqkx.2010.049

基于多重近似索引的空间距离半连接

doi: 10.3799/dqkx.2010.049

1.
中国地质大学信息工程学院，湖北武汉 430074
2.
华中科技大学仿真与数字化工程中心，湖北武汉 430074
3.
华中科技大学文华学院，湖北武汉 430074
4.
北京工商大学计算机与信息工程学院，北京 100048

基金项目:

国家自然科学基金资助项目 40601072

国家重点“863”项目 2007AA120503

详细信息

作者简介:
林伟华(1978－)，男，博士，讲师，主要从事空间数据库和数字城市研究.E-mail：lwhcug@163.com

中图分类号: TP311
计量
- 文章访问数: 2872
- HTML全文浏览量: 164
- PDF下载量: 75
- 被引次数: 0
出版历程
- 收稿日期: 2010-01-15
- 刊出日期: 2010-05-01

Spatial Distance Semi-Join Based on Multi-Approximate Spatial Index

1.
Faculty of Information Engineering, China University of Geosciences, Wuhan 430074, China
2.
Digital Engineering Research Center, Huazhong University of Science and Technology, Wuhan 430074, China
3.
Wenhua College, Huazhong University of Science and Technology, Wuhan 430074, China
4.
School of Computer and Information Engineering, Beijing Technology and Business University, Beijing 100048, China

摘要

摘要: 为了更有效地解决基于外部近似索引空间距离半连接效率较低问题，提出一种基于多重近似索引的空间距离半连接处理方法.该方法在充分利用多重近似索引结构特征基础上，推导出在半连接处理中的距离和空间对象数量约束关系，并在距离半连接算法中利用这些约束关系进行连接处理，从而减少了进行精过滤处理空间对象的数量.通过实验分析表明，基于多重近似索引的距离半连接算法有效，并且基于多重近似索引比基于外部近似索引的距离半连接效率要高.
- 半连接 /
- 空间距离 /
- 空间索引 /
- 多重近似索引 /
- 空间数据库
Abstract: To improve the efficiency for space distance semi-join based on external approximation index, a method of spatial distance semi-join based on multi-approximate index is proposed. The constraint relationship of distance and the number of spatial objects during processing semi-join are deduced based on taking advantage of characteristics of multi-approximate index structure. And these are used during spatial distance semi-join to reduce the number of spatial objects needed to process during refine filter step. A series of tests and verifications indicate that the new method of spatial distance semi-join is valid and the performance of index based on multi-approximation is more effective than the index based on external approximation during processing spatial distance semi-join.
- semi-join /
- spatial distance /
- spatial index /
- multi-approximate index /
- spatial database

HTML全文

图 1 MR-tree索引结构示意

(a)为空间数据的平面示意；(b)为其对应的MR-tree结构

Fig. 1. The index architecture of MR-tree

下载: 全尺寸图片幻灯片

表 1 不同距离上限和索引结构下距离半连接性能比较

Table 1. The performance comparison of distance semi-join by the difference distance upper-limit and index structure

距离上限	距离计算次数(次)		需精过滤对象对数(对)
距离上限	R-tree	MR-tree	R-tree	MR-tree
100	8 380	18 844	84	54
200	13 754	32 027	141	90
400	26 036	61 940	228	119
600	41 188	99 088	239	137
800	58 382	141 635	312	171
1 000	77 438	189 170	326	178
1 300	97 344	238 935	276	178
1 500	102 026	250 640	183	104
1 700	102 950	252 950	43	32
2 000	102 950	252 950	0	0

下载: 导出CSV

表 2 不同连接结果k和索引结构下距离半连接性能比较

Table 2. The performance comparison of distance semi-join by the difference join result k and index structure

k	距离计算次数(次)		需精过滤对象对数(对)
k	R-tree	MR-tree	R-tree	MR-tree
1	16 692	39 060	3	2
2	16 692	39 060	3	2
3	16 692	39 060	3	2
4	16 692	39 060	3	2
5	16 692	39 060	3	2
6	16 692	39 060	5	3
7	19 124	45 140	6	4
8	19 124	45 140	13	8
9	19 124	45 140	22	13
10	21 322	50 635	30	17
11	21 322	50 635	37	18
12	21 322	50 635	41	19
13	21 322	50 635	47	20
14	21 322	50 635	51	23
15	21 322	50 635	56	25
16	21 642	50 955	61	27
17	21 642	50 955	62	28
18	22 992	54 330	68	32
19	22 992	54 330	77	37
20	22 992	54 330	81	40

下载: 导出CSV

参考文献(15)

[1]	Corral, A., Manolopoulos, Y., Theodoridis, Y., et al., 2000. Closest pair queries in spatial databases. ACM SIGMOD Record, 29(2): 189-200. doi: 10.1145/335191.335414
[2]	Corral, A., Manolopoulos, Y., Theodoridis, Y., et al., 2004. Algorithms for processing k-closest-pair queries in spatial databases. Data and Knowledge Engineering, 49(1): 67-104. doi: 10.1016/j.datak.2003.08.007
[3]	Guttman, A., 1984. R-trees: a dynamic index structure for spatial searching. The ACM SIGMOD Int. Conf. on Management of Data Boston, Massachusetts, 47-57.
[4]	Liang, Y., Zhang, H., 2008. Method for multi-way spatial distance join query processing. Computer Applications, 28(1): 155-158 (in Chinese with English abstract). http://www.oalib.com/paper/1626985
[5]	Lin, W.H., Wu, Y.G., Tan, X.J., et al., 2008. Multi-approximate index based on R-tree for massive spatial data. Proceedings of Information Technology and Environmental System Science, Jiaozuo, 1: 574-579.
[6]	Papadopoulos, A.N., Nanopoulos, A., Manolopoulos, Y., 2006. Processing distance join queries with constraints. Computer Journal, 49(3): 281-296. doi: 10.1093/comjnl/bxl002
[7]	Sankaranarayanan, J., Alborzi, H., Samet, H., 2006. Distance join queries on spatial networks. In: ACM, ed., proceedings of the 14th annual ACM international symposium on advances in GIS, New York, U.S.A., 211-218. doi: 10.1145/1183471.1183506
[8]	Shin, H., Moon, B., Lee, S., 2003. Adaptive and incremental processing for distance join queries. IEEE Transactions on Knowledge and Data Engineering, 15(6): 1561-1578. doi: 10.1109/TKDE.2003.1245293
[9]	Xiao, Y.Q., Zhang, J., Chen, L., et al., 2003. Online spatial distance queries processing based on the multi-step implementation of DJI. Journal of National University of Defense Technology, 25(6): 5-9 (in Chinese with English abstract).
[10]	Yeh, T.S., 1999. Spot: distance based join indices for spatial data. In: ACM, ed., proceedings of the 7th ACM international sysmposium on advance in GIS, New York, U.S.A., 103-109. doi: 10.1145/320134.320161
[11]	Zhang, F., Pan, M.S., Zou, B.J., 2007. Nearest neighbor queries of spatial object based on SR-tree. Computer Engineering and Applications, 43(4): 173-175 (in Chinese with English abstract).
[12]	Zhu, M. L., Papadias, D., Zhang, J., et al., 2005. Top-k spatial joins. IEEE Transaction on Knowledge and Data Engineering, 17(4): 567-579. doi: 10.1109/TKDE.2005.65
[13]	梁银, 张虹, 2008. 一种多路空间距离连接查询处理方法. 计算机应用, 28(1): 155-158. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJY200801052.htm
[14]	肖予钦, 张巨, 陈荦, 等, 2003. 基于DJI分步实现的联机空间距离查询处理. 国防科技大学学报, 25(6): 5-9.
[15]	张奋, 潘梅生, 邹北骥, 2007. 基于SR-树的空间对象最近邻查询. 计算机工程与应用, 43(4): 173-175. https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG200704052.htm