• 中国出版政府奖提名奖

    中国百强科技报刊

    湖北出版政府奖

    中国高校百佳科技期刊

    中国最美期刊

    留言板

    尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

    姓名
    邮箱
    手机号码
    标题
    留言内容
    验证码

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

    林伟华 谈晓军 余艳 毛典辉

    林伟华, 谈晓军, 余艳, 毛典辉, 2010. 基于多重近似索引的空间距离半连接. 地球科学, 35(3): 415-420. doi: 10.3799/dqkx.2010.049
    引用本文: 林伟华, 谈晓军, 余艳, 毛典辉, 2010. 基于多重近似索引的空间距离半连接. 地球科学, 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

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

    doi: 10.3799/dqkx.2010.049
    基金项目: 

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

    国家重点“863”项目 2007AA120503

    详细信息
      作者简介:

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

    • 中图分类号: TP311

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

    • 摘要: 为了更有效地解决基于外部近似索引空间距离半连接效率较低问题,提出一种基于多重近似索引的空间距离半连接处理方法.该方法在充分利用多重近似索引结构特征基础上,推导出在半连接处理中的距离和空间对象数量约束关系,并在距离半连接算法中利用这些约束关系进行连接处理,从而减少了进行精过滤处理空间对象的数量.通过实验分析表明,基于多重近似索引的距离半连接算法有效,并且基于多重近似索引比基于外部近似索引的距离半连接效率要高.

       

    • 图  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 距离计算次数(次) 需精过滤对象对数(对)
      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
    • 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
    • 加载中
    图(1) / 表(2)
    计量
    • 文章访问数:  3047
    • HTML全文浏览量:  416
    • PDF下载量:  78
    • 被引次数: 0
    出版历程
    • 收稿日期:  2010-01-15
    • 刊出日期:  2010-05-01

    目录

      /

      返回文章
      返回