分段時序查詢優(yōu)化方法研究.pdf

1、時序是一種不同于其它類型的序列數(shù)據(jù)，它通過在離散的時間點(diǎn)取樣形成。它在現(xiàn)實(shí)世界的許多領(lǐng)域廣泛存在，例如：生物醫(yī)學(xué)、金融、氣象學(xué)、自然科學(xué)等。時序處理技術(shù)是一種非常重要而有價值的技術(shù)，已經(jīng)在許多重要領(lǐng)域成功應(yīng)用，例如：傳感器網(wǎng)絡(luò)監(jiān)控、金融數(shù)據(jù)分析、DNA序列分析、移動對象跟蹤以及運(yùn)動捕獲等。然而，時序是一種典型的高維和海量類型數(shù)據(jù)，當(dāng)前時序處理技術(shù)依然面臨很大挑戰(zhàn)。
　　 圍繞時序分段處理方法和分段時序的查詢優(yōu)化技術(shù)，展開了五個方

2、面的研究工作：時序分段相關(guān)處理技術(shù)、基于聚類的靜態(tài)分段時序的查詢優(yōu)化方法、基于分區(qū)的靜態(tài)時序逆向近鄰查詢優(yōu)化方法、動態(tài)分段時序的特定模式查詢優(yōu)化方法、基于網(wǎng)格的動態(tài)分段時序的相關(guān)模式查詢優(yōu)化方法。
　　 由于時序分段在時序處理技術(shù)中具有重要意義，針對缺乏動態(tài)非等長時序分段方法的問題，在詳細(xì)分析了靜態(tài)時序和動態(tài)時序的等長和非等長分段方法的基礎(chǔ)上，利用點(diǎn)對累積近似(Piecewise Aggregate Approximation，

3、PAA)和點(diǎn)對線性近似(Piecewise Linear Approximation，PLA)的增量計算特性，給出了一種多數(shù)據(jù)流的自適應(yīng)分段算法QONSP，并證明了它僅有線性的時間復(fù)雜度。實(shí)驗(yàn)結(jié)果表明，QONSP能對上千個動態(tài)時序進(jìn)行自適應(yīng)分段，通過調(diào)節(jié)參數(shù)可控制分段的精度和平均長度。
　　 為了提高分段之后的靜態(tài)時序的查詢效率，研究了聚類對時序范圍查詢的影響。給出了一種基于等長分段的對稱低邊界函數(shù)SLBS，并證明了它下界于分段

4、時序間的歐氏距離。利用SLBS，給出了基于聚類的靜態(tài)時序范圍查詢優(yōu)化方法RQIC，它同時集成了靜態(tài)查詢優(yōu)化技術(shù)，包括：first-k過濾、三角不等式修剪以及低邊界過濾。實(shí)驗(yàn)結(jié)果表明，RQIC在大部分?jǐn)?shù)據(jù)集上保持了60％以上的修剪能力，且與PLA查詢方法的查詢性能接近。
　　 針對當(dāng)前缺乏基于B+樹索引的靜態(tài)分段時序查詢優(yōu)化方法，研究了分段靜態(tài)時序的逆向近鄰查詢優(yōu)化技術(shù)。通過利用靜態(tài)分段時序具有的普遍適應(yīng)的性質(zhì)：任意兩個不同時序，

5、它們?nèi)绻麖恼w上且(或)在局部趨勢上保持相似，則它們將可能是靠近的對象，對靜態(tài)時序進(jìn)行分區(qū)，并根據(jù)分區(qū)大小和分區(qū)相似度進(jìn)行分區(qū)分裂和合并，將分區(qū)后的時序?qū)ο笏饕揭活wB+樹中。最后，在著名算法iDistance基礎(chǔ)上，給出了基于過濾-精煉框架的查詢優(yōu)化方法RiDistance。實(shí)驗(yàn)結(jié)果表明，RiDistance是有效的，它的查詢效率比序列掃描方法快1～2數(shù)量級。
　　 在對分段之后的動態(tài)時序的查詢處理方面，為了改進(jìn)存在的模式匹配

6、函數(shù)難以適應(yīng)快速數(shù)據(jù)流模式長度和幅度變化的問題，研究了動態(tài)分段時序的特定模式查詢優(yōu)化方法。引入了一種新的模式相似距離函數(shù)，并證明它是一種度量函數(shù)，因而可以利用三角不等式加快模式匹配速度。同時給出了一種快速的模式匹配算法和一種基于統(tǒng)計信息預(yù)測可能出現(xiàn)的模式的概率算法?；诮鹑跀?shù)據(jù)流的實(shí)驗(yàn)結(jié)果表明，給出的模式相似函數(shù)比其他同類函數(shù)更易適應(yīng)幅度偏移和縮放的變化，查詢方法能夠監(jiān)視大部分金融數(shù)據(jù)流中的特定模式。
　　 進(jìn)一步地，針對子序列

7、匹配相關(guān)性查詢的缺點(diǎn)以及缺乏動態(tài)環(huán)境下的主題發(fā)現(xiàn)算法，研究了基于網(wǎng)格技術(shù)的動態(tài)分段時序相關(guān)性查詢優(yōu)化方法。引入了能適應(yīng)長度和幅度的變化的局部模式相似函數(shù)SDD，并證明了它滿足度量函數(shù)特性。利用前述的動態(tài)分段技術(shù)和SDD，給出了基于網(wǎng)格投影技術(shù)的相關(guān)性模型MCALP，它能夠監(jiān)控多數(shù)據(jù)流中的最小相關(guān)(交叉相關(guān))和最大相關(guān)(主題相關(guān))，并證明了它的兩個提高查詢效率的性能定理。該模型包括監(jiān)視最小相關(guān)的查詢方法MCPDG和P-主題查詢方法PMDG