| 1 |
1
멀티셋(multiset)의 개별 원소의 개수를 카운팅하기 위해 컴퓨터로 구현되는 카운팅 방법에 있어서,각각 제1 비트크기를 갖는 복수의 변수들을 포함하는 카운팅 메모리를 유지하는 단계; 및입력되는 원소의 중복을 포함한 입력개수를 상기 카운팅 메모리의 대응 변수를 이용하여 카운팅하되, 상기 입력개수가 상기 제1 비트크기에 따라 카운팅 가능한 최대값을 초과하는 원소에 대해서는 동적으로 할당되는 추가 메모리를 더 이용하여 상기 입력개수를 카운팅하는 단계를 포함하는 카운팅 방법
|
| 2 |
2
제1항에 있어서,상기 대응 변수는, 상기 입력되는 원소를 변수로 갖는 해쉬함수를 이용하여 결정되는 것을 특징으로 하는 카운팅 방법
|
| 3 |
3
제1항 또는 제2항에 있어서,상기 추가 메모리는, 상기 초과하는 원소의 식별자와 추가변수가 서로 대응되도록 함께 저장되는 확장테이블을 포함하고,상기 추가변수는 상기 식별자에 대응하는 원소의 추가 카운팅을 위한 제2 비트크기를 갖는 것을 특징으로 하는 카운팅 방법
|
| 4 |
4
제3항에 있어서,상기 입력개수를 카운팅하는 단계는,상기 입력되는 원소에 대응하는 상기 카운팅 메모리의 변수의 값이 상기 최대값을 초과하는 경우, 상기 추가변수에 상기 최대값을 누적하고, 상기 카운팅 메모리의 변수의 값을 1로 설정하는 것을 특징으로 하는 카운팅 방법
|
| 5 |
5
제3항에 있어서,상기 입력개수를 카운팅하는 단계는,상기 입력되는 원소에 대응하는 상기 카운팅 메모리의 변수의 값이 상기 최대값을 초과하는 경우, 상기 추가변수에 상기 최대값과 노이즈값의 차를 누적하고, 상기 카운팅 메모리의 변수의 값을 상기 노이즈값으로 설정하고,상기 노이즈값은, 상기 멀티셋에 포함된 모든 원소의 개수의 상기 카운팅 메모리의 변수의 개수에 대한 비율을 포함하는 것을 특징으로 하는 카운팅 방법
|
| 6 |
6
삭제
|
| 7 |
7
제3항에 있어서,상기 원소의 식별자는, 상기 원소 또는 상기 원소를 인자로 갖는 체크섬 함수(checksum function)의 결과값을 포함하는 것을 특징으로 하는 카운팅 방법
|
| 8 |
8
제3항에 있어서,요청된 원소를 상기 확장테이블에서 검색하는 단계; 및상기 요청된 원소가 상기 확장테이블에 존재하는 경우, 상기 카운팅 메모리의 변수에 카운팅된 원소의 개수 및 상기 추가변수에 카운팅된 원소의 개수의 합을 상기 요청된 원소의 개수로 산출하는 단계를 더 포함하는 카운팅 방법
|
| 9 |
9
제3항에 있어서,요청된 원소를 상기 확장테이블에서 검색하는 단계; 및상기 요청된 원소가 상기 확장테이블에 존재하는 경우, 상기 카운팅 메모리의 변수에 카운팅된 원소의 개수와 상기 추가변수에 카운팅된 원소의 개수의 합에서 노이즈값을 뺀 값을 상기 요청된 원소의 개수로 산출하는 단계를 더 포함하고,상기 노이즈값은, 상기 멀티셋에 포함된 모든 원소의 개수의 상기 카운팅 메모리의 변수의 개수에 대한 비율을 포함하는 카운팅 방법
|
| 10 |
10
멀티셋(multiset)의 개별 원소의 개수를 카운팅하는 카운팅 시스템에 있어서,적어도 하나의 스토리지 유닛; 및적어도 하나의 프로세서를 포함하고,상기 적어도 하나의 프로세서는,각각 제1 비트크기를 갖는 복수의 변수들을 포함하는 카운팅 메모리를 상기 적어도 하나의 스토리지 유닛에 유지하는 과정; 및입력되는 원소의 중복을 포함한 입력개수를 상기 카운팅 메모리의 대응 변수를 이용하여 카운팅하되, 상기 입력개수가 상기 제1 비트크기에 따라 카운팅 가능한 최대값을 초과하는 원소에 대해서는 상기 적어도 하나의 스토리지 유닛에 동적으로 할당되는 추가 메모리를 더 이용하여 상기 입력개수를 카운팅하는 과정을 처리하는 것을 특징으로 하는 카운팅 시스템
|
