數(shù)據(jù)流上的相似性查詢及優(yōu)化.pdf

1、自二十世紀(jì)末,隨著數(shù)據(jù)庫技術(shù)在諸如網(wǎng)絡(luò)路由、傳感器網(wǎng)絡(luò)、股票分析等領(lǐng)域的深入應(yīng)用,人們發(fā)現(xiàn)傳統(tǒng)的DBMS技術(shù)在處理這些速度快、規(guī)模大、持續(xù)時間長的數(shù)據(jù)時遇到了很大的困難。于是一種新型的數(shù)據(jù)模型-數(shù)據(jù)流被發(fā)展起來并得到廣泛研究。數(shù)據(jù)流模型的研究核心是設(shè)計高效的單遍掃描算法以及概要數(shù)據(jù)結(jié)構(gòu),在有限的內(nèi)存空間內(nèi)盡量多的保留數(shù)據(jù)流信息。隨著對數(shù)據(jù)流的深入研究,許多傳統(tǒng)的數(shù)據(jù)庫問題如頻繁項挖掘、關(guān)聯(lián)規(guī)則挖掘、topk查詢、聚類等都被擴展到數(shù)據(jù)流上

2、。本文著重研究基于數(shù)據(jù)流的相似性查詢及其優(yōu)化問題,因為它在金融數(shù)據(jù)分析、網(wǎng)絡(luò)監(jiān)控、異常檢測等領(lǐng)域具有極其重要的作用,而且由于數(shù)據(jù)流的持續(xù)更新的特性,傳統(tǒng)的基于靜態(tài)時間序列的相似性查詢算法不再適用。本文通過詳細(xì)對比在相似性問題中常用的各種距離的優(yōu)劣,引入k-DTW距離作為相似度的衡量標(biāo)準(zhǔn),在保持準(zhǔn)確度的前提下提高了計算速度;為了進一步提高匹配速度,我們使用MPAA技術(shù)對數(shù)據(jù)流進行降維,并且證明該技術(shù)可以保持k-DTW距離的下界,使得后續(xù)的