master.dvi

Size: px

Start display at page:

Download "master.dvi"

ゆきひらすえたけ
5 years ago
Views:

1 TC S -TR -B TC S Technical Report Master Thesis: Efficient Algorithms for Complex Time-Series Pattern Matching Based on Bit-Parallel Method by Tomoya Saito Division of Computer Science Report Series B July 15, 2008 Hokkaido University Graduate School of Information Science and Technology saito@ist.hokudai.ac.jp Phone: Fax:

3 14 9 July 15, O( 1 mn) d O( 1 mn log m) d =2 O( 1 mn log v) m; v; n; 1:5 ο [2, 4, 10, 11, 19, 20] 1: d geometric time-series query d 2 1

4 2 Tomoya Saito 2: ß 1 = q 1 q 2 q 3 q 4 q 5 here q 1 =(x>2) and q 2 =(x<5) and q 3 =(x>2 ^ x<7) and q 4 =(x<5)= q 2 and q 5 =(x<3): 3: ß Harada [6, 7] Sadri-Zaniolo [13] 1 3 KMP [8, 5, 18] BM [3, 5, 18] L2R R2L 1.4 [12] d BPS NFA( ) Shift-And [12] O(mn) BPS d ~x P (~x) =f q 2 Q j q(~x) =1g Q d 1. 1 O(1) O(1) O( 1 m2 n) 1-HT-naive 2. 1 O( 1 cm2 ) O( 1 cm) O( 1 mn) 1-HT-table 3. 1 O( 1 m3 ) O( 1 m2 ) O( 1 mn log m) 1-HTbin 4. d O( 1 dm2 ) O( 1 dm2 ) O( 1 dmn log m) d-ht-bin 5. d O(1) O(1) O( 1 m2 n) d-ht-naive 6. d =2 O( 1 m2 ) O( 1 m2 ) O( 1 mn log m) d-ht-slab

5 Master Thesis: Efficient Algorithms for Complex Time-Series Pattern Matching Based on Bit-Parallel Method 3 7. d =2 O( 1 m2 N 2 ) O( 1 m2 N 2 ) O(T fl + 1 mn) d-ht-bucket m = jjßjj ß n = jsj S N T fl BPS KMP BM [12] L2R [7, 13] R2L [7] BPS DEWS'07[17] SWOD'07[14] 5 FIT'07[15] 6 DEWS'08[16] 2 d 2.1 RAM [1, 12] m>0 b m 1 b 0 2 f0; 1g m m < 0 j & ο 0» n» m 1 X n X << n 0 m 0 1 << i =0 m i 10 i 1 i 1 S f0;:::;m 1g Bit(S) 2f0; 1g m S 1 =8 X = ;Y = : X j Y = : X & Y = : X = : X << 1 = : 0 8 = : 1 = << 4 = S = f0; 2; 3; 5g : Bit(S) = =32 =64 O(1) m> O(d m e) [1, 12]

6 4 Tomoya Saito 2.2 d N = f0; 1; 2;:::g R A Λ A [9] d R d d R d ~s =(x 1 ;:::;x d ) 2 R d x dom(x) dom(x) =R d d S =(~s 1 ;:::;~s n ) 2 (R d ) Λ 2 S 1 = (1; 5; 3; 5; 4; 2; 4; 1; 2; 2) 2 (R 1 ) Λ S 2 = ((0; 0); (1; 1); (2; 0); ( 1; 1); (0; 1); ( 1; 0)) 2 (R 2 ) Λ 6 2 d 1. 2 ~p = (x; y) x y 2. ~p = (x; y; z; info) x; y; z 3 info 3. ~p =(x 1 ;:::;x d ) 4. ~p =(x 1 ;y 1 ;z 1 ; 1 ;ffi 1 ;ψ 1 ;:::;x 19 ;y 19 ;z 19 ; 19 ;ffi 19 ;ψ 19 ) 19 i x i ;y i ;z i 2 R 3 i ;ffi i ;ψ i 2 ( ß; +ß] 2.3 d d>0 d R d q : R d!f0; 1g d R d f ~s 2 R d j q(~s) =1g R d q jjqjj d C d geo C C P = fq 1 ;:::;q m g d ~s ~s P ~s P P (~s) =f q 2 P j q(~s) =1g q i i 1 C C P = fq 1 ;:::;q m g d ~s P ~s P (~s) m Bit(P (~s)) 2f0; 1g m 2 C m ß ß =(q 1 ;:::;q m ) 2 C Λ 1» i» m q i 2 C C m P ß jßj = m ß m jjßjj = i=1 jjq i jj m ß = (q 1 ;:::;q m ) n d S = (~s 1 ;:::;~s n ) 2 (R d ) Λ 1» j» n q 1 (~s j ) ^ ^q m (~s j+m 1 ) 3 C d C ß 2 C d S =(~s 1 ;:::;~s n ) 2 (R d ) Λ S ß m = jßj v = jjßjj n = jsj Ω(v + n)

7 Master Thesis: Efficient Algorithms for Complex Time-Series Pattern Matching Based on Bit-Parallel Method d R d (x 1 ;:::;x d ) p = (c 1 ;:::;c d ) 2 R d i x i c i (atomic inequality) ` = (ax» c) a 2f+1; 1g, c 2 R (linear inequality) ` (a 1 x a d x d» c) a 1 ;:::;a d ;c 2 R C 1 ieq;int C1 ieq;int q q = `1 ^ ^`k (1» i» k) `i =(a i x» c i ) a i 2f+1; 1g, c i 2 R dom(x) =N 1 C 1 ieq;real C1 ieq;real q q = `1 ^ ^`k (1» i» k) `i =(a i x» c i ) a i 2f+1; 1g, c i 2 R dom(x) =R 1 C 1 ieq;int C1 ieq;real x 2 q =(a 1 x» c 1 ) ^ (a 2 x» c 2 ) x = c 2 (x» c)^(x c) C 1 ieq;int C 1 ieq;real d d d C d ieq;real C d ieq;real q q = `1 ^ ^`1 1 k(d) ^ ^`d1 ^ ^`d k(d) 1» i» d; 1» j» k(d) `ij i x i `ij =(ai j x i» c i j ) ai j 2f+1; 1g ci j 2 R dom(x i )=R ; d d d C d lin C d linear q d q = `1 ^ ^`k (k» 0) ` =(a 1 x 1 + +a d x d» c) d a 1 ; ;a d ;c 2 R dom(x i )R 4 ffl box(a 1 ;b 1 ;a 2 ;b 2 ) = [a 1 ;b 1 ] [a 2 ;b 2 ] = f (x 1 ;x 2 ) j a 1» x 1» b 1 ;a 2» x 2» b 2 g. ffl HS(a 1 ;:::;a d ;c)=fx 1 :::x d j a 1 x a d x d» c g. ffl. P =(~s 1 ;:::;~s k ) conv(p )=fff 1 ~s 1 +:::+ff k ~s k j ff 1 +:::+ff k = 1;ff i g C 1 ieq;int C1 ieq;real Cd ieq;real C d lin Cd geo 3 d ß =(q 1 ;:::;q m ) d BPS [12] Shift-And [12]

8 6 Tomoya Saito NFA ªªªªªª ªªªª ªªªs ªªª ªªªªªª «««ªªªªª 4: BPS BPS 2 ß ß (NFA) M NFA C ß =(q 1 ; ;q m ) 2 C Λ NFA NFA q i = [12] <0> <1> <2> <3> <4> <5> : 5 NFA M m 0 ß = (q 1 ; ;q m ) NFA M = (Q ß ; ± ß ;ffi ß ;I ß ;F ß ) 5 0 m NFA 0 h0i hii ß i q i q 0 = ffl Q ß f0; 1;:::;mg ffl ± ß fh0i; h1i;:::;hmig ffl ffi ß Q ß ± ß Q ß ffi ß = f(i 1; hii;i) j i =1;:::;mg[f(0; h0i; 0)g ffl I ß I ß = h0i ffl F ß F ß = fhmig NFA ~s ß =(q 1 ;:::;q m ) P = fq 1 ;:::;q g P (~s) ~s t m q 1 ;:::;q m q i (~s t )= 1?" q O(jjqjj) O(v) =O(jjßjj) O(vn) 3.3 BPS NFA M 0 t ~s t hii = q i m t m +1 6 d S NFA ScanStream D f1;:::;mg m D 2f0; 1g m B 6 O( m) m» O(1) NFA RAM [12] ScanStream 2 6 ScanStream ß d O((T H + O( m )) n) T H

9 Master Thesis: Efficient Algorithms for Complex Time-Series Pattern Matching Based on Bit-Parallel Method 7 procedure ScanStream(S) d S = ~s 1 ~s n ß = q 1 q m S. 1: I ψ 0 m 1 1; 2: F ψ 10 m 1 ; 3: D ψ I; 4: for t ψ 1;:::;n do 5: ~s t B 6: D ψ ((D <<1) j I) &B; 7: if (D & F ) 6= 0 m then t m +1 ; 8: end for 6: NFA ScanStream 3.4 NFA P = fß 1 ;:::;ß k g ß i B i ;I i ;F i ;D i B 0 ;I 0 ;F 0 ;D 0 ß i NFA [12] 3.5 C [lo; high]? Λ [9] C REG C (i) q 2 C "; q 2 REG C (ii) P; Q 2 REG C P Q; (P jq); (P ) Λ 2 REG C (iii) REG C 4 C ß 2 REG C ß E(ß) ß [9] (i) q 2 C E(") = f"g E(q) =fqg (ii) P; Q 2 REG C E(P Q) =E(P ) E(Q), E(P jq) =E(P ) [ E(Q), E((P ) Λ )=E(P ) Λ (iii) E(ß) 5 E(ß) ß Q 2 E(ß) C ß ß S 1» j» n ß Q 2 E(ß) S j 6 3 ß 1 2 S NFA NFA ß 2 = q 1 q 2 [1::3]q 3 q[i::j] q i j 7 ß 0 2 = q 1 q 2 q 2 q 2 q 3 NFA " (k; h0i;l) NFA k q 2 =2 k 1» l» k + j i 1 D i j 1 1 GI GF GI " D ψ D j ((GF (D & GI)) & ο GF ); = 0111 j 1 i(< j) 1 i j 1 1

10 8 Tomoya Saito <0> <0> <1> <2> <0> <2> <2> <3> : ß 2 NFA " ß 3 = q 1 (q 2 )?q 3 ß 4 = q 1 (q 2 ) Λ q 3 [12] 1: ~s P (~s) Bit(P (~s)) O(m) O(mn) 1 C 1 ieq;real O( 1 m log m) 1 C 1 ieq;int O( 1 m) C 1 ieq;int 1 1-HT-table 1 ~s P (~s) =f1::cg ~s 2 f1::cg P (~s) f1;:::;mg Bit(P (~s)) 2 f0; 1g m B[1::c] = (B[1];:::;B[c]) 2 (f0; 1g m ) c 7 P 1 q 1 =(x>2) q 2 =(x<5) q 3 =(x>2 ^ x<7) q 4 =(x<5) q 5 =(x<3) 1 =f1;:::;8g ~s ~s P (~s) Bit(P (~s)) fh1i; h2i; h3ig HT-table C 1 ieq;int P O( 1 cm2 ) O( 1 cm) p 2 N1 O( 1 m) m = jjp jj P 2 1 C 1 ieq;int d O( 1 cm2 ) O( 1 cm) O( 1 mn) m = jjßjj ß n = jsj S

11 Master Thesis: Efficient Algorithms for Complex Time-Series Pattern Matching Based on Bit-Parallel Method 9 Global 2(f0; 1g m ) c // Build( ;P) (B[1];:::;B[c]) P,. 1: for x 2f1; ;cg do 2: B[x] ψ 0 m ; 3: for i 2f1; ;m 1g do 4: if q i (x) =1then B[x] ψ B[x] j 1 << i; 5: end for 6: end for // LookUp(~s) =f1; ;cg ~s = x 2 N ~s = x B[x]. return B[x] 2f0; 1g m ; 8: 1-HT-table C 1 ieq;real 1 1-HT-bin 10 ß jjßjj `i =(x» c) c A 3 q A ( ) A A Global 2(f0; 1g m ) c [6pt] // Build(P ) P. (B[1];:::;B[c]) 1: P A 2: A 2 // LookUp(~s) 1 ~s = x 2 R ~s = x B[x]. 1: ~s B 2: return B 2f0; 1g m ; 9: 1-HT-bin 2 ~s 2 R ~s Bit(P (~s)) 8 7 P 1 10 P 1 A 2 ~s ~s P (~s) Bit(P (~s)) fh1i; h2i; h3ig 123 A jjßjj

12 10 Tomoya Saito 2: ~s P (~s) Bit(P (~s)) q 1 y y q 1 ~s > ~s = <~s< ~s = <~s< ~s = <~s< ~s = ~s < q 2 y q 0 y q 1 x q 0 q 2 q 2 x q 0 x x q 1 11: x y 7 5 q 3 q 2 =q q 5 10: P HT-bin C 1 ieq;real P O( 1 m3 ) O( 1 m2 ) p 2 R1 O( 1 m log m) m = jjp jj P 2 2 C 1 ieq;real d O( 1 m3 ) O( 1 m2 ) O( 1 mn log m) m = jjßjj ß n = jsj S d d C d ieq;real 2 R 2 d d 5.1 q `i(1» i»jqj) `i =(a i x j» c i ) 1» j» d j`ij =1 d =2 11 x y d-ht-bin

13 Master Thesis: Efficient Algorithms for Complex Time-Series Pattern Matching Based on Bit-Parallel Method 11 procedure d-ht-bin(~s =(x; y) 2 R 2 ) 1: a 1 < < a ff x x ~s (0» i» ff +1) S x i 2: b 1 < < b fi y y ~s (0» j» fi +1) S y j 3: B x i By j 4: return B =(B x i & B y j ) 2f0; 1g ; 12: d-ht-bin 11 lin(p ) x y ~s t = fx 1 ;:::;x d g P (~s) =^i `i(x i ) lin(p ) y x L x = fff i x i» a i g ff (ff i=1 i 2 f+1; 1g) R 2 R 2 = S x Sff x Si x (0» i» ff) p 2 P Bi x 2f0; 1g x R 2 = S y Sy fi R2 S y j (0» j» fi) B y j 2f0; 1g d-ht-bin ~s =(x; y) x y z O(z) 3 d-ht-bin C d ieq;real P O( 1 dm2 ) O( 1 dm2 ) p 2 R d 1 O( 1 dm log m) m = jjp jj P 2 3 C d ieq;real d O( 1 dm2 ) O( 1 dm2 ) O( 1 dmn log m) m = jjßjj ß n = jsj S 5.3 ax + by» c z = ax+by z» c x x:prev» c z = x x:prev 5.4 d C d linear R 2 2 R 2 P = fp 1 ;:::;p g( 1) P lin(p ) L v = jlin(p )j O(v) =O(jjßjj)

14 12 Tomoya Saito // d-ht-naive(~s = (x; y) 2 R 2 ) 1: B ψ 0 ; 2 y R 0,6 R 2,6 R 4,6 R 6,6 2: for i ψ 1;:::; do 3: foreach ` 2 p i do 4: if `(~x)=1 then B ψ B j (1 << i 1); 5: end foreach 6: end for 7: return B; 1 R 0,4 R 0,2 R 2,4 R 4,4 R 2,2 R 4,2 R 6,4 13: d-ht-naive 6.2 P 17 d-ht-naive 4 d-ht-naive C d linear P O(1) O(1) p 2 R d 1 O(m) m = jjp jj P 2 4 C d linear d d-ht-naive O(dm 2 1 ) O(dm2 1 ) O( 1 dnm log m) m = jjßjj ß n = jsj S 6.3 d-ht-slab d-ht-slab P 3 R 0,0 R 2,0 R 4,0 S 0 S 1 S 2 S 3 S 4 S 5 S 6 14: R 6,0 R 6,2 lin(p ) `1;`2 2 lin(p ) `1 `2 I(P ) = f `1 `2 j `1;`2 2 lin(p ) g R 2 x x 1 < <x ff y R 2 R 2 = S S 2ff 0» i» ff 2i S 2i =(x i ;x i+1 ) R 2i +1 S 2i+1 = [x i+1 ;x i+1 ] R x 0 = 1;x ff+1 =+1 i = 0;:::;2ff S i S i lin(p ) S i S i = R i;0 + + R i;2fi S i lin(p ) R i;0 ;:::;R i;2fi y R i;j R i;j p 2 P B r 2 f0; 1g 14 3 `1;:::;`3 6.3 ~s =(x; y) x ~s x

15 Master Thesis: Efficient Algorithms for Complex Time-Series Pattern Matching Based on Bit-Parallel Method 13 procedure algd-ht-slab(~s = (x; y) 2 R 2 ) 1: x x 1 < <x ff ~s S i (0» i» 2ff) 2: S i ~s R i;j (0» j» 2fi) 3: return B r 2f0; 1g ; y N R 1,N R N,N 15: S i S i y ~s R i;j R i;j R 1,1 R N,1 lin(p ) v M = v 2 ff; fi M O(log M) =O(log v) 16: N x 5 d-ht-slab C d linear P O( 1 m3 ) O( 1 m3 ) p 2 R d 1 O( 1 m log m) m = jjp jj P 2 5 C d linear d d-ht-slab O( 1 m3 ) O( 1 m3 ) O( 1 mn log m) m = jjßjj ß n = jsj S d 3 d» R [a; b] R 2 d-ht-bucket d [0 ;N ) [0 ;N ) R 2 2 A[1::N; 1::N] R i;j = [i 1 ;i ) [j 1 ;j ) A[i; j] (1» i; j» N) R i;j p 2 P B i;j 2f0; 1g B i;j 6.4 d-ht-bucket ~s = (x; y) i = dx= e j = dy= e A[i; j] B i;j 2f0; 1g

16 14 Tomoya Saito procedure HTConvexBucket(~s =(x; y) 2 R 2 ) 1: i = dx= e; 2: j = dy= e; 3: A[i; j] ; 4: B i;j 2 f0; 1g 17: 6 d-ht-bucket C d linear P O( 1 m2 N 2 ) O( 1 m2 N 2 ) p 2 R d 1 O(T fl + 1 m) m = jjp jj P T fl 2 6 C d linear d d-ht-bucket O( 1 m2 N 2 ) O( 1 m2 N 2 ) O(T fl + 1 mn) m = jjßjj ß N n = jsj S T fl T fl O(v) T fl = O(1) BPS C++ NAIVE: O(mn) [12] L2R: KMP [8] Harada [7] Sadri [13] L2R R2L: BM [3] Harada [7] R2L BPS bin: 4 1-HT-bin BPS [1] BPS lin: 4 1-HT-bin [1] BPS BPS tab: 4 1-HT-table BPS d>1 BPS bin, BPS lin, BPS tab 5 d d-bps bin, d-bps lin, d-bps tab N d =[1;c] d N d n d S ß = q 1 q m 0» "» c a i j 2 [1;c "] q i = ff i 1^ ^ffi d (1» i» m) ffi j =(x j >a i j )^(x j» a i j + ") d =1 c = 100;n=10 7 ;m=3

17 Master Thesis: Efficient Algorithms for Complex Time-Series Pattern Matching Based on Bit-Parallel Method 15 Time (sec) R2L BPS_lin BPS_tab Time (sec) NAÏVE L2R R2L BPS_bin BPS_lin BPS_tab Length of Data 18: PC Pentium M 1.30GHz 32bit RAM 1GB Cygin g n R2L BPS lin BPS tab n BPS n n =10 7 =10; 000; 000 BPS tab 0.8 m 6 m BPS tab m NAIVE L2R R2L 1.5 BPS lin m» 4 NAIVE L2R R2L m 5 BPS bin BPS tab BPS tab Time (sec) Length of P attern 19: NAÏVE L2R R2L BPS_bin BPS_lin BPS_tab Range of Data 20: c c h = 25(%) c 2 3 = =16; 777; BPS tab BPS 3.4 l 1 8 NAIVE L2R R2L 21 BPS tab 0.6 BPS bin BPS lin l 2 NAIVE L2R R2L 6 R2L BPS tab 10 BPS bin BPS lin 2.5

18 16 Tomoya Saito Time (sec) 12 NAÏVE 10 L2R R2L 8 BPS_bin 6 BPS_lin BPS_tab Number of P attern Time (sec) Naïve L2R R2L d-bps _bin d-bps _lin d-bps _tab Number of Variables : 23: d Time (sec) Naïve L2R R2L d-bps _bin d-bps _lin d-bps _tab R ange of Pattern : " " d =3 22 d-bps tab d-bps lin d-bps bin NAIVE, L2R R2L 3 " =70(%) d-bps tab d-bps lin NAIVE, L2R R2L 4 2 d 23 d 1 8 m =4 d R d fl =0:25 " = fl 1=d d d-bps tab 2:5 m» 4 BPS lin m 5 L2R R2L BPS 8 6 d d-ht-naive, d-ht-slab d-ht-bucket d-ht-bucket PC Core 2 Duo T GHz 32bit RAM 1GB VisualC R =[0; 1] [0; 1] R 2 e = 10 p 1 ;:::;p e 2 R 24 m m 2 n S =(~s 1 ;:::;~s n ) 2 R Λ 2 c» 2 16 BPS tab

19 Master Thesis: Efficient Algorithms for Complex Time-Series Pattern Matching Based on Bit-Parallel Method 17 y 1 Time (msec) d-ht-naive d-ht-s lab d-ht-bucket P attern length x 25: 24: e m d-ht-naive m d-ht-slab m m =4 d-ht-naive 4 d-ht-bucket m m =4 d-ht-naive 25 6 d-ht-bucket m =4;e =10 0:5% 9 d BPS mocapdata( bvh alk-normal-azumi.bvh bvh alk-normalazumi.bvh alk-normal-azumi.bvh root 54 t = 206 m = 16 d = 54 S[t::t + m 1] ß = q 1 q m q i = ff i 1 ^ ^ffi d ; (1» i» m) ff j i =(x j <p j [i]+" j =2)^(x j p j [i] " j =2)

20 18 Tomoya Saito HIERARCHY ROOT Hips OFFSET CHANNELS 6 XpositionYpositionZpositionZrotationXrotationYrotation JOINT LeftHip OFFSET e CHANNELS 6 XpositionYpositionZpositionZrotationXrotationYrotation JOINT LeftKnee OFFSET e e-014 CHANNELS 6 XpositionYpositionZpositionZrotationXrotationYrotation JOINT LeftAnkle OFFSET e e-014 CHANNELS 6 XpositionYpositionZpositionZrotationXrotationYrotation End Site OFFSET } } } } JOINT RightHip OFFSET e CHANNELS 6 XpositionYpositionZpositionZrotationXrotationYrotation JOINT RightKnee OFFSET e e-014 CHANNELS 6 XpositionYpositionZpositionZrotationXrotationYrotation JOINT RightAnkle OFFSET e e-014 CHANNELS 6 XpositionYpositionZpositionZrotationXrotationYrotation End Site OFFSET } MOTION Frames: 747 Frame Time: e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e e-01 26: bvh ( ) p j [i] ~p j i " j j j range j h " j = range j h 9.2 alk-normal-azumi.bvh alk-normal-azumi.bvh d BPS bin h 0 0:05 BPS GUI 28 (1): (2): (3): 27: bvh ( ) (4): (5): t (6): h (7): m (8): (9): bvh t h m GUI 9.3 ß( 29-(a)) ß 9 h ß 9 A 1 ;:::;A 9 ß B 1 ;:::

=0:85 ß A 5 ( 29- (b)) h = 1:35 9 2 ( 29-(c)) n = 747 150msec (4) h 3: h 0 ο 0:8 A 1 0:85 ο 1:05 A 1 ;A

1 ;A 2 ;A 3 ;A 4 ;A 5 ;A 6 ;A 7 ;A 9 ;B 2 1:35 A 1 ;A 2 ;B 1 ;A 3 ;A 4 ;A 5 ;A 6 ;A 7 ;A 8 ;A 9 ;B 2 10

21 Master Thesis: Efficient Algorithms for Complex Time-Series Pattern Matching Based on Bit-Parallel Method 19 (a) (b) (c) (1) (5) (6) (7) (8) (2) (9) (3) 28: BPS GUI 29: (a) ß (b) (c) h =0ο 0:8 A 1 : ß h =0:85 ß A 5 ( 29- (b)) h = 1: ( 29-(c)) n = msec (4) h 3: h 0 ο 0:8 A 1 0:85 ο 1:05 A 1 ;A 5 1:10 ο 1:15 A 1 ;A 5 ;A 7 1:20 A 1 ;A 2 ;A 5 ;A 6 ;A 7 1:25 A 1 ;A 2 ;A 4 ;A 5 ;A 6 ;A 7 ;B 2 1:30 A 1 ;A 2 ;A 3 ;A 4 ;A 5 ;A 6 ;A 7 ;A 9 ;B 2 1:35 A 1 ;A 2 ;B 1 ;A 3 ;A 4 ;A 5 ;A 6 ;A 7 ;A 8 ;A 9 ;B 2 10 d 1 O(mn) NAIVE O( 1 mn) 1 O( 1 mn log m) m; n; m» O(n) =32or64 d O( 1 dmn log m) d =2 O( 1 mn log v) v [2]

22 20 Tomoya Saito [1] A. V. Aho, J. E. Hopcroft and J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, [2] T. Asai, H. Arimura, K. Abe, S. Kaasoe and S. Arikaa, Online Algorithms for Mining Semi-structured Data Stream, Proc. ICDM'02, 27 34, [3] R. S. Boyer and J. S. Moore, A Fast String Searching Algorithm, CACM, , [4] D. Carney, U. Cetintemel, M. Cherniack, C. Convey, S. Lee, G. Seidman, M. Stonebraker, N. Tatbul and S. Zdonik, Monitoring Streams: A Ne Class of Data Management Applications, Proc. VLDB'02, , [5] M. Crochemore and W. Rytter, Text Algorithms, Oxford University Press, [6] L. Harada, Complex Temporal Patterns Detection over Continuous Data Streams, Proc. AD- BIS'02, , [7] L. Harada, Pattern Matching over Multiattribute Data Streams, Proc. SPIRE'02, LNCS 2476, , [8] D. E. Knuth, J. H. Morris Jr. and V. R. Pratt, Fast Pattern Matching in Strings, SIAM J. Comput., , [9] H. R. Leis and C. H. Papadimitriou, Elements of the Theory of Computation, Prentice-Hall, [10], XPath, Proc.DBWS'03, , [11] R. Motani, J. Widom, A. Arasu, B. Babcock, S. Babu, M. Datar, G. Manku, C. Olston, J. Rosenstein and R. Varma, Query Processing, Approximation, and Resource Management in a Data Stream Management System, Proc. CIDR'03, [12] G. Navarro and M. Raffinot, Flexible Pattern Matching in Strings, Cambridge University Press, [13] R. Sadri, C. Zaniolo, A. M. Zarkesh and J. Adibi, Optimization of Sequence Queries in Database Systems, Proc. PODS'01, ACM, 71 81, [14] T. Saito, T. Kida and H. Arimura, An Efficient Algorithm for Complex Pattern Matching over Continuous Data Streams Based on Bit-parallel Method, Proc. SWOD'07, IEEE, 13 18, [15],, 6 (FIT2007),, D-019, [16],, 19 (DEWS2008),, E1-1, 2008.

23 Master Thesis: Efficient Algorithms for Complex Time-Series Pattern Matching Based on Bit-Parallel Method 21 [17],, 18 (DEWS2007),, C1-9, [18] G. A. Stephen, String Searching Algorithms, World Scientific, [19] M. Stonebraker and U. Cetintemel, "One Size Fits All": An Idea Whose Time Has Come and Gone, Proc. ICDE'05, 2 11, [20] Y. Watanabe and H. Kitagaa, A Multiple Continuous Query Optimization Method Based on Query Execution Pattern Analysis, Proc. DASFAA'04, , 2004.

DEIM Forum 2014 D3-5 DSMS DSMS DSMS 2.13% RTOS Realtime-Aware Efficient Query Processing for Automotiv

DEIM Forum 2014 D3-5 DSMS DSMS DSMS 2.13% RTOS Realtime-Aware Efficient Query Processing for Automotiv DEIM Forum 2014 D3-5 DSMS 464 8601 E-mail: {katsunuma,honda,hiro}@ertl.jp DSMS DSMS 2.13% RTOS Realtime-Aware Efficient Query Processing for Automotive DSMS Satoshi KATSUNUMA, Shinya HONDA, and Hiroaki