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

1、過去三十年，計算機硬件技術(shù)以令人驚奇的速度快速持續(xù)發(fā)展，已經(jīng)極大地推動了數(shù)據(jù)庫和信息工業(yè)發(fā)展。借助于技術(shù)的進步，數(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ù)據(jù)建模時，大部分新型應(yīng)用數(shù)據(jù)都可以建模成為高維數(shù)據(jù)(high-dimensional data)，比如圖像數(shù)據(jù)經(jīng)過特征提取后可建模

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

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

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

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

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