대화형 통신 순서열 패턴의 마이닝을 위한 효율적인 알고리즘 = An Efficient Algorithm for Mining Interactive Communication Sequence Patterns

국문 초록 (Abstract)

통신 기록 데이타는 이메일이나 인스턴스 메시지를 주고 받거나, 웹사이트에 접속하는 것과 같은 통신 이벤트들로 구성된다. 미국과 유럽연합을 포함한 여러 나라에서는 인터넷을 사용한 범죄의 조사와 발견을 위해서 통신 서비스 제공자에게 이런 데이타를 보관하도록 규정하고 있다. 보관되는 통신 기록 데이타의 크기가 매우 크기 때문에 치안당국이 이 데이타를 사용하기 위해서는 필요한 정보만을 효과적으로 추출해내는 방법이 필요하다. 본 논문에서는 발신자, 수신자, 통신발생시각의 세 가지 정보만 포함하는 통신 이벤트가 주어질 때, 의미 있는 정보 중 하나인 대화형 통신 순서열 패턴과 이러한 패턴의 마이닝 문제를 정의하고 그것을 해결하기 위해 Fast Discovering Interactive Communication Sequence Patterns(FDICSP)라 불리는 알고리즘을 제안한다. FDICSP는 길이가 짧은 대화형 통신 순서열을 조합하여 길이가 긴 대화형 통신 순서열을 생성해나가는데, 대화형 통신 순서열의 특성에 초점을 맞춘 작업을 통해 효율적으로 대화형 통신 순서열 패턴을 찾는다.

다국어 초록 (Multilingual Abstract)

Communication log data consist of communication events such as sending and receiving e-mail or instance message and visiting web sites, etc. Many countries including USA and EU enforce the retention of these data on the communication service providers for the purpose of investigating or detecting criminals through the Internet. Because size of the retained data is very large, the efficient method for extracting valuable information from the data is needed for Law Enforcement Authorities to use the retained data. This paper defines the Interactive Communication Sequence Patterns(ICSPs) that is the important information when each communication event in communication log data consists of sender, receiver, and timestamp of this event. We also define a Mining(ICSPM) problem to discover such patterns and propose a method called Fast Discovering Interactive Communication Sequence Pattern(FDICSP) to solve this problem. FDICSP focuses on the characteristics of ICS to reduce the search space when it finds longer sequences by using shorter sequences. Thus, FDICSP can find Interactive Communication Sequence Patterns efficiently.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 대화형 통신 순서열(Interactive Communication Sequence)
• 3. FDICSP 알고리즘
• 4. 실험
• 5. 결론
• 참고문헌

참고문헌 (Reference)

1 "Telecommunications security; Lawful Interception(LI); Requirements of Law Enforcement Agencies" ETSI

2 "Telecommunications security; Lawful Interception(LI); Handover interface for the lawful interception of telecommunications traffic" ETSI

3 M. Zaki, "SPADE: An Efficient Algorithm for Mining Frequent Sequences" 40 : 31-60, 2001

4 J. Pei, "PrefixSpan: Mining Sequential Patterns Efficiently by Prefix-Projected Pattern Growth" 215-224, 2001

5 R. Agrawal, "Mining Sequential Patterns: Generalizations and Performance Improvements" 3-17, 1996

6 C. Yu, "Mining Sequential Patterns from Multidimensional Sequence Data" 17 (17): 136-140, 2005

7 J. Pei, "Mining Sequential Patterns by Pattern-Growth: The PrefixSpan Approach" 16 : 1424-1440, 2004

8 C. Raissi, "Mining Multidimensional Sequential Patterns over Data Streams" 5182 : 263-272, 2008

9 Philip A. Branch, "Lawful Interception of the Internet" Centre for Advanced Internet Architectures

10 M. Plantevit, "HYPE: mining hierarchical sequential patterns" 19-26, 2006

11 R. Agrawal, "Fast algorithms for mining association rules" 487-499, 1994

12 H. Mannila, "Discovering frequent episodes in sequences" 210-215, 1995

13 "DIRECTIVE 2006/24/EC OF THE EUROPEAN PARLIAMENT AND OF THE COUNCIL of 15 March 2006 on the retention of data generated or processed in connection with the provision of publicly available electronic communications services or of public communications networks and amending Directive 2002/58/EC"

14 S. Aseervatham, "Bitspade: A Lattice-Based Sequential Pattern Mining Algorithm Using Bitmap Representation" 792-797, 2006