1 |
1
그래프 저장 관리 장치에 의해 구현되는 그래프 저장 관리 방법에 있어서,상기 그래프 저장 관리 장치에서, 연속되는 주기 간에 발생한 복수의 그래프 스트림을 추출하는 단계;상기 그래프 저장 관리 장치에서, 상기 복수의 그래프 스트림으로부터, 중점 사이를 연결하는 간선의 방향을 확인하여 중복 데이터를 식별하는 단계;상기 그래프 저장 관리 장치에서, 상기 중복 데이터를 중복 스냅샷에 저장하는 단계; 및상기 그래프 저장 관리 장치에서, 상기 연속되는 주기 중에서, n(상기 n은 자연수) 주기에 발생한 그래프 스트림으로부터, 상기 중복 데이터를 제외한 비중복 데이터를 식별하는 단계;상기 그래프 저장 관리 장치에서, 상기 비중복 데이터를, 상기 n에 대응하는 제n 델타 스냅샷에 저장하는 단계; 및상기 그래프 저장 관리 장치에서, 상기 제n 델타 스냅샷을, 상기 중복 스냅샷과 연결하여 데이터 저장 구조체를 구성하는 단계를 포함하는 변경 추적 및 이력 그래프 검색을 위한 그래프 저장 관리 방법
|
2 |
2
삭제
|
3 |
3
제1항에 있어서,상기 그래프 저장 관리 장치에서, 상기 복수의 그래프 스트림 각각에 대해 희소 행렬을 작성하는 단계; 및상기 그래프 저장 관리 장치에서, 상기 희소 행렬을, 제1 로우 포인터 배열(Row pointer array)과 제1 컬럼 인덱스 배열(column indices array)을 포함하는 CSR(Compressed Sparse Row)로 표현하는 단계를 더 포함하는 변경 추적 및 이력 그래프 검색을 위한 그래프 저장 관리 방법
|
4 |
4
제3항에 있어서,상기 CSR로 표현하는 단계는,상기 희소 행렬 내 그래프 데이터 각각으로 가상의 좌표 정보를 할당하는 단계;상기 그래프 데이터가 '1'로 존재하는 제1 좌표 정보를 독출하는 단계; 및상기 제1 좌표 정보 중 시작행 번호, 시작행에서의 상기 제1 좌표 정보를 독출한 횟수, 상기 시작행에서부터 u행까지(상기 u는 2번째행 번호에서 마지막행 번호)의 상기 제1 좌표 정보를 독출한 누적 횟수를 순차적으로 기재하여, 제1 로우 포인터 배열을 표현하는 단계를 포함하는 변경 추적 및 이력 그래프 검색을 위한 그래프 저장 관리 방법
|
5 |
5
제4항에 있어서,상기 CSR로 표현하는 단계는,상기 제1 좌표 정보에서, 열에 해당하는 값을 순차적으로 기재하여 제1 컬럼 인덱스 배열을 표현하는 단계를 더 포함하는 변경 추적 및 이력 그래프 검색을 위한 그래프 저장 관리 방법
|
6 |
6
제5항에 있어서,상기 CSR로 표현하는 단계는,상기 희소 행렬을 비교하여, 상기 제1 좌표 정보 중에서, 중복 데이터가 있는 제2 좌표 정보를 독출하는 단계;상기 제2 좌표 정보 중 시작행 번호, 시작행에서의 상기 제2 좌표 정보를 독출한 횟수, 상기 시작행에서부터 v행까지(상기 v는 2번째행 번호에서 마지막행 번호)의 상기 제2 좌표 정보를 독출한 누적 횟수를 순차적으로 기재하여 제2 로우 포인터 배열을 표현하는 단계;상기 제2 좌표 정보에서, 열에 해당하는 값을 순차적으로 기재하여 제2 컬럼 인덱스 배열을 표현하는 단계; 및상기 제2 로우 포인터 배열과 상기 제2 컬럼 인덱스 배열을 중복 스냅샷에 저장하는 단계를 더 포함하는 변경 추적 및 이력 그래프 검색을 위한 그래프 저장 관리 방법
|
7 |
7
제6항에 있어서,상기 CSR로 표현하는 단계는,상기 제1 컬럼 인덱스 배열 내, 상기 제2 좌표 정보와 연관되는 일부를 상기 중복 스냅샷을 지정하는 식별자로 대체하여, 델타 스냅샷에 저장하는 단계; 및상기 제1 로우 포인터 배열을 상기 델타 스냅샷에 더 저장하는 단계를 더 포함하는 변경 추적 및 이력 그래프 검색을 위한 그래프 저장 관리 방법
|
8 |
8
연속되는 주기 간에 발생한 복수의 그래프 스트림을 추출하는 추출부;상기 복수의 그래프 스트림으로부터, 중점 사이를 연결하는 간선의 방향을 확인하여 중복 데이터를 식별하고, 상기 연속되는 주기 중에서, n(상기 n은 자연수) 주기에 발생한 그래프 스트림으로부터, 상기 중복 데이터를 제외한 비중복 데이터를 식별하는 식별부;상기 중복 데이터를 중복 스냅샷에 저장하고, 상기 비중복 데이터를, 상기 n에 대응하는 제n 델타 스냅샷에 저장하는 처리부; 및상기 제n 델타 스냅샷을, 상기 중복 스냅샷과 연결하여 데이터 저장 구조체를 구성하는 구성부를 포함하는 변경 추적 및 이력 그래프 검색을 위한 그래프 저장 관리 장치
|
9 |
9
삭제
|
10 |
10
제8항에 있어서,상기 처리부는,상기 복수의 그래프 스트림 각각에 대해 희소 행렬을 작성하고,상기 희소 행렬을, 제1 로우 포인터 배열과 제1 컬럼 인덱스 배열을 포함하는 CSR로 표현하는그래프 저장 관리 장치
|
11 |
11
제10항에 있어서,상기 처리부는,상기 희소 행렬 내 그래프 데이터 각각으로 가상의 좌표 정보를 할당하고,상기 그래프 데이터가 '1'로 존재하는 제1 좌표 정보를 독출하며,상기 제1 좌표 정보 중 시작행 번호, 시작행에서의 상기 제1 좌표 정보를 독출한 횟수, 상기 시작행에서부터 u행까지(상기 u는 2번째행 번호에서 마지막행 번호)의 상기 제1 좌표 정보를 독출한 누적 횟수를 순차적으로 기재하여, 제1 로우 포인터 배열을 표현하는그래프 저장 관리 장치
|
12 |
12
제11항에 있어서,상기 처리부는,상기 제1 좌표 정보에서, 열에 해당하는 값을 순차적으로 기재하여 제1 컬럼 인덱스 배열을 표현하는그래프 저장 관리 장치
|
13 |
13
제12항에 있어서,상기 처리부는,상기 희소 행렬을 비교하여, 상기 제1 좌표 정보 중에서, 중복 데이터가 있는 제2 좌표 정보를 독출하고,상기 제2 좌표 정보 중 시작행 번호, 시작행에서의 상기 제2 좌표 정보를 독출한 횟수, 상기 시작행에서부터 v행까지(상기 v는 2번째행 번호에서 마지막행 번호)의 상기 제2 좌표 정보를 독출한 누적 횟수를 순차적으로 기재하여 제2 로우 포인터 배열을 표현하며,상기 제2 좌표 정보에서, 열에 해당하는 값을 순차적으로 기재하여 제2 컬럼 인덱스 배열을 표현하고,상기 제2 로우 포인터 배열과 상기 제2 컬럼 인덱스 배열을 중복 스냅샷에 저장하는그래프 저장 관리 장치
|
14 |
14
제13항에 있어서,상기 처리부는,상기 제1 컬럼 인덱스 배열 내, 상기 제2 좌표 정보와 연관되는 일부를 상기 중복 스냅샷을 지정하는 식별자로 대체하여, 델타 스냅샷에 저장하고,상기 제1 로우 포인터 배열을 상기 델타 스냅샷에 더 저장하는그래프 저장 관리 장치
|