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

1(国防科学技术大学计算机学院长沙 410073) 2(长沙民政职业技术学院软件学院长沙 410004) 3(解放军后勤指挥学院后勤指挥系北京 100858) (gl.nudt@gmail.com)

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

1(College of Computer, National University of Defense Technology, Changsha 410073) 2(School of Software, Changsha Social Work College, Changsha 410004) 3(Department of Logistics Command, Logistics Command Academy of Peoples Liberation Army, Beijing 100858)

摘要:
考虑偏好top-k计算问题,提出一种整合网格索引和DG索引的Gridded Dominant Graph(GDG)混合索引结构.首先,提出基于数据点逆支配点集性质的剪枝自由点方法,该方法大大减少了构建索引中的数据点及查询时可能访问的数据点.通过网格索引高效地计算逆支配点集,并得出网格中“k-最大运算区域”和“k-最大查找区域”,分别在建立索引和top-k查询阶段近似地剪枝自由点.然后,分析了查询索引阶段层次式索引(如dominant graph(DG))在同一层次中无序访问数据点的不足,通过增加网格索引而使访问有序.计算网格概要信息并将网格单元按函数分值排序,使层次内数据点依据网格单元顺序而访问有序.由于附加的网格索引增加计算和存储开销较少，同时性能有较大提升,所以GDG适用性强.理论分析和实验结果均验证了上述方法的有效性.
- preference top-k query /
- reverse dominant point set /
- dominant graph /
- grid index /
- gridded dominant graph