[發(fā)明專利]適合數(shù)據(jù)流環(huán)境的多子空間PARETO查詢信息處理方法

無效

• 申請(qǐng)?zhí)枺?/td>: 201010564257.1
• 申請(qǐng)日: 2010-11-26
• 公開（公告）號(hào): CN102479209A
• 公開（公告）日: 2012-05-30
• 發(fā)明（設(shè)計(jì)）人: 黃震華;向陽;陳千;王棟;張波;劉立平;伍申申
• 申請(qǐng)（專利權(quán)）人: 同濟(jì)大學(xué)
• 主分類號(hào): G06F17/30
• 分類號(hào): G06F17/30
• 代理公司: 上海科盛知識(shí)產(chǎn)權(quán)代理有限公司 31225
• 代理人: 趙繼明

技術(shù)領(lǐng)域

本發(fā)明涉及一種PARETO查詢信息處理方法，尤其是涉及一種適合數(shù)據(jù)流環(huán)境的多子空間PARETO查詢信息處理方法。

背景技術(shù)

S.Borzsonyi等人首次將全空間PARETO查詢計(jì)算引進(jìn)到數(shù)據(jù)庫領(lǐng)域進(jìn)行優(yōu)化控制，并針對(duì)靜態(tài)數(shù)據(jù)集設(shè)計(jì)了兩個(gè)可行的查詢算法：BNL算法以及DC算法。其中BNL算法在多項(xiàng)式時(shí)間復(fù)雜度內(nèi)找出所有全空間PARETO對(duì)象，而DC算法使用遞歸分區(qū)的方法來獲取查詢結(jié)果。J.Chomicki等人在BNL算法的基礎(chǔ)上發(fā)明了一種先進(jìn)行對(duì)象排序，再進(jìn)行比較的查詢方法SFS，SFS算法能夠有效減少BNL算法中對(duì)象間比較的次數(shù)，然而，它增加了排序的時(shí)間開銷。P.Godfrey等人從理論上給出在均勻分布情況下，BNL算法、DC算法以及SFS算法的時(shí)間開銷，并提出一種基于外部排序的可行方法LESS，算法LESS的時(shí)間復(fù)雜度可降為對(duì)數(shù)級(jí)別。D.Kossmann等人給出一種基于R-樹索引的計(jì)算方法NN，NN算法遞歸搜索區(qū)域的最近鄰點(diǎn)，并且通過區(qū)域剪枝技術(shù)刪除被最近鄰點(diǎn)支配的所有對(duì)象，從而提高了獲取查詢結(jié)果的速度。D.Papadias等人指出NN算法缺陷，并提出一種基于排序R-樹節(jié)點(diǎn)的方法BBS，BBS算法克服了NN算法冗余比較R-樹節(jié)點(diǎn)的不足，而且比NN算法具有更強(qiáng)的剪枝能力。以上的PARETO查詢算法均是針對(duì)全空間的、靜態(tài)的數(shù)據(jù)集，也就是說，這些算法只能優(yōu)化企業(yè)固定數(shù)據(jù)集上的全空間。

Y.Tao等人首次研究不同子空間上的PARETO查詢，并給出一種計(jì)算任一子空間上PARETO對(duì)象的方法SUBSKY。SUBSKY算法首先通過k-mean聚類算法將數(shù)據(jù)集劃分為m個(gè)類，然后對(duì)于每個(gè)類c1，以c1中的核心點(diǎn)為參照點(diǎn)進(jìn)行計(jì)算任一子空間上的PARETO對(duì)象。然而，SUBSKY算法計(jì)算每一個(gè)子空間上的PARETO對(duì)象時(shí)，需要掃描絕大部分?jǐn)?shù)據(jù)集，而且對(duì)所有m個(gè)類中的對(duì)象均計(jì)算完成之后才能返回第一個(gè)PARETO對(duì)象，因此，SUBSKY算法的效率較低。另一方面，當(dāng)數(shù)據(jù)集頻繁更新時(shí)，SUBSKY算法需要使用k-mean聚類算法重新劃分?jǐn)?shù)據(jù)集，并且需要維護(hù)每個(gè)類中的核心到該類中所有對(duì)象的距離，因此，SUBSKY算法無法應(yīng)用于快速數(shù)據(jù)流環(huán)境中。X.Tian等人構(gòu)造了一種壓縮的PARETO立方體的層次數(shù)據(jù)結(jié)構(gòu)CSC，并在CSC的基礎(chǔ)上設(shè)計(jì)了一個(gè)有效處理任一子空間上PARETO查詢的方法QueryCSC；對(duì)于子空間U上的PARETO查詢，假定U在CSC中處于第i層，那么QueryCSC算法搜索第1到i-1層中所有壓縮PARETO立方體實(shí)例內(nèi)的數(shù)據(jù)對(duì)象來返回U上的PARETO查詢；不難看出，QueryCSC算法需要訪問指數(shù)級(jí)個(gè)壓縮PARETO立方體實(shí)例，因此當(dāng)子空間個(gè)數(shù)增多時(shí)，QueryCSC算法的效率顯著下降。另一方面，當(dāng)數(shù)據(jù)集頻繁更新時(shí)，QueryCSC算法需要更新指數(shù)級(jí)個(gè)數(shù)的壓縮PARETO立方體實(shí)例，因此，QueryCSC算法也無法應(yīng)用于快速數(shù)據(jù)流環(huán)境中。Y.Tao等人首次考慮在數(shù)據(jù)流環(huán)境下維護(hù)全空間的PARETO對(duì)象，并以R-樹索引為基礎(chǔ)，設(shè)計(jì)了兩個(gè)基于區(qū)域查詢技術(shù)的樸質(zhì)維護(hù)方法：I-Eager算法和I-Lazy算法。對(duì)于新到達(dá)的對(duì)象p，I-Eager算法搜索p受支配區(qū)域中的所有對(duì)象來標(biāo)識(shí)p成為全空間PARETO對(duì)象的時(shí)間點(diǎn)，并刪除p支配區(qū)域中的所有對(duì)象；而I-Lazy算法搜索p受支配區(qū)域時(shí)，如果遇到有一個(gè)點(diǎn)支配p就退出搜索，并將p加入到非全空間PARETO對(duì)象集合中。對(duì)于過期的對(duì)象r，I-Eager算法刪除r，同時(shí)將在該時(shí)刻成為全空間PARETO對(duì)象的所有對(duì)象加入到全空間PARETO對(duì)象集合中；而I-Eager算法先判斷r是否為全空間PARETO對(duì)象，如果是則刪除它，否則推遲到下一個(gè)全空間PARETO對(duì)象過期時(shí)再刪除它。由于Y.Tao等人沒有給出任何優(yōu)化技術(shù)來提高I-Lazy和I-Eager這兩個(gè)算法區(qū)域搜索的效率，因此，它們的維護(hù)效率都比較低。另一方面，Y.Tao等人沒有考慮任一子空間上的PARETO查詢問題，以及同時(shí)優(yōu)化多個(gè)子空間上的PARETO查詢問題。如果使用I-Lazy和I-Eager這兩個(gè)算法來計(jì)算任一子空間上的PARETO對(duì)象，那么需要對(duì)每個(gè)子空間使用一次維護(hù)算法，這是不現(xiàn)實(shí)的。

發(fā)明內(nèi)容

本發(fā)明的目的就是為了克服上述現(xiàn)有技術(shù)存在的缺陷而提供一種適合數(shù)據(jù)流環(huán)境的多子空間PARETO查詢信息處理方法。

本發(fā)明的目的可以通過以下技術(shù)方案來實(shí)現(xiàn)：

一種適合數(shù)據(jù)流環(huán)境的多子空間PARETO查詢信息處理方法，其特征在于，包括以下步驟：

1)持續(xù)維護(hù)模塊在每一個(gè)時(shí)間戳點(diǎn)對(duì)三類非偽對(duì)象數(shù)據(jù)進(jìn)行區(qū)分并維護(hù)處理；