PBASQ：一種基于劃分的Skyline查詢算法.pdf

1、Skyline查詢作為數(shù)據(jù)挖掘的重要分支，廣泛應用于多標準決策、可視化和用戶參考查詢等領域。近年來，在數(shù)據(jù)庫和信息檢索研究領域，有效計算Skyline的問題已經(jīng)引起國內外研究者的廣泛關注?，F(xiàn)有的技術主要是對數(shù)據(jù)實行批處理和在線處理；采用的劃分方法主要為物理劃分或根據(jù)分段的維值進行劃分，并沒有對被劃分的各部分間所固有的特性進行深入分析。 本文在數(shù)據(jù)劃分方面進行了探討。首先在NN算法的基礎上，深入分析了被NN點劃分后各區(qū)域間的支配關

2、系，研究了相關性質，發(fā)現(xiàn)并證明了被全局NN點劃分一次后，區(qū)域間具有單向的不完全支配關系；其次利用上述性質并結合可應用于任意維空間的BNL算法提出了一種基于劃分的PBASQ算法。該算法由于實現(xiàn)了有效的過濾和減少了那些不具有支配關系區(qū)域間的支配檢查，節(jié)省了內存空間的占用，提高了執(zhí)行效率。同時，該算法還具有傳輸Skyline結果的實時性，當全部的Skyline點還未獲得前，全局的NN點作為第一個Skyline點可以立刻返回給用戶，并且隨著時間