高级检索
    甘亮, 金鑫, 贾焰, 李爱平, 盘仰柯. GDG:一种基于逆支配点集的top-k高效查询索引方法[J]. 计算机研究与发展, 2010, 47(10): 1771-1784.
    引用本文: 甘亮, 金鑫, 贾焰, 李爱平, 盘仰柯. GDG:一种基于逆支配点集的top-k高效查询索引方法[J]. 计算机研究与发展, 2010, 47(10): 1771-1784.
    Gan Liang, Jin Xin, Jia Yan, Li Aiping, Pan Yangke. Gridded Dominant Graph: A More Efficient Index Structure for top-k Queries Based on Reverse Dominant Point Set[J]. Journal of Computer Research and Development, 2010, 47(10): 1771-1784.
    Citation: Gan Liang, Jin Xin, Jia Yan, Li Aiping, Pan Yangke. Gridded Dominant Graph: A More Efficient Index Structure for top-k Queries Based on Reverse Dominant Point Set[J]. Journal of Computer Research and Development, 2010, 47(10): 1771-1784.

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

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

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

       

    /

    返回文章
    返回