CAJ | 학술논문

考虑偏好top-k计算问题,提出一种整合网格索引和DG索引的Gridded Dominant Graph(GDG)混合索引结构.首先,提出基于数据点逆支配点集性质的剪枝自由点方法,该方法大大减少了构建索引中的数据点及查询时可能访问的数据点.通过网格索引高效地计算逆支配点集,并得出网格中"k-最大运算区域"和"k-最大查找区域",分别在建立索引和top-k查询阶段近似地剪枝自由点.然后,分析了查询索引阶段层次式索引(如dominant graph(DG))在同一层次中无序访问数据点的不足,通过增加网格索引而使访问有序.计算网格概要信息并将网格单元按函数分值排序,使层次内数据点依据网格单元顺序而访问有序.由于附加的网格索引增加计算和存储开销较少,同时性能有较大提升,所以GDG适用性强.理论分析和实验结果均验证了上述方法的有效性.
고필편호top-k계산문제,제출일충정합망격색인화DG색인적Gridded Dominant Graph(GDG)혼합색인결구.수선,제출기우수거점역지배점집성질적전지자유점방법,해방법대대감소료구건색인중적수거점급사순시가능방문적수거점.통과망격색인고효지계산역지배점집,병득출망격중"k-최대운산구역"화"k-최대사조구역",분별재건립색인화top-k사순계단근사지전지자유점.연후,분석료사순색인계단층차식색인(여dominant graph(DG))재동일층차중무서방문수거점적불족,통과증가망격색인이사방문유서.계산망격개요신식병장망격단원안함수분치배서,사층차내수거점의거망격단원순서이방문유서.유우부가적망격색인증가계산화존저개소교소,동시성능유교대제승,소이GDG괄용성강.이론분석화실험결과균험증료상술방법적유효성.