期刊文献+
任意字段
题名或关键词
题名
关键词
文摘
作者
第一作者
机构
刊名
分类号
参考文献
作者简介
基金资助
栏目信息

多路R树连接的加权处理

Weighted Processing of Multi-way R-tree Join
下载PDF
导出
摘要 空间连接运算是空间数据查询中最重要、最耗时的基本操作之一,其中基于R树的空间连接(RJ)被认为是一种高效的处理机制,但在空间连接的精化阶段处理复杂的空间数据时需要很大的系统开销。基于MBR及直接查询谓词,提出了一种加权处理方法,并扩展了R树结构及MRJ算法。从而优化了多路R树连接的筛选处理,能得到更加有效的候选集;同时,减少了磁盘访问次数,可节省CPU及I/O的时间开销。还通过应用实例验证了其在空间数据库查询优化方面的优势。 Spatial join is the most important and time-consumed in spatial query of SDBMS,R-tree based spatial join is always considered as a kind of high efficient processing mechanism.In the refinement step of spatial join,it needs a lot of system overhead to process complex spatial data.This paper based on the MBR and the direct query predicate proposes a method to generate a weighted complete query graph and extends the structure of R-tree and the MRJ algorithm which mainly contributes to optimize the filter step of the multi-way R-tree join to get a set of more effective candidates and then reduce the frequency of disk access and the overhead of CPU as well as I/O.Through the experiment of specific application by using this method,we show the significant superiority in optimizing the spatial query of SDBMS.
作者 姜素芳 陈天滋
机构地区 江苏大学计算机科学与通信工程学院
出处 《计算机工程与应用》 CSCD 北大核心 2006年第31期174-178,共5页 Computer Engineering and Applications
基金 信息产业部资助项目(2003xk320014)
关键词 空间连接 多路R树连接 派生谓词 查询图 加权处理 spatial join multi-way R-tree join derived predicate query graph weighted processing
分类号 TP311 [自动化与计算机技术—计算机软件与理论]
  • 相关文献

参考文献8

  • 1PREPARATA F P,SHAMOS M I.Computational geometry:an introduction[M].Berlin:Springer,1985.
  • 2MAMOULIS N,PAPADIAS D.Multiway spatial joins[J].ACM Trans Database Syst(TODS),2001,26(4):424-475.
  • 3PARK H H.Early separated filter/refinement strategies and multiway spatial joins for spatial query optimization[D].KAIST,2001.
  • 4EGENHOFER M J,HERRING J R.Categorizing binary topological relationships between regions,lines and points in geographic database,technical report,91-7[R].Orono:University of Maine,1991.
  • 5PARKA H H,MINB J K,CHUNGB C W,et al.Multi-way R-tree joins using indirect predicates[C]//Proc Elsevier B V Information and Software Technology,2004,46:739-751.
  • 6HOROWITZ E,SAHNI S.Fundamentals of computer algorithms[M].Rockville,MD:Computer Science Press,1978.
  • 7李立言,秦小麟.空间数据库中连接运算的处理与优化[J].中国图象图形学报（A辑）,2003,8(7):732-737. 被引量：11
  • 8蒋苏蓉,石青青,黄志良.空间查询优化[J].计算机工程与应用,2004,40(9):188-190. 被引量：5

二级参考文献11

  • 1Hgarcia-Molina J D Ullman J Widom著 杨冬青 唐世渭等译.数据库系统实现[M].北京:机械工业出版社,2001..
  • 2[1]Brinkhoff T, Kriegel H P, Seeger B. Efficient processing of spatial joins using R-trees [A]. In: Proceedings of the 1993 Association for Computing Machinery Special Interest Group International Conference on Management of Data [C].Washington,D. C. USA,1993: 237～246.
  • 3[2]Huang Y W, ling N, Rundensteiner E A. A cost model for estimating the performance of spatial joins using R-trees [A].In: Proceedings of Ninth International Conference on Scientific and Statistical Database Management [C]. Olympia, Washington USA,1997: 30～38.
  • 4[3]Mamoulis N, Papadias D. Integration of spatial join algorithms for processing multiple inputs[A]. In: Proceedings of the 1999 Association for Computing Machinery Special Interest Group International Conference on Management of Data [C].Philadelphia,Pennsylvania USA, 1999: 1 ～ 12.
  • 5[4]Huang Y W, Jing N, Rundensteiner E A. Spatial joins using Rtrees: Breadth first traversal with global optimizations [A]. In:Proceedings of 23rd International Conference on Very Large Data Bases [C]. Athens ,Greece, 1997: 396～405.
  • 6[5]Lo M L, Ravishankar C V. The design and implementation of seeded trees: an efficent method for spatial joins [J]. IEEE Transactions on Knowledge and Data Engineering, 1998,10 (1):136～152.
  • 7[6]Lo M L, Ravishankar C V. Spatial hash-joins [A]. In:Proceedings of the 1996 Assciation for Computing Machinery Special Interest Group International Conference on Management of Data[C]. Montreal,Cananda, 1996: 247～258.
  • 8[7]Patel J M, DeWitt D J. Partition based spatial merge join[A].In: Proceedings of the 1996 Association for Computing Machinery Special Interest Group International Conference on Management of Data[C]. Montreal,Cananda, 1996: 259～270.
  • 9[8]Koudas N, Sevcik K C. Size separation spatial join[A]. In:Proceedings of the 1997 Assciation for Computing Machinery Special Interest Group International Conference on Management of Data[C]. Tucson, Arizona USA, 1997: 324～335.
  • 10[9]Garcia-Molina H, Ullman J D, Widom J. Database system implementation [M]. Upper Saddle River, New Jersey USA:Prentice Hall, 2000: Chapter 7, Section 6.

共引文献12

计算机工程与应用
2006年 第31期

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部