Á¤º¸°úÇÐȸ ³í¹®Áö D : µ¥ÀÌŸº£À̽º
Current Result Document : 5 / 5
ÀÌÀü°Ç
ÇѱÛÁ¦¸ñ(Korean Title) |
HybridFTW: ¹üÀ§ ÁúÀÇ¿¡¼ µ¿Àû ŸÀÓ ¿öÇÎ °Å¸®ÀÇ ÇÏÀ̺긮µå °è»ê |
¿µ¹®Á¦¸ñ(English Title) |
HybridFTW: A Hybrid Approach to Computing of Dynamic Time Warping Distances in Range Queries |
ÀúÀÚ(Author) |
À̹οì
±è»óÇÊ
¹®¾ç¼¼
±èÁøÈ£
ÀÌ»ó¹Î
Minwoo Lee
Sang-Pil Kim
Yang-Sae Moon
Jinho Kim
Sang-Min Rhee
|
¿ø¹®¼ö·Ïó(Citation) |
VOL 40 NO. 04 PP. 0251 ~ 0262 (2013. 08) |
Çѱ۳»¿ë (Korean Abstract) |
º» ³í¹®¿¡¼´Â ½Ã°è¿ ´ë»óÀÇ À¯»ç °Ë»ö¿¡¼ µ¿Àû ŸÀÓ ¿öÇÎ(DTW) °Å¸®¸¦ °è»êÇÏ´Â È¿À²ÀûÀÎ ¹æ¹ýÀ» Á¦¾ÈÇÑ´Ù. DTW °Å¸®´Â À¯»ç °Ë»ö¿¡¼ ³ôÀº Á¤È®µµ¸¦ Á¦°øÇÏÁö¸¸, °è»êÀÌ º¹ÀâÇÏ¿© ´ë¿ë·® µ¥ÀÌÅͺ£À̽º Àû¿ëÀÌ Èûµç ¹®Á¦Á¡ÀÌ ÀÖ´Ù. ÃÖ±Ù ÀÌ·¯ÇÑ DTW °Å¸®ÀÇ È¿À²Àû °è»ê ¹æ¹ýÀ¸·Î FastDTW¿Í FTW°¡ Á¦¾ÈµÇ¾ú´Ù. ±×·¯³ª, FastDTW´Â °è»ê µµÁß °Å¸® °ªÀÌ Çã¿ëÄ¡º¸´Ù Å« °æ¿ì¿¡µµ °è¼Ó °Å¸® °è»êÀÌ ÀÌ·ç¾îÁö´Â ´ÜÁ¡ÀÌ ÀÖ°í, FTW´Â Çã¿ëÄ¡°¡ »ó´ëÀûÀ¸·Î Å©°Ô ÁÖ¾îÁö´Â °æ¿ì¿¡ À¯»çÇÏÁö ¾ÊÀº ¸¹Àº µ¥ÀÌÅÍ ½ÃÄö½º¸¦ »¡¸® ÀüÁö(pruning)ÇÏÁö ¸øÇÏ´Â ´ÜÁ¡ÀÌ ÀÖ´Ù. º» ³í¹®¿¡¼´Â ÀÌ µÎ ¹æ¹ýÀÇ ÀåÁ¡À» ÃëÇÏ¿© DTW °Å¸® °è»ê ¼º´ÉÀ» Çâ»ó½ÃÅ°´Â ÇÏÀ̺긮µå °è»ê¹ýÀÎ HybridFTWÀ» Á¦¾ÈÇÑ´Ù. HybridFTW´Â FastDTWÀÇ Çã¿ë ¹üÀ§ Á¦ÇÑÀ» ÅëÇÑ ºü¸¥ °è»êÀÇ ÀåÁ¡°ú FTWÀÇ ¹Ì¸® ¹ö¸²ÀÇ ÀåÁ¡À» Á¶ÇÕÇÔÀ¸·Î½á DTW °Å¸® °è»êÀÇ ¼º´ÉÀ» Å©°Ô Çâ»ó½ÃŲ´Ù. À̸¦ À§ÇØ, º» ³í¹®¿¡¼´Â ¿ì¼± ±âÁ¸ FTW¿Í FastDTWÀÇ µ¿ÀÛ ÀýÂ÷¸¦ ÀÚ¼¼È÷ ºÐ¼®ÇÏ°í, ÀÌµé ¹æ¹ýÀÇ ÀåÁ¡À» µµÃâÇÑ´Ù. ±×¸®°í, À̵é ÀåÁ¡À» ÃëÇÑ HybridFTWÀÇ °³³äÀ» Á¦½ÃÇÏ°í, HybridFTW¸¦ ÀÌ·ç´Â ¼¼ °¡Áö ´Ü°è¿Í °¢ ´Ü°èÀÇ µ¿ÀÛ ÀýÂ÷¸¦ Á¤ÇüÀûÀ¸·Î ¼³¸íÇÑ´Ù. ¶ÇÇÑ, HybridFTW¸¦ »ç¿ëÇÑ ¹üÀ§ °Ë»ö(range search) ¾Ë°í¸®ÁòÀ» Á¦½ÃÇÏ°í, ÀÌ ¾Ë°í¸®ÁòÀÇ Á¤È®¼ºÀ» Á¤¸®·Î Áõ¸íÇÑ´Ù. ½ÇÁ¦ ½ÇÇè °á°ú, HybridFTW´Â FastDTW¿¡ ºñÇØ ÃÖ´ë 4.5¹è, FTW¿¡ ºñÇØ ÃÖ´ë 2.0¹è±îÁö ¼º´ÉÀ» Çâ»ó½ÃŲ °ÍÀ¸·Î ³ªÅ¸³µ´Ù.
|
¿µ¹®³»¿ë (English Abstract) |
In this paper, we propose an efficient approach that computes the dynamic time warping (DTW) distance in time-series similarity search. The DTW distance is known to offer the high accuracy in similarity search, but it has a difficult problem in supporting the large database due to its high computation complexity. Recently, FastDTW and FTW have been proposed for the efficient computation of the DTW distance. These two methods, however, have the following disadvantages: FastDTW continues the complex computation until the final DTW distance is obtained even if the intermediate distance exceeds the given tolerance; FTW may not prune many dissimilar data sequences at an early stage if the given tolerance is relatively large. In this paper, we propose a hybrid approach, called HybridFTW, which adopts advantages of both methods. HybridFTW improves the performance significantly by combining the advantage of FastDTW, which provides the fast computation through the limitation of allowable ranges, and the advantage of FTW, which exploits the early abandon effect. For this, we first analyze the computation procedure of FastDTW and FTW in detail and derive their advantages clearly. We then present the concept of HybridFTW by taking their both advantages, describe three steps of HybridFTW, and formally explain the detailed computing procedure of each step. We also propose a range search algorithm that exploits HybridFTW and prove its correctness through a formal theorem. Experimental results on real and simulation data sets show that the proposed HybridFTW improves the search performance by up to 4.5 times over FastDTW and by up to 2.0 times over FTW.
|
Å°¿öµå(Keyword) |
µ¥ÀÌÅÍ ¸¶ÀÌ´×
½Ã°è¿ µ¥ÀÌÅÍ
À¯»ç ½ÃÄö½º ¸ÅĪ
µ¿Àû ŸÀÓ ¿öÇÎ
data mining
time-series data
similar sequence matching
dynamic time warping
|
ÆÄÀÏ÷ºÎ |
PDF ´Ù¿î·Îµå
|