데이터 스트림에 대한 기존의 패턴 분석알고리즘은 대부분 속도 향상과 효율적인 메모리 사용에 대하여 연구되어 왔다. 그러나 기존의 연구들은 새로운 패턴을 가진 데이터 스트림이 입력되었을 경우, 이 전에 분석된 패턴을 버리고 다시 패턴을 분석하여야 한다. 이러한 방법은 데이터의 실시간적인 패턴 분석을 필요로 하는 실제 환경에서는 많은 속도와 계산 비용이 소모된다. 본 논문에서는 끊임없이 입력되는 데이터 스트림의 패턴을 실시간으로 분석하는 방법을 제안한다. 이 것은 먼저 빠르게 패턴을 분석하고 그 다음부터는 이전에 분석된 패턴을 효율적으로 갱신하여 실시간적인 패턴을 얻어내는 방법이다. 데이터 스트림이 입력되면 시간 기반 윈도우로 나누어 여러 개의 순차들을 생성한다. 그리고 생성된 순차들의 정보는 해시 테이블에 입력되어 정해진 개수의 순차가 해시 테이블에 채워질 때마다 해시 테이블에서 패턴을 분석해 낸다. 이렇게 분석된 패턴은 패턴 트리를 형성하게 되고, 이 후에 새로 분석된 패턴들은 이 패턴 트리 안의 패턴 별로 갱신하여 현재 패턴을 유지하게 된다. 새로운 패턴 추가를 위해 패턴을 분석할 때 이전에 이미 발견된 패턴이 Suffix로 나올 수 있다. 그러면 패턴 트리에서 이 전 패턴으로의 포인터를 생성하여 중복되는 패턴 분석으로 인한 계산 시간의 낭비를 방지한다. 그리고 FIFO방법을 사용하여 오랫동안 입력이 안 된 패턴을 손쉽게 제거한다. 패턴이 조금씩 바뀌는 데이터 스트림 환경에서 RSP-DS가 기존의 알고리즘보다 우수하다는 것을 성능 평가를 통하여 증명하였다. 또한 패턴 분석을 수행할 데이터 순차의 개수와 자주 등장하는 데이터를 판별하는 기준을 조절하여 성능의 변화를 살펴보았다.
데이터 스트림에 대한 기존의 패턴 분석 알고리즘은 대부분 속도 향상과 효율적인 메모리 사용에 대하여 연구되어 왔다. 그러나 기존의 연구들은 새로운 패턴을 가진 데이터 스트림이 입력되었을 경우, 이 전에 분석된 패턴을 버리고 다시 패턴을 분석하여야 한다. 이러한 방법은 데이터의 실시간적인 패턴 분석을 필요로 하는 실제 환경에서는 많은 속도와 계산 비용이 소모된다. 본 논문에서는 끊임없이 입력되는 데이터 스트림의 패턴을 실시간으로 분석하는 방법을 제안한다. 이 것은 먼저 빠르게 패턴을 분석하고 그 다음부터는 이전에 분석된 패턴을 효율적으로 갱신하여 실시간적인 패턴을 얻어내는 방법이다. 데이터 스트림이 입력되면 시간 기반 윈도우로 나누어 여러 개의 순차들을 생성한다. 그리고 생성된 순차들의 정보는 해시 테이블에 입력되어 정해진 개수의 순차가 해시 테이블에 채워질 때마다 해시 테이블에서 패턴을 분석해 낸다. 이렇게 분석된 패턴은 패턴 트리를 형성하게 되고, 이 후에 새로 분석된 패턴들은 이 패턴 트리 안의 패턴 별로 갱신하여 현재 패턴을 유지하게 된다. 새로운 패턴 추가를 위해 패턴을 분석할 때 이전에 이미 발견된 패턴이 Suffix로 나올 수 있다. 그러면 패턴 트리에서 이 전 패턴으로의 포인터를 생성하여 중복되는 패턴 분석으로 인한 계산 시간의 낭비를 방지한다. 그리고 FIFO방법을 사용하여 오랫동안 입력이 안 된 패턴을 손쉽게 제거한다. 패턴이 조금씩 바뀌는 데이터 스트림 환경에서 RSP-DS가 기존의 알고리즘보다 우수하다는 것을 성능 평가를 통하여 증명하였다. 또한 패턴 분석을 수행할 데이터 순차의 개수와 자주 등장하는 데이터를 판별하는 기준을 조절하여 성능의 변화를 살펴보았다.
Existed pattern analysis algorithms in data streams environment have researched performance improvement and effective memory usage. But when new data streams come, existed pattern analysis algorithms have to analyze patterns again and have to generate pattern tree again. This approach needs many cal...
Existed pattern analysis algorithms in data streams environment have researched performance improvement and effective memory usage. But when new data streams come, existed pattern analysis algorithms have to analyze patterns again and have to generate pattern tree again. This approach needs many calculations in real situation that needs real time pattern analysis. This paper proposes a method that continuously analyzes patterns of incoming data streams in real time. This method analyzes patterns fast, and thereafter obtains real time patterns by updating previously analyzed patterns. The incoming data streams are divided into several sequences based on time based window. Informations of the sequences are inputted into a hash table. When the number of the sequences are over predefined bound, patterns are analyzed from the hash table. The patterns form a pattern tree, and later created new patterns update the pattern tree. In this way, real time patterns are always maintained in the pattern tree. During pattern analysis, suffixes of both new pattern and existed pattern in the tree can be same. Then a pointer is created from the new pattern to the existed pattern. This method reduce calculation time during duplicated pattern analysis. And old patterns in the tree are deleted easily by FIFO method. The advantage of our algorithm is proved by performance comparison with existed method, MILE, in a condition that pattern is changed continuously. And we look around performance variation by changing several variable in the algorithm.
Existed pattern analysis algorithms in data streams environment have researched performance improvement and effective memory usage. But when new data streams come, existed pattern analysis algorithms have to analyze patterns again and have to generate pattern tree again. This approach needs many calculations in real situation that needs real time pattern analysis. This paper proposes a method that continuously analyzes patterns of incoming data streams in real time. This method analyzes patterns fast, and thereafter obtains real time patterns by updating previously analyzed patterns. The incoming data streams are divided into several sequences based on time based window. Informations of the sequences are inputted into a hash table. When the number of the sequences are over predefined bound, patterns are analyzed from the hash table. The patterns form a pattern tree, and later created new patterns update the pattern tree. In this way, real time patterns are always maintained in the pattern tree. During pattern analysis, suffixes of both new pattern and existed pattern in the tree can be same. Then a pointer is created from the new pattern to the existed pattern. This method reduce calculation time during duplicated pattern analysis. And old patterns in the tree are deleted easily by FIFO method. The advantage of our algorithm is proved by performance comparison with existed method, MILE, in a condition that pattern is changed continuously. And we look around performance variation by changing several variable in the algorithm.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
따라서 사용자가 계속해서 실시간으로 분석된 패턴을 요구할 경우 데이터 스트림이 입력될 때마다 계속해서 패턴 분석을 실행해야 하는 단점이 있다. 본 논문에서는 계속해서 변하는 데이터 스트림의 패턴을 실시간으로 분석하는 방법을 제안한다. 제안하는 알고리즘은 입력되는 데이터 스트림를 시간 기반 윈도우로 나누어 여러 개의 순차들을 만든다.
가설 설정
4: PT에서 pat 와 pat의 하위 패턴들을 지움. 이때 하위 패턴에 포인터가 있을 경우 포인터는 따라가서 지우지는 않음
8. 구해진 진행패턴이 최종패턴에 추가된다.
제안 방법
MILEe PrefixSpan을 확장하여 단순한 순차 패턴 분석을 여러 데이터 스트림 사이의 패턴 분석에 적용하였다. 그러나 실제 상황에서 각각의 데이터 스트림의 패턴은 끊임없이 바뀔 수 있다.
Seql 의 , Seq2의 , Seq3의 를q3에 나오는 데이터의 nSuffix가 큰 기준으로 조사한다.
<e> 의req도 2이므로 패턴이 된다. 그리고 각 순차에서의 Suffix들을 조사한다. 즉, Seq2에서 <>와 Seq3에서 <b, c>에서3에 등장하는 데이터들의 nSuffix가 큰 기준으로 조사한다.
이 중에서 많은 수의 패턴을 손쉽게 삭제 할 수 있는 FIFO를 간단하게 수정하여 패턴 삭제에 이용하겠다. 먼저 입력된 패턴의 시간별로 FIFO를 생성한다.
이러한 방법으로 변하는 패턴을 인식하려면 계속해서 알고리즘을 처음부터 수행해야 하는 단점을 가지고 있다. 제안하는 RSP-DS 방법은 발견된 패턴으로 패턴 트리를 구축하고 조금씩 변하는 패턴들을 이용하여 패턴 트리를 가지별로 갱신하여 실시간으로 패턴을 분석해내는 방법을 제안하였다. RSP-DSe 데이터 스트림 패턴 분석 알고리즘인 MILE을 기본으로 하여 작성되었다.
본 논문에서는 계속해서 변하는 데이터 스트림의 패턴을 실시간으로 분석하는 방법을 제안한다. 제안하는 알고리즘은 입력되는 데이터 스트림를 시간 기반 윈도우로 나누어 여러 개의 순차들을 만든다. 이러한 순차들은 데이터를 키로 갖는 해시 테이블로 관리가 되며, 정해진 개수의 순차가 입력될 경우 매번 해시테이블에서 패턴 분석이 이루어진다.
즉, Seq2에서 와 Seq3에서 에서3에 등장하는 데이터들의 nSuffix가 큰 기준으로 조사한다.
이론/모형
제안하는 RSP-DS 방법은 발견된 패턴으로 패턴 트리를 구축하고 조금씩 변하는 패턴들을 이용하여 패턴 트리를 가지별로 갱신하여 실시간으로 패턴을 분석해내는 방법을 제안하였다. RSP-DSe 데이터 스트림 패턴 분석 알고리즘인 MILE을 기본으로 하여 작성되었다. 그러나 실험을 통하여 계속해서 변 하는 패턴을 인식하는 과정은 MILE보다 높은 성능을 보인다는 것은 증명하였다.
MILE에서는 다수의 데이터 스트림 소스에서 입력을 받아 튜플 기반 윈도우로 데이터 스트림을 나누어 다수의 순차를 생성한다. 나누어진 순차들은 PrefixSpan방법과 같이 방법으로 패턴 분석에 이용된다. 그러나 PrefixSpan과는 다르게 현재 생성하고 있는 패턴의 Suffix가 이미 패턴 트리에 생성이 되어 있다면 더 이상의 패턴 생성을 중단하고 이전 패턴으로 포인터를 형성하는 방법으로 패턴 트리를 구축한다.
성능/효과
RSP-DSe 데이터 스트림 패턴 분석 알고리즘인 MILE을 기본으로 하여 작성되었다. 그러나 실험을 통하여 계속해서 변 하는 패턴을 인식하는 과정은 MILE보다 높은 성능을 보인다는 것은 증명하였다. 이것는 MILEe 새로운 순차가 입력될 때마다 매번 트리를 다시 생성하지만, RSP-DS는 이 전에 생성된 트리를 수정하여 현재 패턴을 유지하기 때문이다.
이것는 MILEe 새로운 순차가 입력될 때마다 매번 트리를 다시 생성하지만, RSP-DS는 이 전에 생성된 트리를 수정하여 현재 패턴을 유지하기 때문이다. 그리고 빈발 항목을 판단하는 min_sup 와 패턴 분석하는데 이용하는 순차의 개수에 따라 알고리즘의 성능이 조절될 수 있다는 것을 발견하였다. 따라서 이 두 변수의 적절한 선택으로 성능의 최적화를 이루어 낼 수 있다.
실험의 결과들을 통하여 RSP-DS 방법을 이용하면 상황에 따라 변하는 패턴을 빠르게 알아낼 수 있다는 사실을 알아내었다. 특히 과학적 실험의 성능 측정, 네트워크 패킷 모니터링, 교통량 측정과 같이 지속적으로 모니터링을 하면서 패턴의 이 상치를 발견해야만 하는 응용에서 효과적으로 쓰일 수 있다.
후속연구
RSP-DS는 패턴이 일정한 시간 주기로 등장한다. 는 것을 가정하고 있기 때문에 향후에 패턴의 주기가 변하는 데이터 스트림에서의 패턴 분석이 연구가 되 어져야 한다. 또한 패턴의 변화가 거의 발생하지 않은 환경에서 RSP-DS와 같이 계속하여 패턴을 분석하는 방법은 불필요한 연산을 초래한다.
또한 패턴의 변화가 거의 발생하지 않은 환경에서 RSP-DS와 같이 계속하여 패턴을 분석하는 방법은 불필요한 연산을 초래한다. 따라서 데이터 스트림의 패턴이 변하고 있는지 빠르게 알아낼 수 있는 알고리즘의 연구도 이루어져야 할 것이다.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.