1 |
1
질의 요청이 수신 됨에 따라,상기 질의와 연관된 그래프 데이터를, 이전 질의 요청에 따라 기 출력된 데이터가 저장되는 제1 캐시 메모리에서 탐색하는 단계;상기 제1 캐시 메모리에서 탐색되지 않으면,상기 제1 캐시 메모리에 저장된 각 데이터에 대해 접근한 이력이 있는 인접 데이터가 저장된 제2 캐시 메모리에서, 상기 그래프 데이터를 재탐색하는 단계; 및상기 재탐색에 따라 상기 제2 캐시 메모리에서 확인되는 제1 인접 데이터를, 상기 그래프 데이터로서 상기 질의 요청에 대한 응답으로 출력하는 단계를 포함하고,상기 그래프 데이터는, 상기 질의 요청된 서브 그래프를 구성하는 복수의 정점(vertex) 및 상기 복수의 정점 사이를 연결하는 간선(edge)을 포함하고,상기 출력하는 단계는,상기 제1 캐시 메모리에서 상기 복수의 정점 중 일부의 정점이 탐색되는 경우, 상기 제1 캐시 메모리에서 탐색된 일부의 정점과, 상기 제2 캐시 메모리에서 재탐색된 나머지 정점을 상기 그래프 데이터로서 조합하여 출력하는 단계를 포함하는 그래프 처리 성능 향상을 위한 복수 계층 캐싱 방법
|
2 |
2
제1항에 있어서,상기 복수 계층 캐싱 방법은,상기 제2 캐시 메모리에서 확인되는 제1 인접 데이터를, 상기 제1 캐시 메모리로 이동시켜 저장하는 단계; 및제1 캐시 메모리에 저장된 제1 인접 데이터에 대해 접근한 이력이 있는 데이터를, 디스크 메모리로부터 선별하여 신규의 인접 데이터로서 상기 제2 캐시 메모리에 추가하여 저장하는 단계를 더 포함하는 복수 계층 캐싱 방법
|
3 |
3
제2항에 있어서,상기 제1 캐시 메모리에 저장 가능한 공간이 없는 경우,상기 제1 캐시 메모리로 이동시켜 저장하는 단계는,상기 제2 캐시 메모리에서 확인되는 데이터에 설정되는 만료시간값(TTL 값)을, 상기 제1 캐시 메모리 내 데이터에 설정된 각 만료시간값 중 최소값과 비교하는 단계; 및상기 만료시간값이 상기 최소값 보다 큰 경우, 상기 제1 캐시 메모리에서 상기 최소값을 만료시간값으로 가지는 데이터를, 상기 제2 캐시 메모리의 데이터로 교체하는 단계; 또는상기 만료시간값이 상기 최소값 보다 작은 경우, 상기 제2 캐시 메모리에서 확인되는 데이터를, 상기 제1 캐시 메모리로 이동시키지 않고 상기 제2 캐시 메모리에 유지하는 단계를 포함하는 복수 계층 캐싱 방법
|
4 |
4
제2항에 있어서,상기 추가하여 저장하는 단계는,상기 제1 인접 데이터로부터, 일정 홉 수 이내로 접근한 이력이 있는 데이터 중에서, 접근 횟수에 따라 상기 신규의 인접 데이터를 선별하는 단계를 포함하는 복수 계층 캐싱 방법
|
5 |
5
제4항에 있어서,상기 제2 캐시 메모리에 저장 가능한 공간이 없는 경우,상기 추가하여 저장하는 단계는,상기 제2 캐시 메모리에 기 저장된 인접 데이터를 저장시점이 오래된 순서대로 삭제하여, 상기 신규의 인접 데이터를 추가하는 단계를 포함하는 복수 계층 캐싱 방법
|
6 |
6
삭제
|
7 |
7
제1항에 있어서,상기 복수 계층 캐싱 방법은,질의 이력 테이블에 기록된 이전 질의 각각에 대해, 서브 그래프를 구성하는 정점의 리스트를 식별하는 단계;상기 이전 질의 각각에 대한 정점의 리스트를 참조하여 사용 빈도수가 높은 제1 정점으로 이루어진 질의 패턴을, 상기 서브 그래프로부터 추출하는 단계; 및상기 질의 패턴 내 제1 정점의 개수와, 상기 제1 정점에 부여된 패턴 가중치를 고려하여, 상기 제1 정점에 대한 만료시간값을 설정하는 단계를 더 포함하는 복수 계층 캐싱 방법
|
8 |
8
제7항에 있어서,상기 추출하는 단계는,상기 정점의 리스트를 사용 빈도수에 따라 내림차순으로 정렬하는 단계;상기 정렬된 순서대로 상기 정점의 리스트 내 각 정점을 호출하고, 상기 각 정점 사이의 접근 횟수를 의미하는 간선을 고려하여 FP-트리(Frequent Pattern Tree)를 생성하는 단계; 및상기 FP-트리를 이용하여 질의 패턴을 추출하는 단계를 포함하는 복수 계층 캐싱 방법
|
9 |
9
제7항에 있어서,상기 질의 요청의 수신에 따라 상기 질의를 상기 질의 이력 테이블에 추가로 기록하는 단계; 및상기 추가된 질의를 이용하여 추출한 질의 패턴을 이루는 제2 정점에 대한 패턴 가중치를 더 고려하여, 상기 제1 정점에 대한 만료시간값을 업데이트 하는 단계를 더 포함하는 복수 계층 캐싱 방법
|
10 |
10
질의 요청이 수신 됨에 따라,상기 질의와 연관된 그래프 데이터를, 이전 질의 요청에 따라 기 출력된 데이터가 저장되는 제1 캐시 메모리에서 탐색하고, 상기 제1 캐시 메모리에서 탐색되지 않으면, 상기 제1 캐시 메모리에 저장된 각 데이터에 대해 접근한 이력이 있는 인접 데이터가 저장된 제2 캐시 메모리에서, 상기 그래프 데이터를 재탐색하는 탐색부; 및상기 재탐색에 따라 상기 제2 캐시 메모리에서 확인되는 제1 인접 데이터를, 상기 그래프 데이터로서 상기 질의 요청에 대한 응답으로 출력하는 출력부를 포함하고,상기 그래프 데이터는, 상기 질의 요청된 서브 그래프를 구성하는 복수의 정점 및 상기 복수의 정점 사이를 연결하는 간선을 포함하고,상기 출력부는,상기 제1 캐시 메모리에서 상기 복수의 정점 중 일부의 정점이 탐색되는 경우, 상기 제1 캐시 메모리에서 탐색된 일부의 정점과, 상기 제2 캐시 메모리에서 재탐색된 나머지 정점을 상기 그래프 데이터로서 조합하여 출력하는그래프 처리 성능 향상을 위한 복수 계층 캐싱 시스템
|
11 |
11
제10항에 있어서,상기 복수 계층 캐싱 시스템은,상기 제2 캐시 메모리에서 확인되는 제1 인접 데이터를, 상기 제1 캐시 메모리로 이동시켜 저장하고, 제1 캐시 메모리에 저장된 제1 인접 데이터에 대해 접근한 이력이 있는 데이터를, 디스크 메모리로부터 선별하여 신규의 인접 데이터로서 상기 제2 캐시 메모리에 추가하여 저장하는 메모리 관리부를 더 포함하는 복수 계층 캐싱 시스템
|
12 |
12
제10항에 있어서,상기 복수 계층 캐싱 시스템은,질의 이력 테이블에 기록된 이전 질의 각각에 대해, 서브 그래프를 구성하는 정점의 리스트를 식별하고, 상기 이전 질의 각각에 대한 정점의 리스트를 참조하여 사용 빈도수가 높은 제1 정점으로 이루어진 질의 패턴을, 상기 서브 그래프로부터 추출하는 패턴 추출부; 및상기 질의 패턴 내 제1 정점의 개수와, 상기 제1 정점에 부여된 패턴 가중치를 고려하여, 상기 제1 정점에 대한 만료시간값을 설정하는 메모리 관리부를 더 포함하는 복수 계층 캐싱 시스템
|
13 |
13
제12항에 있어서,상기 메모리 관리부는,상기 질의 요청의 수신에 따라 상기 질의를 상기 질의 이력 테이블에 추가로 기록하고, 상기 추가된 질의를 이용하여 추출한 질의 패턴을 이루는 제2 정점에 대한 패턴 가중치를 더 고려하여, 상기 제1 정점에 대한 만료시간값을 업데이트 하는복수 계층 캐싱 시스템
|