空间数据库网格索引机制的最优划分  

Optimum Mesh-Indexing for Spatial Database

作　　者：胡久乡[1] 何松[1] 钟瑜[1] 

机构地区：[1]华中科技大学计算机科学与技术学院,武汉430074

出　　处：《计算机学报》2002年第11期1227-1230,共4页Chinese Journal of Computers

基　　金：本课题得到国家高性能计算基金资助

摘　　要：该文证明了当空间对象的分布特征小于0.2929时,一级网格索引机制才有效,并获得了最佳网格划分条件.通过分析二级网格的最优划分,证明了二级网格检索机制比一级网格索引机制有效,可以减少存储桶的个数.The idea of mesh-indexing is that the space (including mXn pixels) is first decomposed into one-layer mesh which includes K≡M×N blocks called bucks,then a buck will be divided into smaller bucks provided that the distribution of the spatial objects in it is large enough. This paper first defines that A indexing is more effective than B indexing,if the average number of quering a spatial object in the spatial database under A indexes is less than that under B indexes. Then,it proves that the average of queries of one-layer-mesh indexing is (1-qK+1/K)mn,andthat one-layer-mesh indexing is more effective than classical indexing which search a spatial object by pixel,if the probability p = 1-q of distribution of spatial object is below 0. 2929,and thebest mesh generation is reached when f(K)≡1-qk +1/K is minmum. Finally,it is obtained thatthe average number of queries under two-layer-mesh indexing is (1-qk+1/K-(1-qK)(q1k1-1/K))mn,where K1=K/ (M1 ×N1), and p1=p/(1-qK) , and q1 =1- p1, and that two-layer-mesh indexing is always more effective than one-layer-mesh indexing, and the number of storage buck is decreased.

关 键 词：空间数据库 网格索引机制 最优划分 地理信息系统 R树 

分 类 号：TP392[自动化与计算机技术—计算机应用技术] P208[自动化与计算机技术—计算机科学与技术]