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

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

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