GDG:一种基于逆支配点集的top-k高效查询索引方法  

Gridded Dominant Graph:A More Efficient Index Structure for top-k Queries Based on Reverse Dominant Point Set

作　　者：甘亮[1] 金鑫[2] 贾焰[1] 李爱平[1] 盘仰柯[3] 

机构地区：[1]国防科学技术大学计算机学院,长沙410073 [2]长沙民政职业技术学院软件学院,长沙410004 [3]解放军后勤指挥学院后勤指挥系,北京100858

出　　处：《计算机研究与发展》2010年第10期1771-1784,共14页Journal of Computer Research and Development

基　　金：国家"八六三"高技术研究发展计划基金项目(2007AA010502;2007AA01Z474;2006AA01Z451);教育部新世纪优秀人才支持计划基金项目(NCET-06-0928)~~

摘　　要：考虑偏好top-k计算问题,提出一种整合网格索引和DG索引的GriddedDominantGraph(GDG)混合索引结构.首先,提出基于数据点逆支配点集性质的剪枝自由点方法,该方法大大减少了构建索引中的数据点及查询时可能访问的数据点.通过网格索引高效地计算逆支配点集,并得出网格中"k-最大运算区域"和"k-最大查找区域",分别在建立索引和top-k查询阶段近似地剪枝自由点.然后,分析了查询索引阶段层次式索引(如dominantgraph(DG))在同一层次中无序访问数据点的不足,通过增加网格索引而使访问有序.计算网格概要信息并将网格单元按函数分值排序,使层次内数据点依据网格单元顺序而访问有序.由于附加的网格索引增加计算和存储开销较少,同时性能有较大提升,所以GDG适用性强.理论分析和实验结果均验证了上述方法的有效性.To address the problem of top-k queries with preferable function f（）,this paper proposes a hybrid index structure gridded dominant graph（GDG）which integrates grid index into dominant graph（DG）index.Firstly,it proposes an approach to prune a large amount of free points of top-k queries by reverse dominant point set（RDPS）in constructing and traveling the index of data set.GDG uses grid index to calculate all RDPSes approximately and efficiently.When constructing GDG,grid index figures out k-max calculating region to prune free points that all top-k fucntion f（）would not visit,which decreases the amount of index dramatically.When traveling GDG,grid index figures out k-max search region by f（）which avoids traveling those free points of ad-hoc top-k function f（）.Secondly,it analyses the drawback of layer-based indice,such as DG,which can not rank those data points in the same layer.So,GDG uses grid index to rank those data points in the same layer approximately by k-max search region by f（）,and makes less visited points than DG.Howerver,grid index needs less additional computation and storage that makes the GDG index more adaptive for top-k queries.Analytical and experimental evidences show the efficiency of the proposed approaches.

关 键 词：偏好top-k查询 逆支配点集 支配图 网格索引 网格支配网 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]