그래프스트림 압축 시스템에 의해 구현되는 그래프스트림 압축 방법에 있어서,상기 그래프스트림 압축 시스템의 추출부에서, 실시간으로 입력되는 그래프스트림에 대한 압축 명령에 따라, 상기 그래프스트림 중 제1 시간 동안 입력된 서브스트림으로부터, 제1 서브그래프를 추출하는 단계;상기 그래프스트림 압축 시스템의 저장부에서, 상기 제1 서브그래프를, 초기 빈발패턴으로서, 패턴 사전에 저장하는 단계;상기 그래프스트림 압축 시스템의 업데이트부에서, 상기 그래프스트림 중, 상기 제1 시간의 경과시점부터 제2 시간 동안 입력된 서브스트림으로부터, 상기 제1 서브그래프와 상이한 제2 서브그래프가 추출되면, 상기 제2 서브그래프를 이용하여, 상기 패턴 사전 내에서 상기 제1 서브그래프를 확장 서브그래프로 업데이트하여 유지하는 단계; 및상기 그래프스트림 압축 시스템의 처리부에서, 상기 제1 및 제2 시간을 합산한 시간이, 정해진 시간에 도달하면, 상기 패턴 사전 내에 유지되는 상기 확장 서브그래프를, 기준 빈발패턴으로서, 압축 처리하는 단계를 포함하는 점진적 빈발패턴 기반의 그래프스트림 압축 방법.

제1항에 있어서,상기 추출부에서, 상기 제1 및 제2 시간을 합산한 시간이, 정해진 시간에 도달하지 않은 경우, 상기 그래프스트림 중, 상기 제2 시간의 경과시점부터 제3 시간 동안 입력된 서브스트림으로부터, 상기 제1 및 제2 서브그래프와 상이한 제3 서브그래프를 추출하는 단계; 및상기 업데이트부에서, 상기 제3 서브그래프를 이용하여, 상기 확장 서브그래프를 추가확장 서브그래프로 업데이트하는 단계를 더 포함하는 점진적 빈발패턴 기반의 그래프스트림 압축 방법.

제2항에 있어서,상기 처리부에서, 상기 초기 빈발패턴으로서 복수의 제1 서브그래프가 상기 패턴 사전에 저장된 경우, 상기 복수의 제1 서브그래프 중, 상기 확장 서브그래프 또는 상기 추가확장 서브그래프로의 업데이트에 관여하지 않은 제1 서브그래프를, 상기 패턴 사전으로부터 삭제 처리하는 단계를 더 포함하는 점진적 빈발패턴 기반의 그래프스트림 압축 방법.

제1항에 있어서,상기 그래프스트림 압축 시스템의 판별부에서, 상기 제2 서브그래프의 추출에 따라, VF2 알고리즘을 이용하여, 상기 제1 서브그래프와 상기 제2 서브그래프 간 유사도를 판별하는 단계;상기 판별부에서, 상기 유사도에 따라, 상기 제1 서브그래프가, 상기 제2 서브그래프의 적어도 일부와 일치하는 동형 그래프인지 결정하는 단계; 및상기 업데이트부에서, 상기 제1 서브그래프가 상기 제2 서브그래프의 동형 그래프로 결정되면, 상기 제2 서브그래프에 의해 상기 제1 서브그래프의 업데이트를 수행하는 단계를 더 포함하는 점진적 빈발패턴 기반의 그래프스트림 압축 방법.

제1항에 있어서,상기 패턴 사전에 저장하는 단계는,상기 제1 서브그래프를 구성하는 복수의 정점 및 상기 복수의 정점을 연결하는 간선을 상기 패턴 사전에 저장하는 단계를 포함하고,상기 업데이트하여 유지하는 단계는,상기 제2 서브그래프를 구성하는 복수의 정점을, 상기 패턴 사전에 저장된 기존정점과, 상기 패턴 사전에 저장되지 않는 신규정점으로 구분하는 단계;상기 제2 서브그래프로부터, 상기 기존정점과 상기 신규정점 사이를 연결하는 제1 간선을 탐색하는 단계;상기 제2 서브그래프로부터, 상기 제1 간선에 연결되면서, 상기 신규정점 사이를 연결하는 제2 간선을 탐색하는 단계; 및상기 제1 서브그래프에 상기 제1 간선 및 상기 제2 간선을 추가 연결하여, 상기 확장 서브그래프로의 업데이트를 수행하는 단계를 포함하는 점진적 빈발패턴 기반의 그래프스트림 압축 방법.

제1항에 있어서,상기 그래프스트림 압축 시스템의 산출부에서, 상기 확장 서브그래프가 복수이면, 상기 복수의 확장 서브그래프 각각에 대해, 빈발도 및 간선 크기를 고려하여, 패턴 점수를 산출하는 단계;상기 처리부에서, 상기 패턴 점수 순에 따른 상위 k(상기 k는 자연수)개의 확장 서브그래프를 선별하는 단계; 및상기 처리부에서, 상기 k개의 확장 서브그래프를, 상기 기준 빈발패턴으로서 지정하는 단계를 더 포함하는 점진적 빈발패턴 기반의 그래프스트림 압축 방법.

제6항에 있어서,상기 처리부에서, 상기 복수의 확장 서브그래프 중, 선별되지 않는 확장 서브그래프를 상기 패턴 사전으로부터 삭제 처리하는 단계를 더 포함하는 점진적 빈발패턴 기반의 그래프스트림 압축 방법.

제1항에 있어서,상기 저장부에서, 상기 기준 빈발패턴으로 지정된 확장 서브그래프를 기준으로, 시간 경과에 따라 변경되어 입력되는 상기 그래프스트림에 대한 변경사항을 기록한 프로버넌스 정보를, 상기 패턴 사전에 저장하는 단계를 더 포함하고,상기 압축 처리하는 단계는,상기 기준 빈발패턴 및 상기 프로버넌스 정보를 저장한 상기 패턴 사전에, 사전 인코딩(dictionary encoding) 기법을 적용하여, 압축 처리하는 단계를 포함하는 점진적 빈발패턴 기반의 그래프스트림 압축 방법.

제8항에 있어서,상기 프로버넌스 정보는,상기 기준 빈발패턴으로 지정된 확장 서브그래프에 대해, 설정된 빈발도 및 간선 크기에 따라 산출되는 패턴 점수와, 상기 그래프스트림 중 상기 제1 및 제2 서브그래프가 추출된 각 서브스트림이 입력되는 시간인 상기 제1 및 제2 시간을 기록한 타임스탬프와, 상기 각 서브스트림을 구성하는 배치(Batch)의 개수, 및 상기 확장 서브그래프의 식별을 위한 패턴ID 중 적어도 하나를 포함하는점진적 빈발패턴 기반의 그래프스트림 압축 방법.

실시간으로 입력되는 그래프스트림에 대한 압축 명령에 따라,상기 그래프스트림 중 제1 시간 동안 입력된 서브스트림으로부터, 제1 서브그래프를 추출하는 추출부;상기 제1 서브그래프를, 초기 빈발패턴으로서, 패턴 사전에 저장하는 저장부;상기 추출부에 의해, 상기 그래프스트림 중, 상기 제1 시간의 경과시점부터 제2 시간 동안 입력된 서브스트림으로부터, 상기 제1 서브그래프와 상이한 제2 서브그래프가 추출되면,상기 제2 서브그래프를 이용하여, 상기 패턴 사전 내에서 상기 제1 서브그래프를 확장 서브그래프로 업데이트하여 유지하는 업데이트부; 및상기 제1 및 제2 시간을 합산한 시간이, 정해진 시간에 도달하면,상기 패턴 사전 내에 유지되는 상기 확장 서브그래프를, 기준 빈발패턴으로서, 압축 처리하는 처리부를 포함하는 점진적 빈발패턴 기반의 그래프스트림 압축 시스템.

제10항에 있어서,상기 제1 및 제2 시간을 합산한 시간이, 정해진 시간에 도달하지 않은 경우,상기 추출부는,상기 그래프스트림 중, 상기 제2 시간의 경과시점부터 제3 시간 동안 입력된 서브스트림으로부터, 상기 제1 및 제2 서브그래프와 상이한 제3 서브그래프를 추출하고,상기 업데이트부는,상기 제3 서브그래프를 이용하여, 상기 확장 서브그래프를 추가확장 서브그래프로 업데이트하는점진적 빈발패턴 기반의 그래프스트림 압축 시스템.

제10항에 있어서,상기 제2 서브그래프의 추출에 따라, VF2 알고리즘을 이용하여, 상기 제1 서브그래프와 상기 제2 서브그래프 간 유사도를 판별하고, 상기 유사도에 따라, 상기 제1 서브그래프가, 상기 제2 서브그래프의 적어도 일부와 일치하는 동형 그래프인지 결정하는 판별부를 더 포함하고,상기 업데이트부는,상기 제1 서브그래프가 상기 제2 서브그래프의 동형 그래프로 결정되면,상기 제2 서브그래프에 의해 상기 제1 서브그래프의 업데이트를 수행하는점진적 빈발패턴 기반의 그래프스트림 압축 시스템.

제10항에 있어서,상기 확장 서브그래프가 복수이면,상기 복수의 확장 서브그래프 각각에 대해, 빈발도 및 간선 크기를 고려하여, 패턴 점수를 산출하는 산출부를 더 포함하고,상기 처리부는,상기 패턴 점수 순에 따른 상위 k(상기 k는 자연수)개의 확장 서브그래프를 선별하고, 상기 k개의 확장 서브그래프를, 상기 기준 빈발패턴으로서 지정하는점진적 빈발패턴 기반의 그래프스트림 압축 시스템.

제10항에 있어서,상기 저장부는,상기 기준 빈발패턴으로 지정된 확장 서브그래프를 기준으로, 시간 경과에 따라 변경되어 입력되는 상기 그래프스트림에 대한 변경사항을 기록한 프로버넌스 정보를, 상기 패턴 사전에 저장하고,상기 처리부는,상기 기준 빈발패턴 및 상기 프로버넌스 정보를 저장한 상기 패턴 사전에, 사전 인코딩(dictionary encoding) 기법을 적용하여, 압축 처리하는점진적 빈발패턴 기반의 그래프스트림 압축 시스템.

제1항 내지 제9항 중 어느 한 항의 방법을 실행시키기 위한 프로그램을 기록한 컴퓨터 판독 가능한 기록매체.