| 1 |
1
적어도 프로세서를 포함하는 컴퓨팅 장치에서 수행되는, 배열 데이터에서의 상위 k(k는 자연수) 질의 처리 방법에 있어서,복수의 셀(cell)들로 구성된 배열(array)을 복수의 파티션들(partitions)로 분할하는 단계; 및상기 배열 내에서 응답을 검색하는 단계를 포함하는 상위 k 질의 처리 방법
|
| 2 |
2
제1항에 있어서,상기 복수의 파티션들로 분할하는 단계는,각 파티션에 대하여, 파티션 내에 포함된 셀들의 속성(attribute) 값들 중 최대 값, 속성 값을 갖는 셀의 개수, 파티션의 시작 셀(starting cell)의 위치, 및 파티션의 마지막 셀(ending cell)의 위치를 포함하는 파티션 정보를 저장하는 단계; 및상기 복수의 파티션들을 최대 값의 내림차순으로 정렬하는 단계를 포함하는,상위 k 질의 처리 방법
|
| 3 |
3
제2항에 있어서,상기 응답을 검색하는 단계는,상기 복수의 파티션들 중 가장 큰 최대 값을 갖는 제1 파티션을 선택하는 단계;상기 제1 파티션에 포함된 셀들 중 적어도 하나를 포함하는 서브배열(subarray)들 각각의 스코어(score)를 계산하는 단계;스코어가 계산된 서브배열의 스코어와 미리 계산된 스코어들 중 가장 높은 스코어를 갖는 서브배열의 스코어를 비교하는 단계; 및상기 스코어가 계산된 서브배열의 스코어가 상기 가장 높은 스코어를 갖는 서브배열의 스코어보다 큰 경우, 상기 스코어가 계산된 서브배열이 상기 상위 k 질의에 대한 응답으로 미리 결정된 적어도 하나의 서브배열과 중첩되는지 여부를 판단하고, 상기 스코어가 계산된 서브배열이 상기 적어도 하나의 서브배열과 중첩되지 않는 경우, 상기 스코어가 계산된 서브배열로 상기 가장 높은 스코어를 갖는 서브배열을 대체하고, 상기 스코어가 계산된 서브배열을 상기 상위 k 질의에 대한 응답의 후보군으로 결정하는 단계를 포함하는,상위 k 질의 처리 방법
|
| 4 |
4
제3항에 있어서,상기 스코어가 계산된 서브배열의 스코어가 상기 가장 높은 스코어를 갖는 서브배열의 스코어보다 크지 않는 경우, 상기 스코어가 계산된 서브배열을 상기 후보군으로 결정하는 단계를 더 포함하는,상위 k 질의 처리 방법
|
| 5 |
5
제3항 또는 제4항에 있어서,상기 복수의 파티션들 중에서 상기 제1 파티션을 제외한 파티션들 중 가장 큰 최대값을 제2 파티션을 선택하는 단계; 및상기 가장 높은 스코어를 갖는 서브배열의 스코어가 상기 제2 파티션의 상계 스코어(upper bound score, UBS) 보다 큰 경우, 상기 가장 높은 스코어를 갖는 서브배열을 상기 응답으로 결정하는 단계를 더 포함하는,상위 k 질의 처리 방법
|
| 6 |
6
제5항에 있어서,상기 상계 스코어(UBS)는 상기 제2 파티션의 최대 값과 서브배열에 포함되는 셀의 개수를 곱한 값인,상위 k 질의 처리 방법
|
| 7 |
7
제5항에 있어서,상기 후보군에 포함된 서브배열들 중 상기 응답으로 결정된 서브배열과 중첩되는 서브배열을 삭제하는 단계를 더 포함하는,상위 k 질의 처리 방법
|
| 8 |
8
제2항에 있어서,파티션은 미리 정해진 초기 파티션 크기보다 같거나 작은 크기를 갖는 직사각형 형태로 분할되고,상기 시작 셀은 파티션의 좌측 상단에 위치하는 셀을 의미하며,상기 마지막 셀은 파티션의 우측 하단에 위치하는 셀을 의미하는,상위 k 질의 처리 방법
|
