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

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

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

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

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

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

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

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