| 1 |
1
컴퓨터를 이용한 데이터 검색 방법으로서, 상기 컴퓨터가,(a) 데이터베이스에 저장되는 항목에 대한 해시 인덱스들을 기초로 분할 블룸 필터의 비트 포지션들을 "1"로 설정하는 단계; (b) 상기 데이터베이스에 저장된 항목이 삭제될 경우에, 상기 삭제되는 항목에 대한 해시 인덱스들을 기초로 상기 분할 블룸 필터의 비트 포지션들을 "0"으로 설정하는 단계; (c) 질의 항목이 입력되면, 상기 분할 블룸 필터로부터, 상기 질의 항목에 대한 해시 인덱스들의 각각에 상응하는 비트 포지션들의 비트들로 구성되는 비트열을 생성하는 단계; (d) 상기 비트열이 모두 "1"을 포함할 경우에, 상기 데이터베이스 내에 상기 질의 항목과 동일한 항목이 존재한다고 판정하는 단계; 및(e) 상기 비트열이 적어도 하나의 "0"을 포함할 경우에, 상기 데이터베이스 내에 상기 질의 항목과 동일한 항목의 부존재를 상기 비트열 내의 "1"의 개수에 따라 판정하는 단계를 포함하는 분할 블룸 필터를 이용한 데이터 검색 방법
|
| 2 |
2
상기 (e) 단계는상기 컴퓨터가, 상기 비트열 내의 "1"의 개수가 소정의 문턱값(TH 003c# k)보다 작으면 상기 질의 항목과 동일한 항목이 부존재한다고 판정하고, 그렇지 않으면 상기 질의 항목과 동일한 항목이 존재한다고 판정하는 단계를 포함하고, 여기서 TH는 양의 실수인 문턱값, k는 해시 함수들의 개수인 것을 특징으로 하는 분할 블룸 필터를 이용한 데이터 검색 방법
|
| 3 |
3
청구항 2에 있어서, (f) 상기 컴퓨터가, 상기 질의 항목에 대한 동일한 항목의 부존재 판정 결과에 따른 거짓 양성 확률에 기초하여 상기 문턱값을 조절하는 단계를 더 포함하는 것을 특징으로 하는 분할 블룸 필터를 이용한 데이터 검색 방법
|
| 4 |
4
컴퓨터가 청구항 1 내지 3 중 어느 한 청구항에 따른 분할 블룸 필터를 이용한 데이터 검색 방법의 각 단계들을 구현하도록 작성되어 기록 매체에 기록된 컴퓨터 프로그램
|
| 5 |
5
분할 블룸 필터; 및 블룸 필터 관리부를 포함하는 데이터 검색 장치로서, 상기 블룸 필터 관리부는데이터베이스에 저장되는 항목에 대한 해시 인덱스들을 기초로 분할 블룸 필터의 비트 포지션들을 "1"로 설정하고, 상기 데이터베이스에 저장된 항목이 삭제될 경우에, 상기 삭제되는 항목에 대한 해시 인덱스들을 기초로 상기 분할 블룸 필터의 비트 포지션들을 "0"으로 설정하며, 질의 항목이 입력되면 상기 분할 블룸 필터로부터 상기 질의 항목에 대한 해시 인덱스들의 각각에 상응하는 비트 포지션들의 비트들로 구성되는 비트열을 생성하고, 상기 비트열이 모두 "1"을 포함할 경우에는 상기 데이터베이스 내에 상기 질의 항목과 동일한 항목이 존재한다고 판정하지만,상기 비트열이 적어도 하나의 "0"을 포함할 경우에는 상기 데이터베이스 내에 상기 질의 항목과 동일한 항목의 부존재를 상기 비트열 내의 "1"의 개수에 따라 판정하도록 동작하고,상기 분할 블룸 필터는 복수의 서브 블룸 필터들로 구성되는 블룸 필터이고, 캐싱되는 데이터 또는 질의 데이터에 관하여 복수의 해시 함수들에 의해 복수의 해시 인덱스들이 산출될 때에는, 각 서브 블룸 필터마다 "1"인 비트 포지션이 하나씩 설정되는 것을 특징으로 하는 블룸 필터를 이용한 데이터 검색 장치
|
| 6 |
6
청구항 5에 있어서, 상기 블룸 필터 관리부는 상기 비트열 내의 "1"의 개수가 소정의 문턱값(TH 003c# k)보다 작으면 상기 질의 항목과 동일한 항목이 부존재한다고 판정하고, 그렇지 않으면 상기 질의 항목과 동일한 항목이 존재한다고 판정하도록 동작하고, 여기서 TH는 양의 실수인 문턱값, k는 해시 함수들의 개수인 것을 특징으로 하는 분할 블룸 필터를 이용한 데이터 검색 장치
|
| 7 |
7
캐시 메모리 장치가, (i) 캐시 메모리에 캐싱되는 데이터의 데이터 식별자에 대한 해시 인덱스들을 기초로 분할 블룸 필터의 비트 포지션들을 "1"로 설정하는 단계; (ii) 상기 캐시 메모리에 캐싱된 데이터가 퇴출될 경우에, 퇴출되는 데이터의 데이터 식별자에 대한 해시 인덱스들을 기초로 상기 분할 블룸 필터의 비트 포지션들을 "0"으로 설정하는 단계; (iii) 액세스 데이터의 데이터 식별자가 입력되면, 상기 분할 블룸 필터로부터, 상기 액세스 데이터의 데이터 식별자에 대한 해시 인덱스들의 각각에 상응하는 비트 포지션들의 비트들로 구성되는 비트열을 생성하는 단계; (iv) 상기 비트열이 모두 "1"을 포함할 경우에, 상기 캐시 메모리 내에 상기 액세스 데이터와 동일한 캐싱된 데이터가 존재한다고 판정하는 단계; (v) 상기 비트열이 적어도 하나의 "0"을 포함할 경우에, 상기 캐시 메모리 내에 상기 액세스 데이터와 동일한 캐싱된 데이터의 부존재를 상기 비트열 내의 "1"의 개수에 따라 판정하는 단계;(vi) 상기 (iv) 단계 또는 상기 (v) 단계에서 상기 캐시 메모리 내에 상기 액세스 데이터와 동일한 캐싱된 데이터의 존재가 판정되면, 상기 액세스 데이터의 데이터 식별자에 따라 상기 캐시 메모리에서 액세스하는 단계; 및(vii) 상기 (v) 단계에서 상기 캐시 메모리 내에 상기 액세스 데이터와 동일한 캐싱된 데이터의 부존재가 판정되면, 캐시 미스(cache miss)를 출력하는 단계를 포함하고,상기 분할 블룸 필터는 복수의 서브 블룸 필터들로 구성되는 블룸 필터이고, 캐싱되는 데이터 또는 액세스 데이터에 관하여 복수의 해시 함수들에 의해 복수의 해시 인덱스들이 산출될 때에는, 각 서브 블룸 필터마다 "1"인 비트 포지션이 하나씩 설정되는 분할 블룸 필터를 이용한 캐시 메모리 관리 방법
|
| 8 |
8
청구항 7에 있어서, 상기 (v) 단계는상기 캐시 메모리 장치가, 상기 비트열 내의 "1"의 개수가 소정의 문턱값(TH 003c# k)보다 작으면 상기 액세스 데이터와 동일한 캐싱된 데이터가 부존재한다고 판정하고, 그렇지 않으면 상기 액세스 데이터와 동일한 캐싱된 데이터가 존재한다고 판정하는 단계를 포함하고, 여기서 TH는 양의 실수인 문턱값, k는 해시 함수들의 개수인 것을 특징으로 하는 분할 블룸 필터를 이용한 캐시 메모리 관리 방법
|
| 9 |
9
청구항 8에 있어서, (viii) 상기 캐시 메모리 장치가, 상기 액세스 데이터에 대한 동일한 데이터의 부존재 판정 결과에 따른 거짓 양성 확률에 기초하여 상기 문턱값을 조절하는 단계를 더 포함하는 것을 특징으로 하는 분할 블룸 필터를 이용한 캐시 메모리 관리 방법
|
| 10 |
10
청구항 7에 있어서, (ix) 상기 (vi) 단계에서 상기 액세스 데이터의 데이터 식별자에 따라 상기 캐시 메모리에서 액세스하였는데 실제로는 상기 액세스 데이터가 상기 캐시 메모리에 부존재했던 것으로 밝혀질 경우에는, 상기 캐시 메모리의 캐싱 대상인 외부의 스토리지 매체에서 상기 액세스 데이터를 상기 캐시 메모리에 캐싱하는 단계; 및(x) 상기 (vii) 단계에서 캐시 미스가 발생함에 따라, 상기 캐시 메모리의 캐싱 대상인 외부의 스토리지 매체에서 상기 액세스 데이터를 상기 캐시 메모리에 캐싱하는 단계를 더 포함하는 것을 특징으로 하는 분할 블룸 필터를 이용한 캐시 메모리 관리 방법
|
| 11 |
11
컴퓨터가 청구항 7 내지 10 중 어느 한 청구항에 따른 분할 블룸 필터를 이용한 캐시 메모리 관리 방법의 각 단계들을 구현하도록 작성되어 기록 매체에 기록된 컴퓨터 프로그램
|
| 12 |
12
캐시 메모리; 및 외부의 스토리지 매체에서 액세스되는 데이터를 상기 캐시 메모리에 캐싱하거나 또는 퇴출함으로써 상기 캐시 메모리를 관리하는 캐시 메모리 관리부를 포함하는 캐시 메모리 장치로서,상기 캐시 메모리 관리부는상기 캐시 메모리에 캐싱되는 데이터의 데이터 식별자에 대한 해시 인덱스들을 기초로 분할 블룸 필터의 비트 포지션들을 "1"로 설정하며,상기 캐시 메모리에 캐싱된 데이터가 퇴출될 경우에, 퇴출되는 데이터의 데이터 식별자에 대한 해시 인덱스들을 기초로 상기 분할 블룸 필터의 비트 포지션들을 "0"으로 설정하고,상기 캐시 메모리에 액세스 데이터의 데이터 식별자가 입력되면, 상기 분할 블룸 필터로부터, 상기 액세스 데이터의 데이터 식별자에 대한 해시 인덱스들의 각각에 상응하는 비트 포지션들의 비트들로 구성되는 비트열을 생성하며,상기 비트열이 모두 "1"을 포함할 경우에는, 상기 캐시 메모리 내에 상기 액세스 데이터와 동일한 캐싱된 데이터가 존재한다고 판정하고 상기 액세스 데이터의 데이터 식별자에 따라 상기 캐시 메모리에서 액세스하며,상기 비트열이 적어도 하나의 "0"을 포함할 경우에는, 상기 캐시 메모리 내에 상기 액세스 데이터와 동일한 캐싱된 데이터의 부존재를 상기 비트열 내의 "1"의 개수에 따라 판정하고 캐시 미스를 출력하도록 동작하고,상기 분할 블룸 필터는 복수의 서브 블룸 필터들로 구성되는 블룸 필터이고, 캐싱되는 데이터 또는 액세스 데이터에 관하여 복수의 해시 함수들에 의해 복수의 해시 인덱스들이 산출될 때에는, 각 서브 블룸 필터마다 "1"인 비트 포지션이 하나씩 설정되는 것을 특징으로 하는 분할 블룸 필터를 이용한 캐시 메모리 장치
|
| 13 |
13
청구항 12에 있어서, 상기 캐시 메모리 관리부는 상기 비트열 내의 "1"의 개수가 소정의 문턱값(TH 003c# k)보다 작으면 상기 액세스 데이터와 동일한 캐싱된 데이터가 부존재한다고 판정하고, 그렇지 않으면 상기 액세스 데이터와 동일한 캐싱된 데이터가 존재한다고 판정하도록 동작하고, 여기서 TH는 양의 실수인 문턱값, k는 해시 함수들의 개수인 것을 특징으로 하는 분할 블룸 필터를 이용한 캐시 메모리 장치
|
| 14 |
14
청구항 12에 있어서, 상기 캐시 메모리 관리부는, 상기 액세스 데이터의 데이터 식별자에 따라 상기 캐시 메모리에서 액세스하였는데 실제로는 상기 액세스 데이터가 상기 캐시 메모리에 부존재했던 것으로 밝혀질 경우 또는 캐시 미스가 발생할 경우에는, 상기 캐시 메모리의 캐싱 대상인 외부의 스토리지 매체에서 상기 액세스 데이터를 상기 캐시 메모리에 캐싱하도록 동작하는 것을 특징으로 하는 분할 블룸 필터를 이용한 캐시 메모리 장치
|
| 15 |
15
스토리지 매체;호스트의 액세스 요청에 따라 상기 스토리지 매체에 액세스하는 스토리지 액세스 제어부;캐시 메모리; 및상기 스토리지 매체에서 액세스되는 데이터를 상기 캐시 메모리에 캐싱하거나 또는 퇴출함으로써 상기 캐시 메모리를 관리하는 캐시 메모리 관리부를 포함하는 스토리지 장치로서,상기 캐시 메모리 관리부는상기 캐시 메모리에 캐싱되는 데이터의 데이터 식별자에 대한 해시 인덱스들을 기초로 분할 블룸 필터의 비트 포지션들을 "1"로 설정하며,상기 캐시 메모리에 캐싱된 데이터가 퇴출될 경우에, 퇴출되는 데이터의 데이터 식별자에 대한 해시 인덱스들을 기초로 상기 분할 블룸 필터의 비트 포지션들을 "0"으로 설정하고,상기 캐시 메모리에 액세스 데이터의 데이터 식별자가 입력되면, 상기 분할 블룸 필터로부터, 상기 액세스 데이터의 데이터 식별자에 대한 해시 인덱스들의 각각에 상응하는 비트 포지션들의 비트들로 구성되는 비트열을 생성하며,상기 비트열이 모두 "1"을 포함할 경우에는, 상기 캐시 메모리 내에 상기 액세스 데이터와 동일한 캐싱된 데이터가 존재한다고 판정하고 상기 액세스 데이터의 데이터 식별자에 따라 상기 캐시 메모리에서 액세스하며,상기 비트열이 적어도 하나의 "0"을 포함할 경우에는, 상기 캐시 메모리 내에 상기 액세스 데이터와 동일한 캐싱된 데이터의 부존재를 상기 비트열 내의 "1"의 개수에 따라 판정하고 캐시 미스를 출력하도록 동작하고,상기 분할 블룸 필터는 복수의 서브 블룸 필터들로 구성되는 블룸 필터이고, 캐싱되는 데이터 또는 액세스 데이터에 관하여 복수의 해시 함수들에 의해 복수의 해시 인덱스들이 산출될 때에는, 각 서브 블룸 필터마다 "1"인 비트 포지션이 하나씩 설정되는 것을 특징으로 하는 분할 블룸 필터를 이용한 스토리지 장치
|
