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

A Multiple Top-k Join Algorithm Based on the Star Schema

作　　者：曹立新[1] 高宏[1] 

机构地区：[1]哈尔滨工业大学计算机科学与技术学院,哈尔滨150001

出　　处：《计算机学报》2011年第10期1926-1935,共10页Chinese Journal of Computers

基　　金：国家自然科学基金(60933001)资助~~

摘　　要：top-kjoin查询返回用户最感兴趣的k个连接结果.近来top-kjoin已经成为一个重要的研究课题,且在Web数据库、信息抽取和数据挖掘中均有应用.星型模式的数据仓库在实际应用中也存在top-kjoin查询,如有时决策者只想查询星型连接结果中他最感兴趣的k个.然而,现有top-kjoin算法不适合星型模式.为了在星型模式上有效地支持top-kjoin查询,文中提出两类索引并基于这两类索引提出一个适用于星型模式的多路top-kjoin算法.该算法通过采用一个比现有算法更优的上界和一个剪枝策略获得了更高的效率.此外,实验也表明文中的算法比现有算法效率更高.Top-k join query returns k join results that users are most interested in.Top-k join has become one of the main research issues recently,and it＇s dominant in many emerging applications,e.g.,web databases,information retrieval and data mining.Top-k join query also exists in data warehouse based on the star schema in practical application.For example,sometimes just the top-k join results that the decision maker is most interested in are desirable.However,the current existing algorithms aren＇t suitable for the data warehouse based on the star schema.In order to efficiently support top-k join query on star schema,we propose two kinds of indices and a multiple top-k join algorithm that is suitable for star schema based on these indices.By using a tighter upper bound than current existing algorithms and a pruning strategy,the algorithm is more efficient than the current existing algorithms.Furthermore,the experiment also shows that the algorithm is more efficient than the current existing algorithm.

关 键 词：数据仓库 星型模式 星型连接 TOP-K 多路top-k JOIN算法 

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