1 |
1
프로세서에 의해 스캔 가능한 동적 해싱(hashing)을 수행하는 방법에 있어서,데이터 키 값들에 대해 산출된 키 값 분포 정보의 분포 형태를 판단하는 단계;상기 키 값 분포 정보의 상기 분포 형태를 판단한 결과에 기초하여, 상기 데이터 키 값들을 변환시키는 변환 함수를 결정하는 단계;상기 결정된 변환 함수를 이용하여 상기 데이터 키 값들을 균일(uniform)한 분포에 대응하는 값으로 변환하는 단계; 및상기 변환된 데이터 키 값들에 관련된 해쉬 인덱스 구조(hash index structure)를 생성하는 단계를 포함하고,상기 데이터 키 값들에 대해 산출된 키 값 분포 정보의 분포 형태를 판단하는 단계는,균일한 분포에 관련된 값과 상기 키 값 분포 정보 간의 거리를 계산한 결과에 기초하여, 상기 데이터 키 값들을 변환시킬지 여부를 판단하는 단계를 포함하는 스캔 가능한 동적 해싱 수행 방법
|
2 |
2
삭제
|
3 |
3
제1항에 있어서,상기 데이터 키 값들을 변환시킬지 여부를 판단하는 단계는,상기 거리로서 상기 균일한 분포의 분산 값과 상기 키 값 분포 정보의 분산 값의 차이를 계산하는 단계를 포함하는 스캔 가능한 동적 해싱 수행 방법
|
4 |
4
제1항에 있어서,상기 데이터 키 값들을 변환시킬지 여부를 판단하는 단계는,상기 계산된 거리를 미리 지정된 임계 거리에 비교하는 단계; 및상기 계산된 거리 및 상기 임계 거리를 비교한 결과에 기초하여, 상기 데이터 키 값들을 변환을 수행하는 단계를 더 포함하는 스캔 가능한 동적 해싱 수행 방법
|
5 |
5
제1항에 있어서,상기 데이터 키 값들의 군집 레벨(cluster level)에 기초하여, 상기 데이터 키 값들을 변환시킬지 여부를 판단하는 단계를 더 포함하는 스캔 가능한 동적 해싱 수행 방법
|
6 |
6
제5항에 있어서,상기 데이터 키 값들을 변환시킬지 여부를 판단하는 단계는,상기 데이터 키 값들 간의 공통 비트 개수를 상기 군집 레벨로서 결정하는 단계; 및상기 군집 레벨이 미리 지정된 임계 레벨 이상인 경우에 응답하여, 상기 데이터 키 값들을 변환을 수행하는 단계를 포함하는 스캔 가능한 동적 해싱 수행 방법
|
7 |
7
제1항에 있어서,상기 키 값 분포 정보는 상기 데이터 키 값들의 분산 및 평균을 포함하는스캔 가능한 동적 해싱 수행 방법
|
8 |
8
제1항에 있어서,상기 분포 형태를 판단하는 단계는,상기 분포 형태 및 복수의 연속확률분포들의 각 연속확률분포에 대응하는 형태에 매칭하는지 판단하는 단계; 및상기 분포 형태가 상기 복수의 연속확률분포들 중 한 연속확률분포에 대응하는 형태에 매칭하는 경우에 응답하여, 상기 분포 형태를 매칭된 연속확률분포로 결정하는 단계를 포함하는 스캔 가능한 동적 해싱 수행 방법
|
9 |
9
제8항에 있어서,상기 분포 형태를 판단하는 단계는,상기 분포 형태가 상기 복수의 연속확률분포들에 매칭되지 않는 경우에 응답하여, 상기 데이터 키 값들의 군집 레벨을 결정하는 단계; 및상기 결정된 군집 레벨이 미리 지정된 임계 레벨 미만인 경우에 응답하여, 상기 데이터 키 값의 변환을 스킵(skip)하는 단계를 포함하는 스캔 가능한 동적 해싱 수행 방법
|
10 |
10
제1항에 있어서,상기 변환 함수를 결정하는 단계는,상기 키 값 분포 정보의 분포 형태에 대한 누적 분포 함수(Cumulative distribution function, CDF)에 기초하여 상기 변환 함수를 결정하는 단계를 포함하는 스캔 가능한 동적 해싱 수행 방법
|
11 |
11
제10항에 있어서,상기 변환 함수를 결정하는 단계는,선형 보간법에 기초하여 상기 누적 분포 함수를 일련의 선형 함수들의 집합으로 변환하는 단계를 포함하는 스캔 가능한 동적 해싱 수행 방법
|
12 |
12
제11항에 있어서,상기 변환 함수를 결정하는 단계는,상기 데이터 키 값들을 데이터 키 값 개수에 따라 복수의 그룹으로 분할하고, 각 그룹에 대한 선형 함수를 계산하는 단계를 포함하는 스캔 가능한 동적 해싱 수행 방법
|
13 |
13
제1항에 있어서,상기 해쉬 인덱스 구조를 결정하는 단계는,상기 데이터 키 값에 관련된 디렉토리(directory) 및 상기 디렉토리에 대응하는 버킷(bucket)을 생성하고, 상기 변환 함수에 따라 변환된 데이터 키 값들을 상기 버킷에 매핑하는 단계를 포함하는 스캔 가능한 동적 해싱 수행 방법
|
14 |
14
제1항 및 제3항 내지 제13항 중 어느 한 항의 방법을 수행하기 위한 명령어들을 포함하는 하나 이상의 컴퓨터 프로그램을 저장한 컴퓨터 판독 가능 기록 매체
|
15 |
15
데이터 키 값들에 대해 산출된 키 값 분포 정보의 분포 형태를 판단하고, 키 값 분포 정보의 상기 분포 형태를 판단한 결과에 기초하여, 상기 데이터 키 값들을 변환시키는 변환 함수를 결정하며, 기 결정된 변환 함수를 이용하여 상기 데이터 키 값들을 균일(uniform)한 분포에 대응하는 값으로 변환하고, 상기 변환된 데이터 키 값들에 관련된 해쉬 인덱스 구조(hash index structure)를 생성하는 프로세서; 및상기 해쉬 인덱스 구조에 상기 변환된 데이터 키 값들을 저장하는 메모리;를 포함하고,상기 프로세서는,균일한 분포에 관련된 값과 상기 키 값 분포 정보 간의 거리를 계산한 결과에 기초하여, 상기 데이터 키 값들을 변환시킬지 여부를 판단하는,스캔 가능한 동적 해싱 수행 장치
|