基于星型模式的一个多路top-kjoin算法

摘要

top-kjoin查询返回用户最感兴趣的k个连接结果。近来top-kjoin已经成为一个重要的研究课题,且在Web数据库、信息抽取和数据挖掘中均有应用。星型模式的数据仓库在实际应用中也存在top-kjoin查询,如有时决策者只想查询星型连接结果中他最感兴趣的k个。然而,现有top-kjoin算法不适合星型模式。为了在星型模式上有效地支持top-kjoin查询,文中提出两类索引并基于这两类索引提出一个适用于星型模式的多路top-kjoin算法。该算法通过采用一个比现有算法更优的上界和一个剪枝策略获得了更高的效率。此外,实验也表明文中的算法比现有算法效率更高。