• 検索結果がありません。

類似セグメント探索 RDDS 法の評価

N/A
N/A
Info
ダウンロード
Protected

Academic year: 2021

シェア "類似セグメント探索 RDDS 法の評価"

Copied!
6
0
0

読み込み中.... (全文を見る)

今ダウンロードする ( 6 ページ )

全文

(1)IPSr*SIG TechSS^Reports^"""^. .. 2006/12/21. > hUm RDDS. T 965-8580 E-Mail: [email protected]. , 2.. +-7- K: Active £*, tUBLtlf* > hftiRtt, #SlJ«S?&ffi. Evaluation of Similar Segment Search Algorithm in Multiple Time Series Y.Watanabe, Y.Tanimoto, A.Sakai, M.Sugiyamat tSchool of Computer Science and Engineering, The Univ. of Aizu Ikki-machi, Aizu-Wakamatsu, Fukushima, 965-8580 Japan. E-Mail: [email protected] Abstract On an efficient similar segment search algorithm, RDDS (Recursive Diamond Divi sion Search), this report describes the following three investigation results; l.An efficient query search algorithm in one time series, 2. Improvement of similar segment search algorithm in two. time series, 3. Implementation and evaluation of similar search algorithm in three time series. Keyword: Active searching, similar segment search algorithm, Divide-and-Conquer algorithm. (Reference Interval Free Active Search) £^ffl h AS ft 0-4. AS fKC. &l'±^E.-r*tt+r\,\n>i~7* RIFAS AS. AS «R« RIFAS y hmm rdds ^tc , 2. 2. ,ZtLT^Z>. 2gj5TAS &t RIFAS. RDDS JS^flSmU 4S5T RDDS < RIFAS i*. -83-.

(2) 2. as mt rifas. skip. I. 2.1. distance f Pt. d(Pt><t)iq Very. vt (t =. 2.3. RIFAS >:. sequence of. _ _T _ _ 0U?P_ut Props-_ i. i:. RIFAS. AS. 2v\n\. 2.2. (1) P = (pt),Q =. Active. (4) P \zMLX. S^xU, ^ > 0. rn&tu s dP(ptiq)<9.. (2). Bf-SO fc. (1) (3). (3) Vn<. \ dp(pt,q)<e. pt. dp(pt,q). I 2: RIFAS. -84-.

(3) n. 3 3.1 (9). u x,. (9). * (5). t = (ti,. 3.2 (5). (6). R) %¥&£?%> h (6). (> 0). (6). d(t) < 0.. ^. 3.3. (RDDS). (RDDS: Recursive Diamond Division Search) yfz. HI 3 \Z7F~f<k:D \zmM&M T = [0,Ti) x. [0,T2) x ...[0,Tj) £|rH<£>¥!£ W <D h 3&zXW8ltt%>. TcUiBi(ti,W).. (10). (11). d(t). >. (ii) d(t). \ZvkLtc. A (7) ttSC (1) (7) <0H. do). (12) (12). Boo(ti,r)cB1(ti,/r).. T ^MMT3*S r = W/I <D .. W) 5:. C<Dm T C UiBoofaW/I) c. loo (13). (13). r = VT/7 = L/2.. (8). 0, Zo. (8) -85-. 2^ ffi'ttTflM^Sc 2/ 2', iE 2/ [10].. IE.

(4) *) *Jti£Vt>Z<DT?jmm<D [left, right'] X« [left', right]. {. right'. = center - i? — 1. left'. = center + R + 1.. (14). [left, right] \zmttmb, wB =. (right - left + 1) /2. h 3: CampusWave x—. 4. 33. rdds omm. ^. ^ t7Uy#m WB. 4.1. RDDS-lr t AS,. RDDS0E«tt Z CampusWave x-*^-X [11]. tt 713, 645, 520. W. FM. RDDS-lr. 0.. \z wB. RDDS |WHi, RDDS-lr . RDDS,. Lfc. VQ. M = 32 t bfg 1 07-. (Wi -250). RDDS-lr. 6 LBG. 4.2. (300. RDDS. RDDS. •2P>\zwB> 2000 .. 520-530. (b): Mfc. .. RDDS-lr 6=0.1 RDDS-lr6=0.05 RDDS-lr 6=0.01 AS 6=0.1 AS 6=0.05 AS 6=0.01 RDDS 6=0.1. RDDS-lr. . 04K RDDS-lr. left. ^skio resion T. right'. center. —— --— * -— ■■-•-•. right. T. UO1UC1 left'. 1000. 2000. 3000. 4000. 5000. gl 4: RDDS-lr. 5: mmmm ettfuy^mwB [left, right] CD^it center (=(left+right)/2). -86-. 2. RDDS-lr. rddsat.

(5) 4.3. 2 B«R5IJ«fcl-t^ > 2jW 3W. 3 TSfi^fc /i 2W. W. [9]. 0 6 lc. W. t (iWJW). 2W. 3W. 4W. 5W. 6W. 7W. \t 2 iW (i = 0,1,...). 6:. 0 = 0,1,2,...) £3S*ff*l$, x. = 256 <Z)P#, 111,772 (= 618435 - 506663). HI (18.07%), W = 128 <Z)B#, 1,146,346 (= 1561240 414894) II (73.43%) ifc*. W *t. 3^ (2iW,2jW), (2iW,. T = 225000, L = 625, W = 256 <ht"3£ J = 438. **©TE»f Jlfc8t"*tH|C*»4 96141. (15). tf 95703. (11). 191,844 (= 96141 + 95703) £&%>. fot. 5£ (15). <f 4.4. (15). 3. (16). (16). W/3. as as RDDS-2. fcJ4 CampusWave x—^^—. »J(J CampusWavex—. JxJ. 0,. 60 » (r = 3126) -87-. El,.

(6) RDDS-2. T3 = 31263 = 3.05 x 1010 256, L = 625,. ,. (RDDS-2+DM). 9 = 0.3, W =. ffm. 2: RDDS-3. in = 0. t Lit. W = 256. 1 ffl. 183 = 5832 t fc*. rdds. RDDS-3. Wmin. 3.0510. 5. titXS rdds. 7 = 2 wmin =. , -f. , wmin = 4,8 RDDS-3. 1.504 * 106(= 7240 * 603/1040) RDDS-3. Exhaustive. Campu$WaveO3. CampusWawO2 CampusWawOI. 7: RDDS-3(T). [12] R.Vidal: An Algorithm for Finding Nearest Neighbor in (Ap proximately) Constant Average Time, Pattern Recognition Let ters, No.4, pp. 145-158 (1986).. -88-.

(7)

参照

今ダウンロードする ( PDF - 6 ページ - 451.71 KB )

関連したドキュメント

Financial Applications of a Tabu Search Variable Selection Model

A Tabu search procedure is then used to select a subset of financial ratio variables which best predict bankruptcy from among a larger initial set of 20 variables, and use that

Financial Applications of a Tabu Search Variable Selection Model

A Tabu search procedure is then used to select a subset of financial ratio variables which best predict bankruptcy from among a larger initial set of 20 variables, and use that

A Multiswarm Optimizer for Distributed Decision Making in Virtual Enterprise Risk Management

Since the optimizing problem has a two-level hierarchical structure, this risk management algorithm is composed of two types of swarms that search in different levels,

2. On the Computation of the Efficient Frontier

An easy-to-use procedure is presented for improving the ε-constraint method for computing the efficient frontier of the portfolio selection problem endowed with additional cardinality

Algorithm for the Vehicle Routing Problem with Customer Satisfaction

13 proposed a hybrid multiobjective evolutionary algorithm HMOEA that incorporates various heuristics for local exploitation in the evolutionary search and the concept of

Asymptotic normality of recursive algorithms via martingale difference arrays

Under certain assumptions on the sequence (P N ) N≥0 (which still allow for the standard probabilis- tic models of algorithms associated with binary search trees, digital search

AmmarW.MohemmedandNirodChandraSahoo EfficientComputationofShortestPathsinNetworksUsingParticleSwarmOptimizationandNoisingMetaheuristics ResearchArticle

For performance comparison of PSO-based hybrid search algorithm, that is, PSO and noising-method-based local search, using proposed encoding/decoding technique with those reported

An Exact Method for the 2D Guillotine Strip Packing Problem

In this paper, we propose an exact algorithm based on dichotomic search to solve the two-dimensional strip packing problem with guillotine cut2. In Section 2 we present some