基于線性散列索引的時(shí)間序列近似查詢研究.pdf

1、時(shí)間序列作為時(shí)態(tài)數(shù)據(jù)中一種很重要的數(shù)據(jù)類型，由許多領(lǐng)域中的應(yīng)用持續(xù)地產(chǎn)生。同時(shí)它也蘊(yùn)含著豐富的有價(jià)值的信息，這些信息可以給管理者提供決策支撐并對(duì)生產(chǎn)生活提供有效的預(yù)測(cè)。因此，如何處理好這些時(shí)間序列是國(guó)內(nèi)外研究的熱點(diǎn)問(wèn)題。
　　由于時(shí)間序列具有復(fù)雜性、海量性等特點(diǎn)，這些特點(diǎn)決定了不能直接在原始時(shí)間序列上進(jìn)行索引創(chuàng)建和相似性查詢等操作。所以在進(jìn)行這些操作之前就要對(duì)時(shí)間序列進(jìn)行預(yù)處理，本文在預(yù)處理部分提出了一種新的規(guī)范化方法用于時(shí)間序列

2、的離散化表示。
　　針對(duì)時(shí)間序列近似查詢的時(shí)間復(fù)雜度高的問(wèn)題，本文提出了一種基于線性散列的時(shí)間序列索引技術(shù)。在索引的創(chuàng)建過(guò)程中使用的是已經(jīng)離散化表示的時(shí)間序列，這個(gè)離散化的結(jié)果不是單一的時(shí)間序列的表示，它表達(dá)了一組具有相同離散化結(jié)果的時(shí)間序列的集合。這樣執(zhí)行近似查詢得出的結(jié)果是一個(gè)具有相同離散化結(jié)果的時(shí)間序列集合。本文提出的線性散列索引技術(shù)的好處就是該索引會(huì)以很低的時(shí)間復(fù)雜度執(zhí)行時(shí)間序列近似查詢。
　　時(shí)間序列的近似查詢包括

3、直接查詢和查詢結(jié)果精煉兩個(gè)過(guò)程。給定一個(gè)時(shí)間序列的查詢Q，通過(guò)線性散列索引返回一個(gè)BSF(Best-so-far)結(jié)果集，這個(gè)結(jié)果集可以看作是查詢實(shí)例Q的一個(gè)直接查詢的結(jié)果。然后從BSF結(jié)果集中對(duì)查詢結(jié)果進(jìn)一步精煉而得到精煉結(jié)果集(Refine Value，RV)，RV結(jié)果集就是最終近似查詢的結(jié)果。查詢結(jié)果精煉過(guò)程中采用K近鄰與改進(jìn)的下界距離相結(jié)合的方式，進(jìn)一步縮小查詢范圍，實(shí)現(xiàn)查詢結(jié)果精煉?；谝陨侠碚撛O(shè)計(jì)并實(shí)現(xiàn)了時(shí)間序列的近似查詢系