基于四叉樹的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)行深入分析。 在本文中，我們首先分析了四叉樹索引機(jī)制的結(jié)構(gòu)特點(diǎn)，然后根據(jù)其特點(diǎn)系統(tǒng)地提出了一種基于四叉樹的新

2、的Skyline查詢方法--QBSQ算法。QBSQ算法利用四叉樹的結(jié)構(gòu)特性，動(dòng)態(tài)的對數(shù)據(jù)集進(jìn)行劃分，并且在構(gòu)造樹的過程中刪除被樹中結(jié)點(diǎn)支配的數(shù)據(jù)點(diǎn)，同時(shí)還深入研究了劃分后各區(qū)域間以及數(shù)據(jù)點(diǎn)之間的支配關(guān)系，通過分析可知某些區(qū)域之間不存在支配關(guān)系，由此可減少區(qū)域間及數(shù)據(jù)點(diǎn)之間不必要的支配檢查。該算法由于實(shí)現(xiàn)了有效的過濾和減少了不具有支配關(guān)系的區(qū)域內(nèi)數(shù)據(jù)點(diǎn)之間的支配檢查，提高了執(zhí)行效率。此外，還針對QBSQ算法在高維數(shù)據(jù)空間上存在的不足提出了