海量信息的極大點(diǎn)查詢算法優(yōu)化及應(yīng)用研究.pdf

1、近年來，海量的信息已經(jīng)變得無處不在，面對(duì)龐大的數(shù)據(jù)量，如何有效及時(shí)的對(duì)數(shù)據(jù)進(jìn)行處理是目前面臨的一個(gè)重要挑戰(zhàn)，否則很多數(shù)據(jù)就會(huì)失去它應(yīng)有的價(jià)值。幸運(yùn)的是極大點(diǎn)查詢就是一個(gè)有效的數(shù)據(jù)處理工具，可以幫助人們快速的從大量的信息中找到感興趣的內(nèi)容。極大點(diǎn)查詢產(chǎn)生于計(jì)算幾何，由于其良好的應(yīng)用前景，其在多目標(biāo)優(yōu)化、數(shù)據(jù)庫(kù)等領(lǐng)域出現(xiàn)了越來越多的各種應(yīng)用。但面臨的問題是這些應(yīng)用常常需要巨大的計(jì)算資源，使得傳統(tǒng)的極大點(diǎn)查詢算法很難有效的使用。針對(duì)這個(gè)問題，

2、論文主要對(duì)極大點(diǎn)查詢算法的性能優(yōu)化和應(yīng)用方面進(jìn)行了研究。
　　 論文首先對(duì)目前極大點(diǎn)查詢算法的研究現(xiàn)狀進(jìn)行了綜述。從內(nèi)存儲(chǔ)算法和外存儲(chǔ)算法兩個(gè)方面，全面分析了已有的極大點(diǎn)查詢算法。在此基礎(chǔ)上提出基于體積優(yōu)先策略的極大點(diǎn)查詢算法，設(shè)計(jì)了一種線性I/O次數(shù)的極大點(diǎn)查詢外存儲(chǔ)算法。將設(shè)計(jì)的兩種算法結(jié)合應(yīng)用到數(shù)據(jù)庫(kù)的Skyline查詢處理和金融領(lǐng)域的資產(chǎn)配置問題中，取得了良好的實(shí)驗(yàn)效果。本論文的研究工作和創(chuàng)新主要包括以下4個(gè)方面：

3、>　　 (1)構(gòu)造了一種基于體積優(yōu)先策略的極大點(diǎn)查詢算法。通過實(shí)驗(yàn)發(fā)現(xiàn)算法的效率高于Bently等人提出的經(jīng)典的MTF算法。通過理論證明，算法的時(shí)間復(fù)雜度以極高的概率保持線性時(shí)間。部分解決了沒有線性時(shí)間復(fù)雜度的極大點(diǎn)查詢算法這一公開問題。其高維空間上的理論證明對(duì)極大點(diǎn)查詢算法在高維空間上的復(fù)雜性分析提供了有益的參考。
　　 (2)當(dāng)數(shù)據(jù)超過內(nèi)存的限制時(shí)，經(jīng)典的算法往往無法很好的處理這些數(shù)據(jù)，近年來算法研究已經(jīng)關(guān)注于處理海量數(shù)據(jù)

4、的外存儲(chǔ)算法。這時(shí)算法的效率通常以內(nèi)外存之間數(shù)據(jù)輸入輸出次數(shù)(I/O次數(shù))來衡量。對(duì)于極大點(diǎn)查詢問題而言，目前還沒有線性I/O次數(shù)的外存儲(chǔ)算法。對(duì)此，本論文提出了一種針對(duì)海量數(shù)據(jù)的線性I/O次數(shù)的極大點(diǎn)查詢算法。算法針對(duì)獨(dú)立同分布數(shù)據(jù)，利用了極大點(diǎn)的數(shù)目概率特性。并通過實(shí)驗(yàn)和理論證明了算法的有效性。
　　 (3)數(shù)據(jù)庫(kù)Skyline查詢處理是近年來數(shù)據(jù)庫(kù)查詢領(lǐng)域的研究熱點(diǎn)，極大點(diǎn)問題與Skyline查詢有著天然的聯(lián)系。本論文將設(shè)

5、計(jì)的算法結(jié)合應(yīng)用到數(shù)據(jù)庫(kù)的Skyline查詢處理中，取得了良好的實(shí)驗(yàn)效果，使得整個(gè)算法的內(nèi)存時(shí)間復(fù)雜度和I/O復(fù)雜度均達(dá)到了線性時(shí)間。
　　 (4)金融領(lǐng)域存在海量的數(shù)據(jù)信息，如何從這些數(shù)據(jù)中的找到有價(jià)值的信息指導(dǎo)投資決策是在現(xiàn)代投資理論的重要問題之一。本論文在嘗試?yán)脴O大點(diǎn)查詢指導(dǎo)投資決策的過程中，在研究資產(chǎn)類別的歷史表現(xiàn)時(shí)發(fā)現(xiàn)了一些有趣的經(jīng)濟(jì)現(xiàn)象，并首次系統(tǒng)的提出了一種基于復(fù)雜網(wǎng)絡(luò)社團(tuán)結(jié)構(gòu)的股票分類方法和利用極大點(diǎn)查詢進(jìn)行投