基于星型模式的top-k join算法研究.pdf

1、top-k join查詢返回用戶最感興趣的k個(gè)連接結(jié)果。近來top-k join已經(jīng)成為一個(gè)重要的研究課題，其在Web數(shù)據(jù)庫(kù)，信息抽取和數(shù)據(jù)挖掘中均有應(yīng)用。星型模式的數(shù)據(jù)倉(cāng)庫(kù)在實(shí)際應(yīng)用中也存在top-k join查詢，如有時(shí)決策者只想查詢星型連接結(jié)果中他最感興趣的k個(gè)。然而，現(xiàn)有top-k join算法不適合星型模式。為了在星型模式上有效地支持top-k join查詢，本文提出兩種索引并基于這兩種索引提出一個(gè)適用于星型模式的多路top-

2、k join算法MTJS。該算法通過采用一個(gè)比現(xiàn)有算法更優(yōu)的上界和一個(gè)剪枝策略獲得了更高的效率。此外，實(shí)驗(yàn)也表明該算法比現(xiàn)有算法效率更高。
　　獲取精確的top-k join查詢結(jié)果的代價(jià)是較高的，而且有時(shí)決策者希望犧牲top-k join查詢結(jié)果的精確性來縮短查詢的執(zhí)行時(shí)間和資源消耗。更重要的是，我們發(fā)現(xiàn)現(xiàn)有的近似top-k join算法因沒有充分考慮星型模式的固有特點(diǎn)而不適合星型模式，因而本文提出一個(gè)基于星型模式的近似多路to