도로 네트워크에서 랜드마크 다차원 척도법을 이용한 효율적인 M-트리 대량적재 알고리즘

노웅기 한국정보과학회 2020 데이타베이스 연구 Vol.36 No.3

In this study, we propose an algorithm for M-tree bulk loading in road networks. Road networks are highly dynamic; traffic situation changes constantly owing to vehicle movements and unpredicted constructions and accidents. Thus, it is crucial for road network applications to periodically reorganize the index to fully reflect the changes. In such a circumstance, rather than modifying the existing index for each of the changes, it is more efficient to quickly bulk load a new index for the entire road network. The previous M-tree bulk loading algorithms heavily conduct ‘expensive’ shortest-path distance computations and disk page accesses, thereby degrading their performances. The algorithm proposed in this study reduces the number of shortest-path distance computations using landmark multidimensional scaling (LMDS). In addition, since our algorithm stores M-tree nodes in disk and does not access them again, the number of disk page accesses is also dramatically reduced. Experimental results demonstrated that our algorithm outperformed the previous algorithm by up to 21.3 times (single-thread version) and 106 times (multi-thread version with 64 concurrent threads) for M-tree construction and that the performance of the k-nearest neighbor (k-NN) search using the M-tree built by our algorithm was also improved by up to 1.22 times. 본 연구에서는 도로 네트워크를 위한 M-트리 대량적재(bulk loading) 알고리즘을 제안한다. 도로 네트워크는 매우 동적이며, 차량의 이동, 예측하지 못한 공사와 사고 등으로 인하여 교통 상황이 끊임없이 변화한다. 도로 네트워크 응용에서는 이러한 변화를 반영하도록 인덱스를 주기적으로 재구성하는 것이 필수적이다. 각각의 변화에 대하여 기존의 인덱스를 수정하기보다는 전체 도로 네트워크 데이터셋에 대한 새로운 인덱스를빠르게 재구성하는 대량적재가 효율적이다. 기존의 M-트리 대량적재 알고리즘은 ‘비싼’ 최단경로 거리 계산과 디스크 페이지 엑세스를 과도하게 수행하여 충분한 성능을 거두지 못하였다. 본 연구에서 제안하는 M-트리 대량적재 알고리즘은 랜드마크 다차원 척도법(Landmark Multidimensional Scaling, LMDS)을 이용하여 최단경로 거리 계산을 대폭 줄인다. 또한, 각 노드를 한번씩만 디스크에 저장하고 더 이상 읽지 않음으로써 디스크 액세스 횟수를 크게 줄였다. 실험 결과, 제안된 알고리즘은 기존의 알고리즘에 비하여 단일 쓰레드버전은 최대 21.3배, 다중 쓰레드 버전(동시 쓰레드 64개)은 최대 106배까지 M-트리 생성 성능이 향상되었고, 제안된 알고리즘으로 생성한 M-트리를 이용한 k-최근접 객체(k-nearest neighbor) 검색의 성능이 최대 1.22 배까지 향상되었다.

사례발표 : 미국 내의 IPTV 서비스 현황

노웅기,윤용익 한국정보처리학회 2007 정보처리학회지 Vol.14 No.2

도로 네트워크에 대한 다차원 척도법의 비교

노웅기 한국정보과학회 2020 데이타베이스 연구 Vol.36 No.2

A road network consists of points of interest (POIs) and the traffic situations between them in the real world. There are a number of road network applications; they issue many proximity queries, aggregated nearest neighbor (ANN) queries, and flexible aggregated nearest neighbor (FANN) queries. The distance between two POIs in a road network is defined as the shortest-path distance between them, and the computation of the distance has a complexity that is much higher than that of distance computation in a Euclidean space. Each POI in a road network corresponds to an object in a metric space. If the POIs are mapped into the points in a Euclidean space such that their distances are preserved as much as possible, we can harness the existing algorithms using multidimensional index structures like the R-trees and significantly reduce the cost of distance computations when processing diverse queries. In this study, we consider three multidimensional scaling (MDS) methods, namely classical MDS, landmark MDS (LMDS), and FastMap, for mapping POIs in a road network into points in a Euclidean space, and compare the execution time and mapping quality of these methods. Among the methods, LMDS has been proven to be highly efficient in previous studies, and our experiments also demonstrated fast execution and high mapping quality of LMDS for road networks. 도로 네트워크(road network)는 실세계 도로 상의 관심 지점들(points of interest, POIs)과 그들 간의 교통 상황을 반영한다. 도로 네트워크 응용은 매우 다양하며, 이러한 응용에서는 근접성 검색(proximity search)를 비롯하여, 집계 최근접 객체(aggregated nearest neighbor, ANN) 검색, 유연한 집계 최근접 객체(flexible aggregated nearest neighbor, FANN) 검색 등이 발생한다. 도로 네트워크 내의 두 POI 간의 거리는 그들 간의 최단경로 거리(shortest-path distance)로 정의되며, 이 연산은 유클리드 공간 내의 두 지점 간의 거리 계산에 비하여 복잡도가 매우 높다. 도로 네트워크 내의 각 POI는 거리 공간(metric space) 내의 하나의 객체로 대응이 가능하다. 만약 도로 네트워크 내의 POI를 그들 간의 거리가 유지되도록 유클리드 공간으로 매핑이 가능하다면 기존의 R-트리 등에 기반한 알고리즘들을 활용할 수 있으며, 두 POI 간의 거리 계산 비용도 크게 낮아질 것이다. 본 논문에서는 도로 네트워크에 대하여 전통적 MDS (classical MDS), 랜드마크 MDS (landmark MDS, LMDS), 그리고 FastMap 세 가지 다차원 척도법(multidimensional scaling, MDS) 방법들을 적용하여 유클리드 공간으로의 변환 시간 및 품질을 비교한다. 이 중 LMDS는 기존의 연구에서도 그 효율성이 입증되었으며, 본 논문에서의 실험에서 도로 네트워크에 대해서도 우수한 성능을 보였다.

인덱스 보간법에 기반한 효율적인 서브시퀀스 매칭 기법

노웅기,김상욱,Loh Woong-Kee,Kim Sang-Wook 한국정보처리학회 2005 정보처리학회논문지D Vol.12 No.3

Subsequence matching is one of the most important operations in the field of data mining. The existing subsequence matching algorithms use only one index, and their performance gets worse as the difference between the length of a query sequence and the site of windows, which are subsequences of a same length extracted from data sequences to construct the index, increases. In this paper, we propose a new subsequence matching method based on index interpolation to overcome such a problem. An index interpolation method constructs two or more indexes, and performs search ing by selecting the most appropriate index among them according to the given query sequence length. In this paper, we first examine the performance trend with the difference between the query sequence length and the window size through preliminary experiments, and formulate a search cost model that reflects the distribution of query sequence lengths in the view point of the physical database design. Next, we propose a new subsequence matching method based on the index interpolation to improve search performance. We also present an algorithm based on the search cost formula mentioned above to construct optimal indexes to get better search performance. Finally, we verify the superiority of the proposed method through a series of experiments using real and synthesized data sets. 서브시퀀스 매칭은 데이터 마이닝 분야에서 중요한 연산 중의 하나이다. 기존의 서브시퀀스 매칭 알고리즘들은 하나의 인덱스만을 사용하여 검색을 수행하며, 인덱스를 생성하기 위하여 데이터 시퀀스로부터 추출한 윈도우의 크기와 질의 시퀀스의 길이 간의 차이가 커질수록 검색 성능이 급격히 저하된다. 본 논문에서는 이러한 문제점을 해결하기 위하여 인덱스 보간법에 기반한 새로운 서브시퀀스 매칭 기법을 제안한다. 인덱스 보간법이란 하나 이상의 인덱스를 구축하고 주어진 질의 시퀀스의 길이에 따라 적절한 인덱스를 선택하여 검색을 수행하는 기법이다. 본 논문에서는 먼저 사전 실험을 통하여 서브시퀀스 매칭을 수행하는 데에 있어 질의 시퀀스 길이와 윈도우 크기 간의 차이로 인한 성능의 변화를 관찰하고, 이 관찰을 통하여 물리적 데이터베이스 설계 관점에서 질의 시퀀스의 길이 분포에 따른 검색 비용 공식을 산출한다. 다음에, 윈도우 크기 효과에 의한 성능 저하를 개선하기 위해 인덱스 보간법에 기반한 새로운 검색 기법을 제안한다. 또한, 검색 비용 공식에 기반하여 제안된 검색 기법의 성능을 최적화할 수 있도록 다수의 인덱스를 구성하는 알고리즘을 제시한다. 마지막으로, 실제 데이터와 합성 데이터를 이용한 여러 가지 실험을 통하여 제안된 기법의 우수성을 검증한다.

CC-GiST: 임의의 캐시 인식 검색 트리를 효율적으로 구현하기 위한 일반화된 프레임워크

노웅기,김원식,한욱신,Loh, Woong-Kee,Kim, Won-Sik,Han, Wook-Shin 한국정보처리학회 2007 정보처리학회논문지D Vol.14 No.1

최근 메인 메모리 가격이 하락하고 용량이 크게 증가함에 따라 메인 메모리 데이터베이스에 기반한 응용이 급격히 증가하고 있다. 캐시 미스 (cache miss)는 CPU에서 액세스하고자 하는 데이터가 캐시에 존재하지 않아 메모리로부터 읽어 들이는 과정이며, 메인 메모리 데이터베이스의 성능 감소의 중요한 원인이다. 메인 메모리 데이터베이스에서의 캐시 미스를 줄이고 캐시를 최대한 활용하기 위하여 여러 가지 캐시 인식 트리들(cache conscious trees)이 제안되었다. 이러한 캐시 인식 트리들은 각각 특성이 다르므로 하나의 응용에서 둘 이상의 캐시 인식 트리들이 동시에 관리될 수 있다. 또한, 만약 기존의 캐시 인식 트리가 응용에서의 요구를 만족시키지 못하면 새로운 캐시 인식 트리를 구현하여야 한다. 본 논문에서는 캐시 인식하는 일반화된 검색 트리(Cache-Conscious Generalized Search Tree, CC-GiST)를 제안한다. CC-GiST는 디스크 기반의 일반화된 검색 트리 (Generalized Search Tree, GiST) [HNP95]를 캐시 인식하도록 확장한 것이며, 포인터 압축(pointer compression)과 키 압축(key compression) 기법을 비롯하여 임의의 캐시 인식 트리의 공통적인 기능 및 알고리즘들을 동시에 제공한다. CC-GiST를 기반으로 특정 캐시 인식트리를 구현하려면 그 트리에 해당된 기능만을 구현하면 된다. 본 논문에서는 CC-GiST를 기반으로 기존의 대표적인 캐시 인식 트리인 CSB+-트리, pkB-트리, CR-트리를 구현하는 방법을 기술한다. CC-GiST를 이용함에 따라 메인 메모리 데이터베이스 응용에서 여러 개의 캐시 인식 트리를 관리하는 번거로움에서 벗어날 수 있고, 응용의 요구에 따른 새로운 캐시 인식 트리를 최소한의 노력으로 효율적으로 구현할 수 있다. According to recent rapid price drop and capacity growth of main memory, the number of applications on main memory databases is dramatically increasing. Cache miss, which means a phenomenon that the data required by CPU is not resident in cache and is accessed from main memory, is one of the major causes of performance degradation of main memory databases. Several cache-conscious trees have been proposed for reducing cache miss and making the most use of cache in main memory databases. Since each cache-conscious tree has its own unique features, more than one cache-conscious tree can be used in a single application depending on the application's requirement. Moreover, if there is no existing cache-conscious tree that satisfies the application's requirement, we should implement a new cache-conscious tree only for the application's sake. In this paper, we propose the cache-conscious generalized search tree (CC-GiST). The CC-GiST is an extension of the disk-based generalized search tree (GiST) [HNP95] to be tache-conscious, and provides the entire common features and algorithms in the existing cache-conscious trees including pointer compression and key compression techniques. For implementing a cache-conscious tree based on the CC-GiST proposed in this paper, one should implement only a few functions specific to the cache-conscious tree. We show how to implement the most representative cache-conscious trees such as the CSB+-tree, the pkB-tree, and the CR-tree based on the CC-GiST. The CC-GiST eliminates the troublesomeness caused by managing mire than one cache-conscious tree in an application, and provides a framework for efficiently implementing arbitrary cache-conscious trees with new features.

유사한 인기도 추세를 갖는 웹 객체들의 클러스터링

노웅기,Loh, Woong-Kee 한국정보처리학회 2008 정보처리학회논문지D Vol.15 No.4

Huge amounts of various web items such as keywords, images, and web pages are being made widely available on the Web. The popularities of such web items continuously change over time, and mining temporal patterns in popularities of web items is an important problem that is useful for several web applications. For example, the temporal patterns in popularities of search keywords help web search enterprises predict future popular keywords, enabling them to make price decisions when marketing search keywords to advertisers. However, presence of millions of web items makes it difficult to scale up previous techniques for this problem. This paper proposes an efficient method for mining temporal patterns in popularities of web items. We treat the popularities of web items as time-series, and propose gapmeasure to quantify the similarity between the popularities of two web items. To reduce the computation overhead for this measure, an efficient method using the Fast Fourier Transform (FFT) is presented. We assume that the popularities of web items are not necessarily following any probabilistic distribution or periodic. For finding clusters of web items with similar popularity trends, we propose to use a density-based clustering algorithm based on the gap measure. Our experiments using the popularity trends of search keywords obtained from the Google Trends web site illustrate the scalability and usefulness of the proposed approach in real-world applications. 인터넷이 광범위하게 활용됨에 따라 검색 키워드, 멀티미디어 객체, 웹 페이지, 블로그 등의 다양한 웹 객체들이 크게 증가하고 있다. 이러한 웹 객체들의 인기도는 시간에 따라 변화하며, 그러한 웹 객체 인기도의 시간적 패턴에 대한 마이닝이 여러 가지 웹 응용에 필요한 중요한 연구 과제가 되고 있다. 예를 들어, 검색 키워드에 대한 인기도 패턴의 분석은 앞으로 인기가 높아질 키워드를 미리 예측할 수 있게 하여 광고주들에게 키워드를 판매하기 위한 가격을 결정하는 데에 중요한 자료가 될 수 있다. 하지만, 웹 객체 인기도가 시간에 따라 변화하고 웹 객체의 개수가 매우 방대하다는 특성으로 인하여 웹 객체 인기도에 대한 분석은 매우 어려운 문제이다. 본 논문에서는 웹 객체 인기도의 시간적 패턴을 마이닝하기 위한 효율적인 알고리즘을 제안한다. 본 논문은 웹 객체 인기도를 시계열로 표현하고, 두 웹 객체 인기도 간의 유사성을 측정하기 위하여 gap 척도를 제안한다. gap 척도의 효율적인 계산을 위하여 FFT를 활용한 알고리즘을 제안하고, 밀도기반 클러스터링 알고리즘을 이용하여 유사한 인기도 추세를 갖는 웹 객체들의 클러스터를 생성한다. 본 논문에서는 웹 객체 인기도가 특정 분포를 따르거나 주기적이라고 가정하지 않는다. Google Trends 웹 사이트로부터 구한 검색 키워드 인기도를 이용한 실험을 통하여, 제안된 알고리즘이 실세계 응용에서 유용함을 보인다.

MHEG 객체 클래스를 기반으로 하는 멀티미디어 전자 우편 시스템의 설계 및 구현

노웅기(Woong-Kee Loh),황규영(Kyu-Young Whang) 한국정보과학회 1993 한국정보과학회 학술발표논문집 Vol.20 No.2

본 논문에서는 표준화된 멀티미디어 정보 객체를 인코드/디코드하는 멤버 함수를 갖는 MHEG 객체 클래스를 정의하고, 그를 이용하여 인터네트 상에 연결된 시스템들 간의 멀티미디어 메일 시스템을 설계, 구현한다. MHEG 객체 클래스는 멀티미디어 응용 시스템에 서브시스템으로 포함되고, 멀티미디어 전자 우편 시스템은 기존의 텍스트 메일 시스템과의 호환성을 유지하며, 텍스트, 정지 영상, 오디오 등의 복합 객체로 이루어진 멀티미디어 메일을 가능하게 한다.

시계열 데이타베이스에서 인덱스 보간법을 기반으로 정규화 변환을 지원하는 서브시퀀스 매칭 알고리즘 (pp.152-154)

노웅기(Woong-Kee Loh),김상욱(Sang-Wook Kim),황규영(Kyu-Young Whang) 한국정보과학회 2000 한국정보과학회 학술발표논문집 Vol.27 No.1B

본 논문에서는 시계열 데이터베이스에서 정규화 변환을 지원하는 서브시퀀스 매칭 알고리즘을 제안한다. 정규화 변환은 시계열 데이터 간의 절대적인 유클리드 거리에 관계 없이, 구성하는 값들의 상대적인 변화 추이가 유사한 패턴을 갖는 시계열 데이터를 검색하는 데에 유용하다. 제안된 알고리즘은 몇 개의 질의 시퀀스 길이에 대해서만 각각 인덱스를 생성한 후, 이를 이용하여 모든 가능한 길이의 질의 시퀀스 길이에 대해서만 각각 인덱스를 생성한 후, 이를 이용하여 모든 가능한 길이의 질의 시퀀스에 대해서 탐색을 수행한다. 이때, 착오 기각이 발생하지 않음을 증명한다. 본 논문에서는 이와 같이 인덱스가 요구되는 모든 경우 중에서 적당한 간격의 일부에 대해서만 생성된 인덱스를 이용한 탐색 기법을 인덱스 보간법이라 부른다. 질의 시퀀스의 길이 256 ~ 512 중 다섯 개의 길이에 대해 인덱스를 생성하여 실험한 결과, 탐색 결과 선택률이 10^(-5)일 때 제안된 알고리즘의 탐색 알고리즘의 탐색 성능이 순차 검색에 비하여 평균 14.6배 개선되었다.

시계열 데이타베이스에서 임의 계수의 이동평균 변환을 지원하는 서브시퀀스 매칭 알고리즘 (pp.469-485)

노웅기(Woong-Kee Loh),김상욱(Sang-Wook Kim),황규영(Kyu-Young Whang),심규석(Kyuseok Shim) 한국정보과학회 2000 정보과학회논문지 : 데이타베이스 Vol.27 No.3

본 논문에서는 시계열 데이타베이스에서 임의 계수의 이동평균 변환을 지원하는 서브시퀀스 매칭 알고리즘을 제안한다. 이동평균 변환은 시계열 데이타 내의 잡음의 영향을 감소시킴으로써 시계열 데이타 전체의 경향을 파악하는 데에 유용하여 통계경제학 등의 분야에서 널리 사용되어 왔다. 응용 분야와 분석하려고 하는 시계열 데이타의 특성에 따라 잡음의 영향을 줄이는 정도와 경향을 파악하는 주기가 달라지므로 이동평균 계수의 선택도 달라진다. 제안된 매칭 알고리즘은 기존의 서브시퀀스 매칭 알고리즘을 확장하여 임의 계수의 이동평균 변환을 지원한다. 기존의 서브시퀀스 매칭 알고리즘을 확장 없이 그대로 응용할 경우 하나의 이동평균 계수에 대하여 하나씩의 인덱스를 생성하여야 한다. 따라서, 임의의 이동평균 계수를 지원하려면 저장 공간 및 데이타 시퀀스의 삽입/삭제 부담이 매우 심각하다. 본 논문에서는 하나의 이동평균 계수 k에 대해서 생성한 인덱스만을 이용하여 인덱스가 생성되어 있지 않은 계수 m(≤k) 에 대해서도 탐색을 수행하는 방법을 제안한다. 이때, 제안된 탐색 기법이 질의 결과로 반환되어야 할 서브시퀀스를 모두 찾아내지 못하는 착오 기각이 발생하지 않음을 증명한다. 제안된 알고리즘은 하나 이상의 이동평균 계수에 대하여 생성된 인덱스를 이용할 수도 있으며, 이때 탐색 성능의 향상을 얻을 수 있다. 실험을 통하여 제안된 알고리즘의 평균 탐색 성능을 구한 결과, 제안된 알고리즘이 순차 검색에 비하여 최대 약 2.7 배까지 우수하였다. 제안된 알고리즘의 탐색 성능은 탐색 결과 선택률이 작아질수록 향상되어, 일반적인 데이타베이스 응용에서의 효용성이 높다고 판단된다. 본 논문에서 제안된 탐색 기법은 유사한 경향을 갖는 주가 데이타의 검색, 특정 상품의 판매 예측, 기온 데이타 분석을 통한 일기 예보 등 이동평균 변환을 필요로 하는 다양한 응용 분야에 적용될 수 있다. In this paper, we propose a subsequence matching algorithm that supports moving average transform of arbitrary order in time-series databases. Moving average transform reduces the effect of noise and has been used in many areas such as econometrics since it is useful in finding the overall trends in the time-series data. The moving average order to be used varies, since the users want to control the degree of noise reduction and the frequency of analysis depending on the applications and the characteristics of data sequences. The proposed matching algorithm supports moving average transform of arbitrary order by extending the existing subsequence matching algorithm. If we applied the existing subsequence matching algorithm without any extension, we would have to generate an index per each moving average order. Thus, supporting an arbitrary moving average order would cause serious overhead on storage space and insertion/deletion of data sequences. The proposed algorithm can use only one index for a preselected moving average order k and performs subsequence matching for an arbitrary order m(≤k). We prove that the proposed algorithm causes no false dismissal, i.e., it does not miss part of the final search result. The proposed algorithm can also use more than one index for improving search performance. We have evaluated the performance of the proposed algorithm through experiments. The results show that the proposed algorithm improves the performance by up to 2.7 times on the average compared with the sequential scan algorithm. Since the proposed subsequence matching algorithm works better with smaller selectivities, it is suitable for practical applications. The proposed algorithm can be applied in a variety of areas that use the moving average transform. They include finding stock items with similar trends in prices, estimation of sales for a product, and weather forecast through temperature data analysis.

정규화 변환을 지원하는 스트리밍 시계열 매칭 알고리즘

노웅기(Woong-Kee Loh),문양세(Yang-Sae Moon),김영국(Young-Kuk Kim) 한국정보과학회 2006 정보과학회논문지 : 데이타베이스 Vol.33 No.6

최근에 센서 및 모바일 장비들의 발전으로 인하여 이러한 장비들로부터 생성된 대량의 데이타 스트림(data stream)의 처리가 중요한 연구 과제가 되고 있다. 데이타 스트림 중에서 연속되는 시점에 얻어진 실수 값들의 스트림을 스트리밍 시계열(streaming time-series)이라 한다. 스트리밍 시계열에 대한 유사성 매칭은 여러 가지 고유 특성에 의하여 기존의 시계열 데이타와는 다르게 처리되어야 한다. 본 논문에서는 정규화 변환(normalization transform)을 지원하는 스트리밍 시계열 매칭 문제를 해결하기 위한 효율적인 알고리즘을 제안한다. 기존에는 스트리밍 시계열을 아무런 변환 없이 비교하였으나, 본 논문에서는 정규화 변환된 스트리밍 시계열을 비교한다. 정규화 변환은 절대적인 값은 달라도 유사한 변동 경향을 가지는 시계열 데이타를 찾기 위하여 유용하다. 본 논문의 공헌은 다음과 같다. (1) 기존의 정규화 변환을 지원하는 서브시퀀스 매칭 알고리즘[4]에서 제시된 정리(theorem)를 이용하여 정규화 변환을 지원하는 스트리밍 시계열 매칭 문제를 풀기 위한 간단한 알고리즘을 제안한다. (2) 검색 성능을 향상시키기 위하여 간단한 알고리즘을 k (≥ 1) 개의 인덱스를 이용하는 알고리즘으로 확장한다. (3) 주어진 k에 대하여, 확장된 알고리즘의 검색 성능을 최대화하기 위해 k 개의 인덱스를 생성할 최적의 윈도우 길이를 선택하기 위한 근사 방법(approximation)을 제시한다. (4) 스트리밍 시계열의 연속성(continuity) 개념[8]에 기반하여, 현재 시점 t?에서의 스트리밍 서브시퀀스에 대한 검색과 동시에 미래 시점 (t? + m - 1) (m ≥ 1)까지의 검색 결과를 한번의 인덱스 검색으로 구할 수 있도록 재차 확장한 알고리즘을 제안한다. (5) 일련의 실험을 통하여 본 논문에서 제안된 알고리즘들 간의 성능을 비교하고, k 및 m 값의 변화에 따라 제안된 알고리즘들의 검색 성능 변화를 보인다. 본 논문에서 제시한 정규화 변환 스트리밍 시계열 매칭 문제에 대한 연구는 이전에 수행된 적이 없으므로 순차 검색(sequential scan) 알고리즘과 성능을 비교한다. 실험결과, 제안된 알고리즘은 순차 검색에 비하여 최대 13.2배까지 성능이 향상되었으며, 인덱스의 개수 k가 증가함에 따라 검색 성능도 함께 증가하였다. According to recent technical advances on sensors and mobile devices, processing of data streams generated by the devices is becoming an important research issue. The data stream of real values obtained at continuous time points is called streaming time-series. Due to the unique features of streaming time-series that are different from those of traditional time-series, similarity matching problem on the streaming time-series should be solved in a new way. In this paper, we propose an efficient algorithm for streaming time-series matching problem that supports normalization transform. While the existing algorithms compare streaming time-series without any transform, the algorithm proposed in the paper compares them after they are normalization-transformed. The normalization transform is useful for finding time-series that have similar fluctuation trends even though they consist of distant element values. The major contributions of this paper are as follows. (1) By using a theorem presented in the context of subsequence matching that supports normalization transform[4], we propose a simple algorithm for solving the problem. (2) For improving search performance, we extend the simple algorithm to use k ( ≥ 1) indexes. (3) For a given k, for achieving optimal search performance of the extended algorithm, we present an approximation method for choosing k window sizes to construct k indexes. (4) Based on the notion of continuity[8] on streaming time-series, we further extend our algorithm so that it can simultaneously obtain the search results for m ( ≥ 1) time points from present t? to a time point (t? + m - 1) in the near future by retrieving the index only once. (5) Through a series of experiments, we compare search performances of the algorithms proposed in this paper, and show their performance trends according to k and m values. To the best of our knowledge, since there has been no algorithm that solves the same problem presented in this paper, we compare search performances of our algorithms with the sequential scan algorithm. The experiment result showed that our algorithms outperformed the sequential scan algorithm by up to 13.2 times. The performances of our algorithms should be more improved, as k is increased.