시계열 데이터베이스에서 단일 색인을 사용한 정규화 변환 지원 서브시퀀스 매칭

문양세,김진호,노웅기,Moon Yang-Sae,Kim Jin-Ho,Loh Woong-Kee 한국정보처리학회 2006 정보처리학회논문지D Vol.13 No.4

정규화 변환은 시계열 시퀀스를 구성하는 엔트리들의 전체적인 패턴을 분석하는데 매우 유용하다. 본 논문에서는 단일 색인을 사용한 정규화 변환 지원 서브시퀀스 매칭 방법을 제안한다. 기존의 정규화 변환 지원 서브시퀀스 매칭 방법은 다양한 길이의 질의 시퀀스를 지원하기 위하여 여러 개의 색인을 생성해야 하고, 이에 따라 색인 저장 공간의 오버헤드와 색인 관리의 오버헤드가 발생한다. 본 논문에서는 하나의 색인을 사용하면서도 다양한 길이의 질의 시퀀스에 대한 정규화 변환을 지원하는 효율적인 서브시퀀스 매칭 방법을 제안한다. 이를 위하여, 우선 정규화 변환을 일반화한 포함-정규화 변환(inclusion-normalization transform) 개념을 제시한다. 포함 정규화 변환이란 색인에 저장할 윈도우에 대해서 해당 윈도우를 포함하는 서브시퀀스의 평균과 표준편차로 정규화하는 것으로서, 기본적인 정규화 변환을 윈도우 및 서브시퀀스 개념을 사용하여 확장한 것이다. 다음으로, 포함-정규화 변환을 기존 서브시퀀스 매칭 연구에 적용하기 위한 이론적 근거를 정리로서 제시하고 증명한다. 그리고, 이 방안을 구현하기 위한 색인 구성 알고리즘 및 서브시퀀스 매칭 알고리즘을 각각 제시한다. 실제 주식 데이터에 대한 실험 결과, 제안한 방법은 기존 방법에 비해 최대 $2.5{\sim}2.8$배까지 성능을 향상 시킨 것으로 나타났다. 본 논문에서 제안한 정규화 변환 지원 서브시퀀스 매칭은 정규화 변환 이외의 다른 변환을 지원하는 서브시퀀스 매칭으로 일반화 될 수 있다. 따라서, 제안한 방법은 정규화 변환을 포함하는 많은 다른 종류의 변환을 지원하는 서브시퀀스 매칭에 폭넓게 적용될 수 있는 좋은 연구결과라 사료된다. Normalization transform is very useful for finding the overall trend of the time-series data since it enables finding sequences with similar fluctuation patterns. The previous subsequence matching method with normalization transform, however, would incur index overhead both in storage space and in update maintenance since it should build multiple indexes for supporting arbitrary length of query sequences. To solve this problem, we propose a single index approach for the normalization transformed subsequence matching that supports arbitrary length of query sequences. For the single index approach, we first provide the notion of inclusion-normalization transform by generalizing the original definition of normalization transform. The inclusion-normalization transform normalizes a window by using the mean and the standard deviation of a subsequence that includes the window. Next, we formally prove correctness of the proposed method that uses the inclusion-normalization transform for the normalization transformed subsequence matching. We then propose subsequence matching and index building algorithms to implement the proposed method. Experimental results for real stock data show that our method improves performance by up to $2.5{\sim}2.8$ times over the previous method. Our approach has an additional advantage of being generalized to support many sorts of other transforms as well as normalization transform. Therefore, we believe our work will be widely used in many sorts of transform-based subsequence matching methods.

시계열 스트림 데이터 상에서 핸드헬드 디바이스를 위한 효율적인 스트림 시퀀스 매칭 알고리즘

문양세,노웅기,Moon Yang-Sae,Loh Woong-Kee 한국통신학회 2006 韓國通信學會論文誌 Vol.31 No.8B

핸드헬드 디바이스의 경우, 반복 작업에 대한 CPU 연산 최소화가 성능에 중요한 요소이다. 본 논문에서는 주식 데이터, 네트워크 트래픽, 센서 데이터 등의 시계열 스트림 데이터 상에서 유사 시퀀스를 효율적으로 찾아내는 핸드헬드 디바이스용 알고리즘을 제시한다. 이를 위하여, 우선 시계열 스트림 데이터 상에서 유사 시퀀스를 찾아내는 문제를 스트림 시퀀스 매칭(stream sequence matching)으로 정형적으로 정의한다. 다음으로, 기존의 서브시퀀스 매칭에서 사용했던 윈도우 구성법을 적용하여, 스트림 시퀀스 매칭을 효율적으로 처리하는 윈도우 기반 접근법을 제안한다. 그리고 이러한 윈도우 기반 접근법을 가능하게 하는 윈도우 MBR(window MBR) 개념을 제시하고, 이 개념을 사용하면 스트림 시퀀스 매칭을 정확하게 수행할 수 있음을 증명한다. 또한, 윈도우 기반 접근법에 기반한 두 가지 스트림 시퀀스 매칭 알고리즘을 제안한다. 마지막으로, 분석과 실험을 통해 제안한 알고리즘이 단순 접근법에 비해 CPU 연산을 크게 줄이고 성능을 향상시킴을 보인다. 이 같은 결과를 볼 때, 제안한 방법은 CPU 연산 능력이 부족한 핸드헬드 디바이스의 내장형 알고리즘으로 매우 적합하다고 사료된다. For the handhold devices, minimizing repetitive CPU operations such as multiplications is a major factor for their performances. In this paper, we propose efficient algorithms for finding similar sequences from streaming time-series data such as stock prices, network traffic data, and sensor network data. First, we formally define the problem of similar subsequence matching from streaming time-series data, which is called the stream sequence matching in this paper. Second, based on the window construction mechanism adopted by the previous subsequence matching algorithms, we present an efficient window-based approach that minimizes CPU operations required for stream sequence matching. Third, we propose a notion of window MBR and present two stream sequence matching algorithms based on the notion. Fourth, we formally prove correctness of the proposed algorithms. Finally, through a series of analyses and experiments, we show that our algorithms significantly outperform the naive algorithm. We believe that our window-based algorithms are excellent choices for embedded stream sequence matching in handhold devices.

유사 시퀀스 매칭을 위한 하이브리드 저차원 변환

문양세,김진호,Moon, Yang-Sae,Kim, Jin-Ho 한국정보처리학회 2008 정보처리학회논문지D Vol.15 No.1

유사 시퀀스 매칭에서는 고차원인 시퀀스를 저차원의 점으로 변환하기 위하여 저차원 변환을 사용한다. 그런데, 이러한 저차원 변환은 시계열 데이터의 종류에 따라 인덱싱 성능에 있어서 큰 차이를 나타낸다. 즉, 어떤 저차원 변환을 선택하느냐가 유사 시퀀스 매칭의 인덱싱 성능에 큰 영향을 주게 된다. 이 문제를 해결하기 위하여, 본 논문에서는 하나의 인덱스에서 두 개 이상의 저차원 변환을 통합하여 사용하는 하이브리드 접근법을 제안한다. 먼저, 하나의 시퀀스에 두 개 이상의 저차원 변환을 적용하는 하이브리드 저차원 변환의 개념을 제안하고, 변환된 시퀀스간의 거리를 계산하는 하이브리드 거리를 정의한다. 다음으로, 이러한 하이브리드 접근법 사용하면 유사 시퀀스 매칭을 정확하게 수행할 수 있음을 정형적으로 증명한다. 또한, 제안한 하이브리드 접근법을 사용하는 인덱스 구성 및 유사 시퀀스 매칭 알고리즘을 제시한다. 다양한 시계열 데이터에 대한 실험 결과, 제안한 하이브리드 접근법은 단일 저차원 변환을 사용하는 경우에 비해서 우수한 성능을 보이는 것으로 나타났다. 이 같은 결과를 볼 때, 제안한 하이브리드 접근법은 다양한 특성을 지닌 다양한 시계열 데이터에 두루 적용될 수 있는 우수한 방법이라 사료된다. We generally use lower-dimensional transformations to convert high-dimensional sequences into low-dimensional points in similar sequence matching. These traditional transformations, however, show different characteristics in indexing performance by the type of time-series data. It means that the selection of lower-dimensional transformations makes a significant influence on the indexing performance in similar sequence matching. To solve this problem, in this paper we propose a hybrid approach that integrates multiple transformations and uses them in a single multidimensional index. We first propose a new notion of hybrid lower-dimensional transformation that exploits different lower-dimensional transformations for a sequence. We next define the hybrid distance to compute the distance between the transformed sequences. We then formally prove that the hybrid approach performs the similar sequence matching correctly. We also present the index building and the similar sequence matching algorithms that use the hybrid approach. Experimental results for various time-series data sets show that our hybrid approach outperforms the single transformation-based approach. These results indicate that the hybrid approach can be widely used for various time-series data with different characteristics.

통신이력을 사용한 교우 친밀도 분석

문양세(Yang-Sae Moon),최훈영(Hun-Young Choi),김혜숙(Hea-Suk Kim),김진호(Jinho Kim) 한국정보과학회 2006 한국정보과학회 학술발표논문집 Vol.33 No.1

최근 청소년의 교우관계에 있어서 집단 따돌림이 사회적으로 큰 문제가 되고 있다. 본 논문에서는 학생들의 교우관계를 보다 객관적으로 분석하는 방법을 제안한다. 우선 분석을 위한 객관적인 데이터로 교우관계 정보를 묵시적으로 내포하고 있는 통신이력 데이터를 사용한다. 다음으로 교우간 친밀도(degree of familiarity) 개념을 정형적으로 정의하고, 여러 통신도구에서 발생한 통신이력 데이터를 기반으로 교우간 친밀도를 수학적으로 계산하는 방법을 제안한다. 다음으로, 계산한 교우간 친밀도를 사용하여 집단 따돌림의 가능성이 높은 학생을 파악한다. 이는 집단 따돌림 가능성이 높은 학생은 다른 학생으로부터의 통신 시도가 적을 것이라는 직관에 기반한다. 마지막으로, 제안한 방법의 실용성을 입증하기 위하여, 실제 구현 및 분석 실험을 수행하고, 그 의미를 해석한다. 이 같은 결과를 볼 때, 본 연구는 학생들의 교우관계를 보다 객관적으로 파악할 수 있는 매우 우수한 결과라 사료된다.

부분 집계 근사법의 MBR-안전 성질을 이용한 효율적인 시계열 서브시퀀스 매칭

문양세(Yang-Sae Moon) 한국정보과학회 2007 정보과학회논문지 : 데이타베이스 Vol.34 No.6

본 논문에서는 부분 집계 근사법(Piecewise Aggregation Approximation: PAA)이 MBR-안전(MBR-safe) 성질을 가짐을 보이고, 이를 사용한 효율적인 서브시퀀스 매칭 방법을 제안한다. MBR-안전 변환이란 고차원 MBR을 직접 변환한 저차원 MBR이 개별 고차원 시퀀스가 변환된 저차원 시퀀스를 모두 포함하는 변환을 의미한다. 이와 같은 MBR-안전 변환을 사용하면 고차원 MBR을 직접 저차원 MBR로 변환할 수 있어 유사 시퀀스 매칭에서 필요한 저차원 변환 횟수를 크게 줄일 수 있다. 또한, PAA는 계산이 간단하고 성능이 우수한 저차원 변환으로 알려져 있다. 이에 따라, 본 논문에서는 이들 두 개념의 장점을 통합하기 위하여, 기존의 PAA가 MBR-안전 성질을 가짐을 확인하고, 이를 사용하여 서브 시퀀스 매칭의 성능을 개선한다. 본 논문의 공헌은 다음과 같다. 첫째, PAA 기반의 MBR 저차원 변환인 mbrPAA를 제안하고, mbrPAA가 MBR-안전함을 정형적으로 증명한다. 둘째, mbrPAA 기반의 새로운 서브시퀀스 매칭 방법을 제안하고, 이 방법의 정확성을 증명한다. 셋째, 서브시퀀스 매칭에서 엔트리 재사용 성질(entry reuse property)의 개념을 제시하고, 이 개념에 기반하여 고차원 MBR을 효율적으로 구성하는 방법을 제안한다. 넷째, 실험을 통해 mbrPAA의 우수성을 입증한다. 실험 결과, 제안한 mbrPAA는 기존 방법에 비해 저차원 MBR 구성을 평균 24.2배 빠르게 수행하고, 서브시퀀스 매칭 성능을 최대 65.9%까지 향상시킨 것으로 나타났다. In this paper we address the MBR-safe property of Piecewise Aggregation Approximation(PAA), and propose an efficient subsequence matching method based on the MBR-safe PAA. A transformation is said to be MBR-safe if a low-dimensional MBR to which a high- dimensional MBR is transformed by the transformation contains every individual low-dimensional sequence to which a high-dimensional sequence is transformed. Using an MBR-safe transformation we can reduce the number of lower-dimensional transformations required in similar sequence matching, since it transforms a high-dimensional MBR itself to a low-dimensional MBR directly. Furthermore, PAA is known as an excellent lower-dimensional transformation since its computation is very simple, and its performance is superior to other transformations. Thus, to integrate these advantages of PAA and MBR-safeness, we first formally confirm the MBR-safe property of PAA, and then improve subsequence matching performance using the MBR-safe PAA. Contributions of the paper can be summarized as follows. First, we propose a PAA-based MBR-safe transformation, called mbrPAA, and formally prove the MBR-safeness of mbrPAA. Second, we propose an mbrPAA-based subsequence matching method, and formally prove its correctness of the proposed method. Third, we present the notion of entry reuse property, and by using the property, we propose an efficient method of constructing high-dimensional MBRs in subsequence matching. Fourth, we show the superiority of mbrPAA through extensive experiments. Experimental results show that, compared with the previous approach, our mbrPAA is 24.2 times faster in the low-dimensional MBR construction and improves subsequence matching performance by up to 65.9%.

고차원 MBR(Minimum Bounding Rectangle)의 저차원 변환

문양세(Yang-Sae Moon),최훈영(Hun-Young Choi),김범수(Bum-Su Kim),김진호(Jinho Kim) 한국정보과학회 강원지부 2007 한국정보과학회 강원지부 학술대회 논문집 Vol.1 No.1

지금까지는 고차원 점을 저차원 점으로 변환하는 연구가 많이 이루어졌다. 그런데, 실생활에서 발생하는 시퀀스 및 스트리밍 데이터는 많은 경우에 고차원 점이 아닌 고차원 MBR(Minimum Bounding Rectangle)로 모델링 된다. 이들 고차원 MBR을 다차원 인덱스에 저장하고 검색하기 위해서는 고차원 MBR에 대한 저차원 변환이 필요하다. 이에 따라, 본 논문에서는 고차원 MBR을 저차원 MBR로 직접 변환하는 MBR 저차원 변환의 정형적 방법을 제안한다. 이를 위해, 우선 고차원 MBR의 저차원 변환 개념을 정형적으로 정의한다. 다음으로, 이산 푸리에 변환(Discrete Fourier Transform: DFT)과 이산 코사인 변환(Discrete Cosine Transform: DCT)에 대한 MBR 저차원 변환의 단순 해결책으로서, MBR의 모든 꼭지점을 변환 대상으로 삼는 DFTnaive와 DCTnaive를 각각 제안한다. 그런 다음, 단순 해결책의 문제점인 많은 저차원 변환 횟수를 줄이기 위하여, 개선된 해결책인 DFTadv와 DCTadv를 제안한다. 본 논문에서는 이들 방법 모두가 MBR 저차원 변환을 바르게 수행함을 정리로서 제시하고 증명한다. 분석과 실험 결과, 개선된 해결책인 DFTadv와 DCTadv는 단순 해결책인 DFTnaive와 DCTnaive에 비해 저차원 변환 횟수를 획기적으로 줄이고 성능을 크게 향상시킨 것으로 나타났다.

통신이력 데이타에 기반한 교우관계 분석

문양세(Yang-Sae Moon),최훈영(Hun-Young Choi),김진호(Jinho Kim) 한국정보과학회 2006 정보과학회논문지 : 소프트웨어 및 응용 Vol.33 No.8

최근 청소년의 교우관계에 있어서 집단 따돌림과 불량 그룹이 사회적으로 큰 문제가 되고 있다. 본 논문에서는 학생들의 교우관계를 보다 객관적으로 분석하는 방법을 제안한다. 분석을 위한 객관적인 데이타로는 교우관계 정보를 묵시적으로 내포하고 있는 통신이력 데이타를 사용하며, 체계적 분석을 위하여 데이타 마이닝 기법을 활용한다. 제안하는 분석 방법은 다음과 같다. 첫째, 교우간 친밀도(degree of familiarity) 개념을 정형적으로 정의하고, 여러 통신도구에서 발생한 통신이력 데이타를 기반으로 교우간 친밀도를 수학적으로 계산하는 방법을 제안한다. 제안하는 방법은 학생 x가 y로 통신을 많이 시도할수록, 학생 x의 y에 대한 교우간 친밀도가 높다는 직관을 사용한다. 둘째, 계산한 교우간 친밀도를 사용하여 집단 따돌림의 가능성이 높은 학생을 파악한다. 이는 집단 따돌림 가능성이 높은 학생은 다른 학생으로부터의 통신 시도가 적을 것이라는 직관에 기반한다. 셋째, 교우간 친밀도를 데이타 마이닝 기법 중 하나인 클러스터링으로 분석하여 의미 있는 교우집단을 파악한다. 클러스터링 기법을 사용하기 위하여, 본 논문에서는 교우간 친밀도를 기반으로 교우간 유사도(similarity) 개념을 정형적으로 정의하고, 이를 사용하여 클러스터링을 수행한다. 마지막으로, 제안한 방법의 실용성을 입증하기 위하여, 실제 구현 및 분석 실험을 수행하고, 그 의미를 해석한다. 이 같은 결과를 볼 때, 본 연구는 학생들의 교우관계를 보다 객관적으로 파악할 수 있는 효과적인 방법론이라 사료된다. In recent years, bullied students and rogue groups in teenagers make many serious social problems. In this paper we propose a novel approach that more objectively analyzes peer relationships among students. As the data for objective analysis, we use communication history records that are collected from various communication tools such as telephones, e-mails, and messengers. We use the simple intuition that communication history records implicitly contain peer relationship information. And, we adopt data mining techniques for the more systematic analysis. The proposed peer relationship analysis consists of the following steps. First, we formally define the notion of degree of familiarity between friends, and present mathematical equations that compute the degree based on communication history records. In the proposed method, we use the intuition that the degree of familiarity from student x to student y becomes higher as x makes the more communications with y. Second, by using the degree of familiarity between students, we find out the students who are potentially bullied. This procedure is based on the assumption that a bullied student may have a very small number of history records from other students to him. Third, we adopt the clustering technique, one of the most representative data mining techniques, to find out meaningful student groups by using the degree of familiarity. To use the clustering technique, we formally define the notion of similarity between friends based on the degree of familiarity, and perform clustering using the notion. Last, to show the practicality of the proposed method, we have implemented the method and interpreted the meaning of the experimental results. Overall, we believe that our research result provides an effective framework that analyzes peer relationships more objectively and more systematically.

윈도우를 구성하는 방법의 이원성을 이용한 효율적인 시계열 서브시퀀스 매칭

문양세(Yang-Sae Moon),노웅기(Woong-Kee Loh),황규영(Kyu-Young Whang) 한국정보과학회 2001 정보과학회논문지 : 데이타베이스 Vol.28 No.1

서브시퀀스 매칭은 질의 시퀀스와 유사한 서브시퀀스를 가지는 데이타 시퀀스와 해당 서브시퀀스의 위치를 찾는 문제이다. 본 논문에서는 윈도우를 구성하는 방법의 이원성을 이용한 새로운 서브시퀀스 매칭 방법인 Dual-Match를 제안하고, 이 방법이 서브시퀀스 매칭의 성능을 획기적으로 향상시킬 수 있음을 보인다. Dual-Match는 윈도우를 구성하는 방법에 있어서 Faloutsos 등이 사용한 방법(간단히 FRM이라 한다)의 이원적 접근법이다. 즉, FRM에서는 데이타 시퀀스를 슬라이딩 윈도우로 나누고 질의 시퀀스를 디스조인트 윈도우로 나누는 방법을 사용한 반면, Dual-Match에서는 데이타 시퀀스를 디스조인트 윈도우로 나누고 질의 시퀀스를 슬라이딩 윈도우로 나누는 방법을 사용한다. FRM은 색인에 필요한 저장공간을 줄이기 위하여 개별 점 대신 최소 포함 사각형만을 저장함으로 인하여 많은 착오해답(유사하지 않은 후보 서브시퀀스)을 발생시켰다. Dual-Match는 FRM과 비슷한 크기의 저장공간에 개별 점을 직접 저장함으로써 이 문제를 해결한다. 실험 결과, Dual-Match는 많은 경우에 있어서 FRM에 비하여 후보 개수를 크게 줄이고 성능을 향상시켰다. 특히, 선택률이 낮은 경우(10-⁴ 이하)에는 후보 개수를 최대 8800배 까지 줄이고, 페이지 액세스 횟수를 최대 26.9배까지 줄였으며, 성능을 최대 430배까지 향상시켰다. 또한, 동일한 크기의 색인을 생성하는데 있어서 Dual-Match는 FRM보다 4.10~25.6배 빠르게 색인을 구성하였다. 이는 색인 구성 시에 CPU 오버헤드의 많은 부분을 차지하는 저차원 변환의 횟수를 FRM에 비해 크게 줄이기 때문이다. 이 같은 결과로 볼 때, Dual-Match는 대용량 데이타베이스에 대한 서브시퀀스 매칭의 성능을 크게 향상시킬 수 있는 획기적인 연구 결과라 믿는다. Subsequence matching is a solution to a problem of finding the data sequences containing subsequences similar to a given query sequence and of finding the offsets of these subsequences in the original data sequences. In this paper, we propose a new subsequence matching method, which we named Dual-Match. Dual-Match exploits duality in constructing windows and significantly improves overall performance. From the viewpoint of constructing windows, Dual-Match is a kind of dual approach of the subsequence matching method proposed by Faloutsos et al.(FRM in short). FRM divides data sequences into sliding windows, and the query sequence into disjoint windows. Conversely, Dual-Match divides data sequences into disjoint windows and the query sequence into sliding windows. To save storage space for the index, FRM stores minimum bounding rectangles rather than stores individual points representing windows, which causes a lot of false alarms(i.e., candidates that do not qualify). Dual-Match solves this problem by directly storing points without incurring excessive storage overhead. Experimental results show that, given the same amount of storage space, Dual-Match reduces the number of false alarms as well as improves overall performance over FRM. In particular, for low selectivities(less than 10-4), Dual-Match drastically reduces the number of candidates─down to as little as 1/8800 of that for FRM─, reduces the number of page accesses up to 26.9 times, and improves performance by up to 430-fold. Moreover, Dual-Match is 4.10~25.6 times faster than FRM in building indexes of approximately equal sizes. The main reason is that it requires far smaller number of transformations, which are the major part of the CPU overhead, than FRM does. Overall, these results indicate that our approach provides a new paradigm in subsequence matching that improves performance significantly especially in large database applications.

시계열 데이터의 프라이버시 보호 클러스터링에서 노이즈 평준화 효과

문양세(Yang-Sae Moon),김혜숙(Hea-Suk Kim) 한국정보과학회 2010 정보과학회 컴퓨팅의 실제 논문지 Vol.16 No.3

최근, 개인 데이터의 프라이버시 보호에 대한 문제가 대두됨에 따라 대용량 데이터를 대상으로 하는 데이터 마이닝 분야에서도 프라이버시 보호 문제에 대한 활발한 연구가 진행되고 있다. 데이터 마이닝에서의 프라이버시 보호 문제는 정보제공자에 의해 제공된 정보 중 민감한 개인 정보의 노출이 없이도 가능한 정확한 마이닝 결과를 얻는 것이다. 데이터 마이닝의 프라이버시 보호 기법에서는 데이터의 보호뿐만 아니라 결과의 정확도 또한 중요한 요인이다. 이에 따라, 본 논문에서는 시계열 데이터 클러스터링을 기반으로 랜덤 데이터 교란 기법에서 결과의 정확도를 높이는 기법으로 노이즈 평준화 개념을 제시한다. 기존의 랜덤 데이터 교란 기법은 데이터의 프라이버시는 잘 보호하지만 시계열간의 거리-순서가 보존되지 않아 결과의 정확도가 크게 떨어지는 문제점을 가진다. 이를 위해, 본 논문에서는 PAA를 기반으로 하는 노이즈 평준화 개념을 제시하고, 구체적인 예를 통해, 제안한 노이즈 평준화 개념이 랜덤 데이터 교란 기법에서 클러스터링 결과의 정확도를 높일 수 있음을 체계적으로 설명한다. Recently, there have been many research efforts on privacy-preserving data mining. In privacypreserving data mining, accuracy preservation of mining results is as important as privacy preservation. Random perturbation privacy-preserving data mining technique is known to well preserve privacy. However, it has a problem that it destroys distance orders among timeseries. In this paper, we propose a notion of the noise averaging effect of piecewise aggregate approximation (PAA), which can be preserved the clustering accuracy as high as possible in time-series data clustering. Based on the noise averaging effect, we define the PAA distance in computing distance. And, we show that our PAA distance can alleviate the problem of destroying distance orders in random perturbing time series.

KAIST Object Storage System with Variable - Length Attributes (KAOSS - VLA) : 가변길이 속성을 지원하는 관계형 데이타 저장 시스템

문양세(Yang-Sae Moon),조완섭(Wan-Sup Cho),김상욱(Sang-Wook Kim),김원영(Won-Young Kim),이영구(Young-Koo Lee),황규영(Kyu-Young Whang) 한국정보과학회 1994 한국정보과학회 학술발표논문집 Vol.21 No.2A

데이타베이스 관리 시스템은 데이타를 저장하고 관리하는 부분, 동시성 제어 및 회복 기능을 지원하는 부분, 질의어를 처리하는 부분, 질의어를 최적화하는 부분등으로 구성되어 있다. 저장 시스템은 데이타를 저장하고 관리하는 부분으로 데이타베이스의 엔진에 해당되어 성능에 직접적인 영향을 주는 중요한 역할을 한다. 본 논문에서는 UNLX 상에서 단일 사용자용 저장 시스템인 KAIST Object Storage System with Variable-Length Attributes(KAOSS-VLA)를 설계하고 구현하였다. 구현한 저장 시스템은 디스크를 관리하는 디스크 관리자, 버퍼 풀을 관리하는 버퍼 관리자, 데이타 페이지와 튜플을 관리하는 튜플 관리자, B+-트리 색인을 관리하는 B+-트리 관리자, 그리고 편리한 인터페이스를 제공하는 스캔 관라자의 다섯부분으로 구성되어 있다. 본 논문에서 구현한 저장 시스템은 첫째, 가변길이 속성을 허용함으로써 가변길이 튜플과 키를 지원하고, 둘째, 중복키와 다중키를 지원하며, 셋째, 두가지의 다른 스캔 인터페이스를 제공한다.