高維數(shù)據(jù)新型查詢(xún)處理研究.pdf

1、過(guò)去三十年，計(jì)算機(jī)硬件技術(shù)以令人驚奇的速度快速持續(xù)發(fā)展，已經(jīng)極大地推動(dòng)了數(shù)據(jù)庫(kù)和信息工業(yè)發(fā)展。借助于技術(shù)的進(jìn)步，數(shù)據(jù)以前所未有的速度產(chǎn)生。隨著信息化程度的提高，數(shù)據(jù)已經(jīng)超出了原始關(guān)系數(shù)據(jù)的范疇。大量新型應(yīng)用服務(wù)如基于內(nèi)容的圖片檢索等涌現(xiàn)，這直接使得各種新型應(yīng)用數(shù)據(jù)如超文本、多媒體、交易數(shù)據(jù)等層出不窮。在實(shí)際數(shù)據(jù)建模時(shí)，大部分新型應(yīng)用數(shù)據(jù)都可以建模成為高維數(shù)據(jù)(high-dimensional data)，比如圖像數(shù)據(jù)經(jīng)過(guò)特征提取后可建模

2、成高維空間中的特征向量，超市交易數(shù)據(jù)可建模成高維離散目錄空間中的稀疏向量等。大量高維數(shù)據(jù)在眾多的研究和應(yīng)用領(lǐng)域扮演著越來(lái)越重要的角色。當(dāng)前，對(duì)高維數(shù)據(jù)的查詢(xún)處理研究，已經(jīng)成為了學(xué)術(shù)界和產(chǎn)業(yè)界中一個(gè)重要課題。
　　 本文緊跟當(dāng)前國(guó)內(nèi)外前沿研究，通過(guò)分析已有高維數(shù)據(jù)查詢(xún)處理研究的不足，從實(shí)際應(yīng)用需求出發(fā)，集中于高維不確定數(shù)據(jù)查詢(xún)處理以及高維分布式數(shù)據(jù)相似查詢(xún)處理兩大研究點(diǎn)，面對(duì)其中許多難點(diǎn)包括高維不確定數(shù)據(jù)下的“維度災(zāi)難”、指數(shù)復(fù)雜

3、度的概率值計(jì)算、對(duì)等網(wǎng)絡(luò)下的高維“維度災(zāi)難”等，提出了一系列有效的解決方案，并使用大量實(shí)驗(yàn)驗(yàn)證了所提方法的有效性。
　　 本文的主要研究?jī)?nèi)容分為兩個(gè)部分。第一部分考慮到數(shù)據(jù)不確定性，利用可能世界語(yǔ)義來(lái)建模不確定數(shù)據(jù)，深入研究了高維概率閾值范圍查詢(xún)和高維概率集合包含查詢(xún)。第二部分從數(shù)據(jù)的處理方式出發(fā)，主要研究對(duì)等網(wǎng)絡(luò)分布式環(huán)境下的高維相似查詢(xún)處理。本文的主要貢獻(xiàn)及創(chuàng)新點(diǎn)如下：
　　 (1)本文設(shè)計(jì)了一個(gè)基于數(shù)據(jù)單維映射的高

4、維不確定數(shù)據(jù)概率閾值范圍查詢(xún)處理框架。該框架利用概率分位點(diǎn)作為概率剪枝信息的基本結(jié)構(gòu)，可實(shí)現(xiàn)高性?xún)r(jià)比的概率剪枝?；谠摳咝У募糁夹g(shù)，該框架使用了面向高維不確定數(shù)據(jù)的數(shù)據(jù)映射機(jī)制，并基于該機(jī)制將高維不確定數(shù)據(jù)對(duì)象映射到一維數(shù)據(jù)空間，然后使用已有單維索引結(jié)構(gòu)如B+樹(shù)來(lái)索引高維數(shù)據(jù)對(duì)象。與此相適應(yīng)，該框架使用了高維查詢(xún)轉(zhuǎn)換技術(shù)，將高維概率閾值范圍查詢(xún)轉(zhuǎn)化成為若干個(gè)單維范圍查詢(xún)。同時(shí)，框架還運(yùn)用了一個(gè)衡量分位點(diǎn)剪枝能力的數(shù)學(xué)模型，并借助了高效

5、的分位點(diǎn)選取方法以選取“最優(yōu)”剪枝能力的分位點(diǎn)集合以進(jìn)行映射和索引。實(shí)驗(yàn)證明，與已有的技術(shù)相比，該框架可有效減少查詢(xún)處理代價(jià)，并提高了查詢(xún)效率。
　　 (2)本文提出了面向高維不確定集值數(shù)據(jù)的集合包含查詢(xún)以及設(shè)計(jì)了其高效的處理方法。首先，針對(duì)集值數(shù)據(jù)類(lèi)型，本文提出了不確定模型以及兩種新型概率包含語(yǔ)義：概率集合包含以及期望Jaccard包含。接著，本文提出了面向概率集合包含語(yǔ)義的高效計(jì)算方法，然后，基于所提的概率包含語(yǔ)義，本文進(jìn)一

6、步提出了兩種重要的操作：概率閾值包含查詢(xún)以及概率閾值包含連接，并設(shè)計(jì)了概率閾值集合包含查詢(xún)和概率閾值集合包含連接的處理算法。最后，本文提出了面向期望Jaccard包含的高效計(jì)算方法。實(shí)驗(yàn)結(jié)果反映了所提查詢(xún)處理方法的有效性。
　　 (3)提出了一個(gè)查詢(xún)代價(jià)可調(diào)的、支持高容錯(cuò)的、對(duì)等網(wǎng)絡(luò)下的高維相似查詢(xún)處理框架。該框架使用了一種能概括數(shù)據(jù)信息的簡(jiǎn)單結(jié)構(gòu)，以有效地描述網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)據(jù)的聚類(lèi)信息。該框架基于一種數(shù)據(jù)局部性保存的映射機(jī)制，使用