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

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

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

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

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

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

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

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