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

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

doi:10.3799/dqkx.2010.049

Volume 35 Issue 3

May 2010

Turn off MathJax

Article Contents

Article Navigation > Earth Science > 2010 > 35(3): 415-420

LIN Wei-hua, TAN Xiao-jun, YU Yan, MAO Dian-hui, 2010. Spatial Distance Semi-Join Based on Multi-Approximate Spatial Index. Earth Science, 35(3): 415-420. doi: 10.3799/dqkx.2010.049

Citation:

LIN Wei-hua, TAN Xiao-jun, YU Yan, MAO Dian-hui, 2010. Spatial Distance Semi-Join Based on Multi-Approximate Spatial Index. Earth Science, 35(3): 415-420. doi: 10.3799/dqkx.2010.049

LIN Wei-hua, TAN Xiao-jun, YU Yan, MAO Dian-hui, 2010. Spatial Distance Semi-Join Based on Multi-Approximate Spatial Index. Earth Science, 35(3): 415-420. doi: 10.3799/dqkx.2010.049

Citation:

LIN Wei-hua, TAN Xiao-jun, YU Yan, MAO Dian-hui, 2010. Spatial Distance Semi-Join Based on Multi-Approximate Spatial Index. Earth Science, 35(3): 415-420. doi: 10.3799/dqkx.2010.049

PDF( 186 KB)

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

doi: 10.3799/dqkx.2010.049

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

Received Date: 2010-01-15
Publish Date: 2010-05-01

Abstract

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

FullText(HTML)

References(15)

References

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

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

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.

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

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.

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

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

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

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).

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

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).

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

梁银, 张虹, 2008. 一种多路空间距离连接查询处理方法. 计算机应用, 28(1): 155-158. https://www.cnki.com.cn/Article/CJFDTOTAL-JSJY200801052.htm

肖予钦, 张巨, 陈荦, 等, 2003. 基于DJI分步实现的联机空间距离查询处理. 国防科技大学学报, 25(6): 5-9.

张奋, 潘梅生, 邹北骥, 2007. 基于SR-树的空间对象最近邻查询. 计算机工程与应用, 43(4): 173-175. https://www.cnki.com.cn/Article/CJFDTOTAL-JSGG200704052.htm

Relative Articles

Supplements(0)

Cited By

Proportional views