웹 검색 엔진을 위한 중복문서 검색 알고리즘 분석 및 비교

안수한(Soohan Ahn),채용석(Yongsuk Chae),박희진(Heejin Park) 한국정보과학회 2011 한국정보과학회 학술발표논문집 Vol.38 No.2A

블로그 환경에서는 대부분의 중복문서들이 부분 중복문서인 경우가 많으며 앞서 실험해 본 결과 이러한 부분 중복문서들 중 대략 99%가 처음과 끝에서 조금 차이를 보이고 오직 1%만이 문서 중간에서 차이를 보였다. 이것을 찾아내는데 효율적인 알고리즘 중에 하나가 Central-match 알고리즘이다. 중복문서를 식별하는 것과 유사한 문제로는 원본문서 탐색문제(Origin detection problem)가 있다. 이 문제는 특정 문서가 들어오면 이 문서는 주로 어느 문서에서 추출되었는지를 가리키는 문제이다. 이 문제에 대한 효율적인 알고리즘으로는 Hailstorm&BE 알고리즘이 있다. 우리는 원본문서 탐색문제에 사용되는 Hailstorm&BE 알고리즘이 블로그 환경에서 중복문서를 찾아내는 블로그 중복 식별문제도 효과적으로 해결할 수 있을 것으로 예상하였고 이에 Hailstorm&BE 알고리즘을 중복문서를 식별할 수 있도록 변형 Central-match 알고리즘과 비교 분석하여 두 알고리즘 중 어느 알고리즘이 블로그 중복문서를 찾아내는데 더 적합한가를 실험해보았다. 그 결과 Hailstrom&BE 알고리즘이 원본문서 탐색문제뿐만 아니라 블로그 중복 식별문제에서도 효과적인 알고리즘이 될 수 있음을 보였다.

탠덤 질량 스펙트럼에서 2-PTM 검색을 위한 효율적인 알고리즘

안수한(Soohan Ahn),김현우(Hyunwoo Kim),박희진(Heejin Park),백은옥(Eunok Paek) 한국정보과학회 2013 한국정보과학회 학술발표논문집 Vol.2013 No.11

딜또는노딜 게임에서 딜금액 결정 모형

송설희,안수한,Song, Seolhee,Ahn, Soohan 한국데이터정보과학회 2014 한국데이터정보과학회지 Vol.25 No.4

본 논문에서 다루는 딜또는노딜 게임은 미국 NBC 방송국의 인기 오락 프로그램으로 여러 개의 단계로 구성되어 있다. 본 논문에서는 각 단계에서 제시되는 딜금액 결정 모형을 제한이 있는 회귀모형과 이차계획법을 이용하여 규명한다. 최종적으로 딜금액 결정 모형식과 관련하여 각 단계별로 선형식을 유도하고 딜금액이 선형식으로부터 얻어지는 값을 반올림한 정수값과 일치함을 시뮬레이션 자료를 이용하여 밝혔다. Deal-or-No-Deal game is a famous TV show program of NBC, USA, which is composed of 10 stages at most. At each stage from the first and the ninth, a banker suggests a deal price to participants. In this paper, we intend to reveal the banker's deal price model using a constrained linear model and quadratic program. As results, we provide a linear model in relation to the deal price at each stage and then show using simulation data that the deal price is equal to the nearest integer of the value to be obtained by the provided linear model.

마이닝을 이용한 이상트래픽 탐지: 사례 분석을 통한 접근

김정현(JungHyun Kim),안수한(Soohan Ahn),원유집(Youjip Won),이종문(Jongmoon Lee),이은영(Eunyung Lee) 한국정보과학회 2006 정보과학회논문지 : 정보통신 Vol.33 No.3

본 논문에서는 실제 인터넷 백본으로부터 일주일간 캡쳐한 트래픽을 대상으로 기초 통계 분석을 하고, 여기서 발생한 이상트래픽을 분석한다. 이상트래픽은 국외에서 국내로 유입되는 UDP 기반 트래픽에서 나타났다. 트래픽 자료에 대한 탐색적 분석 결과 packets/sec 분포와 bytes/sec 분포에서 이상트래픽이 발생할 경우에 나타나는 새로운 형태의 특성이 발견되었다. 본 연구에서는 이러한 이상트래픽의 원인이 되는 플로우를 분류하기 위하여 자율학습(unsupervised learning) 방법의 하나인 분류분석(k-means clustering)을 이용하였으며, 분류된 플로우의 특성분석을 토대로 발생한 이상트래픽은 DoS 공격의 일종에 의한 것으로 결론지었다. 또한 본 연구에서는 이상트래픽의 원인이 되는 플로우의 존재 시점을 탐지하기 위하여 새로운 기법을 제시한다. 제시된 기법은 분포적합검정(goodness of fit test)의 한 방법인 Cramer-Von-Misses 검정에서 쓰이는 통계량에 바탕을 두고 있으며 1초 단위의 탐지기법이다. 제시된 기법의 응용 결과, 이상트래픽의 존재 시점으로 판단된 시점과 DoS 공격으로 판단된 플로우들의 시점이 일치함을 확인할 수 있었다. In this paper, we collected the physical traces from high speed Internet backbone traffic and analyze the various characteristics of the underlying packet traces. Particularly, our work is focused on analyzing the characteristics of an anomalous traffic. It is found that in our data, the anomalous traffic is caused by UDP session traffic and we determined that it was one of the Denial of Service attacks. In this work, we adopted the unsupervised machine learning algorithm to classify the network flows. We apply the k-means clustering algorithm to train the learner. Via the Cramer-Von-Misses test, we confirmed that the proposed classification method which is able to detect anomalous traffic within 1 second can accurately predict the class of a flow and can be effectively used in determining the anomalous flows.

효율적인 메모리 공간 사용과 구조적 정보에 기반한 표절 탐색 알고리즘 설계

김재성(JaeSung Kim),안수한(SooHan Ahn),박희진(Heejin Park) 한국정보과학회 2012 한국정보과학회 학술발표논문집 Vol.39 No.2B

수동적 인터넷 측정을 위한 샘플링 기법 비교

김정현(Junghyun Kim),원유집(Youjip Won),안수한(Soohan Ahn) 대한전자공학회 2008 電子工學會論文誌-TC (Telecommunications) Vol.45 No.6

인터넷이 일상생활에서 중요한 위치를 차지함에 따라 인터넷에서 발생되는 트래픽의 특성을 밝히는 것은 매우 중요한 연구과제로 주목을 받고 있다. 그러나 인터넷 트래픽은 대용량이므로 쉽게 다룰 수 없다. 이러한 문제는 인터넷 트래픽 측정 연구에 가장 큰 장애다. 많은 연구자들은 다양한 샘플링 기법을 통해 트래픽을 다룰 수 있는 양으로 샘플링하여 분석하고 있다. 본 연구에서는 기존의 인터넷 측정 연구에서 사용된 샘플링 기법을 비교 분석하고, 가장 효과적인 샘플링 방안을 제시하고자 한다. 연구에 비교 사용된 샘플링 기법은 규칙적 샘플링, 단순 랜덤 샘플링, 층화 샘플링이며, 샘플링 단위는 1/10, 1/100, 1/1000을 사용하였다. 분석한 항목은 트래픽 크기 분석, 엔트로피 분석, 패킷 크기 분석이다. 단순 랜덤 샘플링은 무난한 결과를 보였고, (간격을 패킷 개수로 설정한) 규칙적 샘플링은 대상과 샘플링 강도에 상관없이 고른 결과를 보였다. 한편, 간격을 시간으로 설정한 규칙적 샘플링은 매우 좋지 않을 결과를 나타내었다. 전송층 프로토콜을 기준으로 층화 샘플링 수행할 경우 더욱 좋은 결과를 얻을 수 있었다. 연구 결과를 통해 샘플링 기법이 시간에 따른 트래픽의 흐름을 얼마나 잘 유지하는가가 샘플링 성능을 좌우함을 알 수 있었다. 또한 엔트로피 분석은 샘플링에 강하고, 이상 트래픽 탐지에 매우 적절함이 확인되었다. 그러나 병목 현상에 의한 트래픽 크기 감소는 잘못된 엔트로피 분석 결과를 유발할 수 있음을 발견하였다. 마지막으로, 패킷 크기 분포는 패킷 샘플링 방식이나 강도에 영향을 받지 않음을 발견하였다. Today, the Internet is a part of our life. For that reason, we regard revealing characteristics of Internet traffic as an important research theme. However, Internet traffic cannot be easily manipulated because it usually occupy huge capacity. This problem is a serious obstacle to analyze Internet traffic. Many researchers use various sampling techniques to reduce capacity of Internet traffic. In this paper, we compare several famous sampling techniques, and propose efficient sampling scheme. We chose some sampling techniques such as Systematic Sampling, Simple Random Sampling and Stratified Sampling with some sampling intensities such as 1/10, 1/100 and 1/1000. Our observation focused on Traffic Volume, Entropy Analysis and Packet Size Analysis. Both the simple random sampling and the count-based systematic sampling is proper to general case. On the other hand, time-based systematic sampling exhibits relatively bad results. The stratified sampling on Transport Layer Protocols, e.g.. TCP, UDP and so on, shows superior results. Our analysis results suggest that efficient sampling techniques satisfactorily maintain variation of traffic stream according to time change. The entropy analysis endures various sampling techniques well and fits detecting anomalous traffic. We found that a traffic volume diminishment caused by bottleneck could induce wrong results on the entropy analysis. We discovered that Packet Size Distribution perfectly tolerate any packet sampling techniques and intensities.

데이터 마이닝을 이용한 무선 인터넷 서비스 분류기법

이성진(Seongjin Lee),송종우(Jongwoo Song),안수한(Soohan Ahn),원유집(Youjip Won),장재성(Jae-Sung Chang) 한국정보과학회 2009 정보과학회논문지 : 정보통신 Vol.36 No.3

오늘 날 다양한 플랫폼을 기반으로 한 무선 네트워크 위에 실행되고 있는 수 많은 응용 프로그램은 서비스 운영자 입장에서 정확히 분류해내는 것은 중요하다. 이 연구는 WiBro 상용망에서 임의로 생성한 트래픽 데이터에서 다양한 응용프로그램들을 분류하는 것을 목적으로 한다. 분류기를 개발하는데 있어서 기존에 Flow기반으로 분류를 하는 대신 세션이라는 단위로 실험을 진행하였다. 이 단위를 사용하여 두 가지 분류 기법을 사용하였다: Classification and Regression Tree와 Support Vector Machine. 각 판별기는 생성된 변수들을 기반으로 판별을 시도하였을 때 CART의 경우 0.85%, SVM의 경우 0.94%의 오차를 보여 우수한 성능을 보였지만, 판별기의 구현과 결과 해석이 용이한 CART를 이용하여 판별시스템을 구축하는 것이 유리함을 보였다. It is a challenging work for service operators to accurately classify different services, which runs on various wireless networks based upon numerous platforms. This works focuses on design and implementation of a classifier, which accurately classifies applications, which are captured from WiBro Network. Notion of session is introduced for the classifier, instead of commonly used Flow to develop a classifier. Based on session information of given traffic, two classification algorithms are presented, Classification and Regression Tree and Support Vector Machine. Both algorithms are capable of classifying accurately and effectively with misclassification rate of 0.85%, and 0.94%, respectively. This work shows that classifier using CART provides ease of interpreting the result and implementation.

도시부 가로망에 대한 실시간 거시교통류 모니터링

엄기종(Eom Kijong),심정숙(Shim Jungsuk),안수한(Ahn Soohan),이청원(Lee Chungwon) 대한토목학회 2009 대한토목학회 학술대회 Vol.2009 No.10

트래픽 분산 그래프를 이용한 이상 호스트 탐지 기법

김정현(Junghyun Kim),원유집(Youjip Won),안수한(Soohan Ahn) 한국정보과학회 2009 정보과학회논문지 : 정보통신 Vol.36 No.2

오늘날의 인터넷은 일상생활에서 필수적인 요소가 되었으며, 인터넷의 이상 현상은 사회적 문제가 되고 있다. 이 때문에 인터넷 트래픽의 특성을 연구하기 위한 인터넷 측정 연구가 주목을 받고 있다. 특히 최근에는 트래픽 분산 그래프(TDG, Traffic Dispersion Graph)라는 새로운 트래픽 분석 기법이 제안되었다. TDG는 기존의 트래픽의 통계적 표현과 분석이 아닌, 그래프를 이용하여 네트워크 요소들의 상호작용을 표현하는 기법이다. 본 연구에서는 새로운 이상 탐지 기법의 패러다임과 TDG를 활용한 이상 탐지 기법을 제시한다. 기존의 이상 탐지 패러다임은 “비정상 패킷이나 플로우(Abnormal Packets or Flows)를 탐지하여 제거하자”는 것이지만, 본 연구에서는 “이상 트래픽의 근원이 되는 이상 호스트(Anomalous Hosts)를 탐지하여 이상 현상에 대응할 것”을 제안한다. 이를 위해서 TDG 클러스터링 기법(TDG Clustering Technique)을 고안하였다. 제안한 기법에 대한 실험에서 짧은 시간 안에 웜 바이러스(Worm Virus)에 감염된 호스트들을 찾아낼 수 있었고, 그 호스트들이 발생하는 이상 트래픽을 제거하여 정상적인 트래픽을 얻을 수 있었다. TDG 클러스터링 기법은 연산 속도가 빠르므로 실시간 이상 탐지에 적용될 수 있을 것으로 기대된다. Today’s Internet is one of the necessaries of our life. Anomalies of the Internet provoke social problems. For that reason, Internet Measurement which studies characteristics on Internet traffic attracts pubic attention. Recently, Traffic Dispersion Graph (TDG), a novel traffic analysis method, was proposed. The TDG is not a statistical analysis method but a graphical visualization method on interactions among network components. In this paper, we propose a new anomaly detection paradigm and its technique using TDG. The existing studies have focused on detecting anomalous packets of flows. On the other hand, we focus on detecting the sources of anomalous traffic. To realize our paradigm, we designed the TDG Clustering method. Through this method, we could classify anomalous hosts infected by various worm viruses. We obtained normal traffic through dropping traffic of the anomalous hosts. Especially, we expect that the TDG clustering method can be applied to real-time anomaly detection because calculations of the method are fast.

무선 네트워크에서의 효율적 트래픽 분류 기법 연구

이성진(Seongjin Lee),송종우(Jongwoo Song),안수한(Soohan Ahn),원유집(Youjip Won),장재성(Jae-sung Chang) 한국정보과학회 2008 한국정보과학회 학술발표논문집 Vol.35 No.1

무선 인터넷의 구조적 특성상 한 셀에서 대역폭을 공유하고 그 안에서 각기 다른 QoS를 요구하근 서비스들이 한정된 자원을 사용한다. 트래픽의 변화와 패턴을 예측하기 위한 분석은 실제 서비스를 제공하기 전인 기획단계에서 매우 중요한 도구로 사용이 된다. 무선망의 트래픽을 예측하기 위해서는 유선 망의 분석과는 다른 방법이 필요하기 때문에 정확한 분류를 위해서 본 연구에서는 세션의 단위로 분석할 것을 제안한다. 또한 Classification and Regression Tree(CART)와 Support Vector Machine(SVM)의 두 개의 판별 분류 기법을 서로 비교하고 그 성능을 평가한다. 두 개의 판별 기법의 오차는 CART의 경우 0.0094 그리고 SVM의 경우 0.0089로 둘 다 우수한 성능을 보였지만 쉬운 결과 해석이 가능한 CART가 사용하기 용이함을 보인다.