데이터베이스 연구회지(SIGDB)
Current Result Document : 2 / 2
| 한글제목(Korean Title) |
집합 유사 시퀀스 매칭을 위한 색인 구조 |
| 영문제목(English Title) |
An Index Structure for Efficient Set-based Similar Sequence Matching in Monotonically Increasing Data Domains |
| 저자(Author) |
조문증
Moon Jeung Joe
황우성
임효상
Woosung Hwang
Hyo-Sang Lim
|
| 원문수록처(Citation) |
VOL 37 NO. 01 PP. 0017 ~ 0030 (2021. 04) |
한글내용
(Korean Abstract) |
단조 증가 성질을 활용한 집합 유사 시퀀스 매칭 방법은 데이터 도메인이 포함하는 원소들이 사라지지 않고 시간이 흐름에 따라 지속적으로 추가되는 성질을 활용한다. 단조 증가 성질을 활용하면 집합 유사 시퀀스 매칭에서 큰 비용을 차지하는 교집합 계산량을 절약할 수 있다. 그러나, 해당 성질의 활용을 위해, 주어진 집합의 생성 시점이 특정 조건을 만족하는지 확인해야 하므로, 저장된 모든 집합을 확인하는 과정에서 성능 저하가 발생한다. 이러한 문제를 해결하기 위해, 본 논문은 집합 생성 시점을 이용하여 집합들을 색인할 수 있는 도메인 시간 역색인 구조를 제안한다. 제안된 색인 구조를 사용하면, 특정 시점 조건을 만족하는 집합만을 빠르게 찾아서 단조 증가 성질 활용의 효율성을 높일 수 있다. 성능평가 결과, 제안하는 색인 구조를 적용한 집합 유사 시퀀스 매칭 방법은 기존 방법보다 약 6배에서 15배의 수행 시간 단축을 통한 성능 향상을 보인다. |
영문내용
(English Abstract) |
The set-based similar sequence matching method using the monotonically increasing property utilizes the property that elements included in the data domain are continuously added over time without removing. By using the monotonically increasing property, the existing method reduces the computation cost for intersection which takes large proportion of the cost for the set-based similar sequence matching. However, for utilization of the monotonically increasing property, it is necessary to check whether the creation time of given sets satisfies a specific condition, which causes the performance degradation in the process of checking all the stored sets one by one. To solve this problem, we propose the domain time inverse index structure that indexes sets by the creation time of set. Using the proposed index structure, we can fastly find only the sets that satisfies the specific time condition, thereby increasing the efficiency of using the monotonically increasing property. Through experiments, the proposed set-based similar sequence matching using the domain time inverse index structure shows the performance improvement through the reduction in processing time by about 6 to 15 times compared to the existing method. |
| 키워드(Keyword) |
클라우드 컴퓨팅
클라우드 서비스
IT 전략
Cloud Computing
Cloud Service
IT Strategy
단조 증가
집합
집합 유사도
색인 구조
집합 유사 시퀀스 매칭
Monotonically increasing
Set
Set similarity
Index structure
Set-based similar sequence matching
|
| 파일첨부 |
PDF 다운로드
|
