多數(shù)據(jù)類型的數(shù)據(jù)流查詢處理及優(yōu)化.pdf

1、數(shù)據(jù)流作為一種新型的數(shù)據(jù)模型，在許多應(yīng)用，如：網(wǎng)絡(luò)流量管理、金融數(shù)據(jù)分析、電子商務(wù)、交通治理、網(wǎng)站信息的發(fā)布和訂閱、版權(quán)保護(hù)以及環(huán)境和工業(yè)監(jiān)控中扮演著重要的角色?；跀?shù)據(jù)流模型的查詢處理以及優(yōu)化技術(shù)也得到了廣泛的研究。數(shù)據(jù)流無(wú)限、快速的特性和數(shù)據(jù)流應(yīng)用系統(tǒng)資源有限、要求快速響應(yīng)的特點(diǎn)打破了傳統(tǒng)查詢處理技術(shù)的很多假設(shè)，需要我們重新研究基礎(chǔ)的數(shù)據(jù)庫(kù)查詢處理技術(shù)。
　　 由于數(shù)據(jù)流是動(dòng)態(tài)的，數(shù)據(jù)流上的查詢通常是連續(xù)、大量的。而系統(tǒng)只能

2、處理或者保存與查詢相關(guān)的數(shù)據(jù)。因此對(duì)查詢的特性進(jìn)行統(tǒng)計(jì)分析并設(shè)計(jì)有效的索引結(jié)構(gòu)來(lái)將查詢組織起來(lái)，是查詢優(yōu)化的關(guān)鍵所在。同時(shí)，眾多應(yīng)用所面向的數(shù)據(jù)類型是多種多樣的。而在數(shù)據(jù)流系統(tǒng)查詢處理及優(yōu)化的研究中，大多面向結(jié)構(gòu)化和半結(jié)構(gòu)化的數(shù)據(jù)對(duì)象。因此，本文針對(duì)各種數(shù)據(jù)類型(結(jié)構(gòu)化數(shù)據(jù)集中和分布式、多媒體數(shù)據(jù)以及RDF圖數(shù)據(jù))上的連續(xù)查詢問題設(shè)計(jì)新穎的系統(tǒng)框架和有效的優(yōu)化算法。同時(shí)，本文還對(duì)每個(gè)所提出的技術(shù)及其相關(guān)工作進(jìn)行大量、深入的實(shí)驗(yàn)分析，實(shí)驗(yàn)

3、結(jié)果都充分證明了這些技術(shù)的有效性和高效性。本文主要貢獻(xiàn)如下：
　　 1.設(shè)計(jì)了有效且準(zhǔn)確的集中式結(jié)構(gòu)化數(shù)據(jù)k-NN監(jiān)控方案：有效的處理數(shù)據(jù)流上連續(xù)的k最近鄰(k-NN)查詢?cè)谠S多應(yīng)用領(lǐng)域都是一個(gè)重要的問題。通常并非數(shù)據(jù)流上所有數(shù)據(jù)都可以存放在內(nèi)存中。因此，大多數(shù)已存在的解決方案僅把有代表性的數(shù)據(jù)放入索引中，而丟棄一些數(shù)據(jù)。這些解決方案都是近似的。在本文中，通過對(duì)查詢而非流數(shù)據(jù)建立索引結(jié)構(gòu)，將與查詢相關(guān)的數(shù)據(jù)存放在Skyline數(shù)

4、據(jù)結(jié)構(gòu)中以及有效的延遲技術(shù)來(lái)處理結(jié)構(gòu)化數(shù)據(jù)準(zhǔn)確的k-NN查詢。
　　 2.提出一個(gè)新穎的基于劃分的連接操作模式PMJoin，以優(yōu)化分布式結(jié)構(gòu)化數(shù)據(jù)的連接查詢計(jì)劃、減少傳輸代價(jià)：數(shù)據(jù)流的應(yīng)用中，數(shù)據(jù)源通常分散在不同地方。因此，處理多條不同數(shù)據(jù)源數(shù)據(jù)流連接操作查詢的時(shí)候，不可避免的產(chǎn)生巨大的數(shù)據(jù)傳輸代價(jià)。對(duì)于連續(xù)的連接查詢來(lái)說(shuō)，如果不進(jìn)行查詢優(yōu)化處理，寶貴的帶寬資源會(huì)被大量浪費(fèi)。本文提出一個(gè)啟發(fā)式的算法來(lái)合理安排多數(shù)據(jù)流連續(xù)查詢計(jì)劃

5、，使得系統(tǒng)總體傳輸代價(jià)最小化。
　　 3.設(shè)計(jì)了基于數(shù)據(jù)流算法的多媒體數(shù)據(jù)流上拷貝檢測(cè)查詢處理和優(yōu)化算法：數(shù)字視頻被越來(lái)越廣泛的應(yīng)用在眾多的多媒體應(yīng)用中，并通常以視頻流的形式被廣播和傳送。為了從內(nèi)容上來(lái)進(jìn)行版權(quán)管理，連續(xù)監(jiān)控高速、持續(xù)的視頻流上的視頻拷貝問題得到越來(lái)越多的關(guān)注。有效的數(shù)據(jù)流算法是處理大量連續(xù)拷貝檢測(cè)查詢所必需的。本章首先定義了在視頻被改動(dòng)后仍然有效的視頻序列的相似性。同時(shí)采用基于哈希的視頻梗概(Sketch)來(lái)有

6、效的計(jì)算視頻序列的相似性。然后，設(shè)計(jì)了巧妙的位向量簽名(Signature)來(lái)達(dá)到CPU和內(nèi)存兩方面優(yōu)化的目標(biāo)。最后，為了同時(shí)處理多個(gè)連續(xù)查詢，設(shè)計(jì)了一個(gè)索引結(jié)構(gòu)來(lái)組織查詢序列。
　　 4.基于圖特性的語(yǔ)義網(wǎng)上靜態(tài)和流式RDF圖數(shù)據(jù)查詢處理：有效的RDF查詢處理正在成為一個(gè)把語(yǔ)義網(wǎng)技術(shù)(Semantic Web)應(yīng)用到真實(shí)世界的重要因素。正因?yàn)槿绱耍S多研究工作致力于怎樣用特殊的模式在關(guān)系數(shù)據(jù)庫(kù)中進(jìn)行存儲(chǔ)和查詢。本文提出一個(gè)在三

7、元組方式下存儲(chǔ)、索引和查詢RDF數(shù)據(jù)的新穎模式。該模式優(yōu)化兩部分查詢處理：對(duì)于靜態(tài)數(shù)據(jù)的即時(shí)查詢和對(duì)流式RDF數(shù)據(jù)的連續(xù)查詢。主要?jiǎng)?chuàng)新點(diǎn)在于把RDF數(shù)據(jù)的圖形特性考慮進(jìn)來(lái)，有助于減少在垂直數(shù)據(jù)庫(kù)里面連接操作的代價(jià)。在靜態(tài)查詢優(yōu)化算法的基礎(chǔ)上再提出RDF流上連續(xù)查詢優(yōu)化策略：(1)根據(jù)連續(xù)查詢的特征，對(duì)流進(jìn)系統(tǒng)的RDF三元組進(jìn)行分組。(2)每個(gè)查詢維護(hù)相關(guān)的記錄列表。(3)每個(gè)連續(xù)查詢定期的在相關(guān)數(shù)據(jù)組中進(jìn)行查詢處理，進(jìn)而提高了查詢效率并