맞춤기술찾기

이전대상기술

선형 시간 Top-k 정렬 알고리즘

  • 기술번호 : KST2014046609
  • 담당센터 : 대전기술혁신센터
  • 전화번호 : 042-610-2279
요약, Int. CL, CPC, 출원번호/일자, 출원인, 등록번호/일자, 공개번호/일자, 공고번호/일자, 국제출원번호/일자, 국제공개번호/일자, 우선권정보, 법적상태, 심사진행상태, 심판사항, 구분, 원출원번호/일자, 관련 출원번호, 기술이전 희망, 심사청구여부/일자, 심사청구항수의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 서지정보 표입니다.
요약 본 발명은 대량의 원소로 구성된 집합에서 집합의 크기에 선형적으로 비례하는 시간 동안 가장 큰(또는 작은) 키 값을 가지는 k개의 원소(Top-k 결과)만을 정렬된 순서로 찾기 위한 알고리즘에 관한 것으로, 본 발명에 따르면, 크기가 k인 최소(또는 최대) 힙 구조에 Top-k 결과의 후보 데이터를 유지하는 알고리즘을 통하여 한 번의 데이터 스캔으로 Top-k 결과를 구할 수 있는 방법이 제공된다. 즉, 본 발명에 따르면, Top-k 결과를 찾기 위해 종래의 정렬 알고리즘을 사용하는 경우 정렬의 시간 복잡도가 O(nlogn) 이상이므로 집합의 크기에 선형적으로 비례하지 않는 문제를 해결하여, 시간 복잡도가 O(n)으로 집합의 크기에 선형적으로 비례하는 시간 동안 Top-k 결과를 찾을 수 있는 선형 시간 Top-k 정렬방법이 제공된다.
Int. CL G06F 9/44 (2006.01)
CPC G06F 16/00(2013.01) G06F 16/00(2013.01)
출원번호/일자 1020110037332 (2011.04.21)
출원인 한국과학기술원
등록번호/일자 10-1085967-0000 (2011.11.16)
공개번호/일자
공고번호/일자 (20111122) 문서열기
국제출원번호/일자
국제공개번호/일자
우선권정보
법적상태 등록
심사진행상태 수리
심판사항
구분 신규
원출원번호/일자
관련 출원번호
심사청구여부/일자 Y (2011.04.21)
심사청구항수 14

출원인

번호, 이름, 국적, 주소의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 인명정보 - 출원인 표입니다.
번호 이름 국적 주소
1 한국과학기술원 대한민국 대전광역시 유성구

발명자

번호, 이름, 국적, 주소의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 인명정보 - 발명자 표입니다.
번호 이름 국적 주소
1 황규영 대한민국 대전광역시 유성구
2 김민수 대한민국 대전광역시 유성구
3 이정훈 대한민국 대전광역시 유성구

대리인

번호, 이름, 국적, 주소의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 인명정보 - 대리인 표입니다.
번호 이름 국적 주소
1 이원희 대한민국 서울특별시 강남구 테헤란로 ***, 성지하이츠빌딩*차 ***호 (역삼동)

최종권리자

번호, 이름, 국적, 주소의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 인명정보 - 최종권리자 표입니다.
번호 이름 국적 주소
1 한국과학기술원 대한민국 대전광역시 유성구
번호, 서류명, 접수/발송일자, 처리상태, 접수/발송일자의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 행정처리 표입니다.
번호 서류명 접수/발송일자 처리상태 접수/발송번호
1 [우선심사신청]심사청구(우선심사신청)서
[Request for Preferential Examination] Request for Examination (Request for Preferential Examination)
2011.04.21 수리 (Accepted) 1-1-2011-0298316-49
2 [특허출원]특허출원서
[Patent Application] Patent Application
2011.04.21 수리 (Accepted) 1-1-2011-0297762-10
3 의견제출통지서
Notification of reason for refusal
2011.07.18 발송처리완료 (Completion of Transmission) 9-5-2011-0396448-80
4 [거절이유 등 통지에 따른 의견]의견(답변, 소명)서
[Opinion according to the Notification of Reasons for Refusal] Written Opinion(Written Reply, Written Substantiation)
2011.09.01 수리 (Accepted) 1-1-2011-0683944-22
5 [명세서등 보정]보정서
[Amendment to Description, etc.] Amendment
2011.09.01 보정승인간주 (Regarded as an acceptance of amendment) 1-1-2011-0683945-78
6 등록결정서
Decision to grant
2011.10.12 발송처리완료 (Completion of Transmission) 9-5-2011-0588056-99
7 출원인정보변경(경정)신고서
Notification of change of applicant's information
2013.02.01 수리 (Accepted) 4-1-2013-5019983-17
8 출원인정보변경(경정)신고서
Notification of change of applicant's information
2014.12.24 수리 (Accepted) 4-1-2014-5158129-58
9 출원인정보변경(경정)신고서
Notification of change of applicant's information
2014.12.24 수리 (Accepted) 4-1-2014-5157993-01
10 출원인정보변경(경정)신고서
Notification of change of applicant's information
2014.12.24 수리 (Accepted) 4-1-2014-5157968-69
11 출원인정보변경(경정)신고서
Notification of change of applicant's information
2019.04.24 수리 (Accepted) 4-1-2019-5081392-49
12 출원인정보변경(경정)신고서
Notification of change of applicant's information
2020.05.15 수리 (Accepted) 4-1-2020-5108396-12
13 출원인정보변경(경정)신고서
Notification of change of applicant's information
2020.06.12 수리 (Accepted) 4-1-2020-5131486-63
번호, 청구항의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 청구항 표입니다.
번호 청구항
1 1
대용량의 데이터를 처리해야 하는 검색 시스템 또는 분산 시스템에서 데이터를 중요도에 따라 나열했을 때 가장 중요한 상위 k개의 결과만을 출력하는 Top-k 질의 처리를 위해, 입력 데이터의 크기에 선형적으로 비례하는 선형 시간에 n개의 데이터 원소로부터 가장 큰 키 값을 가지는 k개의 데이터 원소를 구하기 위한 선형 시간 Top-k 정렬(Linear-Time Top-k Sort)방법에 있어서, n개의 원소로 구성된 전체 데이터의 집합 S로부터 k개의 데이터를 읽어 들이고, 상기 집합 S에 속하는 데이터 원소 중에서 한번 읽은 데이터 원소는 다시 읽지 않도록 하기 위해 상기 집합 S로부터 읽은 상기 k개의 데이터를 제거하는 제 1 단계와, 결과로서 출력할 최소 힙 구조인 topKHeap을 빈 트리로 초기화하고, 상기 제 1 단계에서 읽은 상기 k개의 데이터를 상기 topKHeap에 입력하여 초기 최소 힙 구조를 구성하는 제 2 단계와, 상기 집합 S에 속하는 임의의 원소 e를 추출하는 제 3 단계와, 상기 제 3 단계에서 추출된 상기 원소 e의 키 값과 루트 노드 r의 키 값을 비교하는 제 4 단계와, 상기 제 4 단계에서, 상기 원소 e의 키 값이 상기 루트 노드 r의 키 값보다 큰 경우는, 상기 원소 e로 상기 루트 노드 r을 대치하는 제 5 단계와, 상기 제 5 단계에서 대치된 상기 루트 노드의 키 값과 그 자식 노드들의 키 값을 비교하여 더 작은 키 값을 가지는 노드가 부모 노드가 되도록 상기 topKHeap을 재조정하는 제 6 단계와, 상기 집합 S로부터 읽은 상기 원소 e를 제거하는 제 7 단계와, 상기 집합 S가 공집합이 되어 더 이상 읽을 원소가 존재하지 않을 때까지 상기 제 3 단계 내지 상기 제 7 단계의 처리를 반복 수행하는 제 8 단계와, 상기 제 8 단계에서, 상기 집합 S가 공집합이면, k개의 가장 큰 키 값을 가지는 데이터 원소들을 저장한 최소 힙 구조인 상기 topKHeap을 결과로서 출력하는 제 9 단계를 포함하고, 상기 제 9단계는, 상기 k개의 데이터를 키 값이 큰 것부터 순차적으로 접근하기 위해, 상기 topKHeap에 저장된 상기 k개의 데이터를 키 값이 작은 것부터 출력한 뒤, 그 결과를 출력된 순서의 역순으로 읽도록 구성됨으로써, 상기 정렬방법의 시간 복잡도는, 각각 k개의 데이터로 초기 힙 구조를 구성하는 시간(O(klogk))과, n-k개 데이터를 읽어 들여 힙 구조를 재구성하는 시간(O((n-k)logk)) 및 k개의 데이터를 정렬하여 출력하는 시간(O(klogk))의 합으로 표현되고, 상수 c, c1 및 c2에 대하여, O(c1klogk + c2klogk + (n-k)logk) = O((n+ck)logk) (c = (c1+c2-1))이 되며, 여기서, c와 k는 상수이므로, 상기 시간 복잡도는, O((n+ck)logk) = O(n)이 되어, 상기 정렬방법 전체의 시간 복잡도가 전체 데이터 원소의 개수인 n에 선형적으로 비례하도록 구성된 것을 특징으로 하는 선형 시간 Top-k 정렬방법
2 2
제 1항에 있어서, 상기 정렬방법은, 입력 데이터 집합 S의 데이터 원소들을 읽고, 읽은 데이터 원소들을 집합 S에서 제거하는 모든 과정이 디스크와 같은 저장 장치에 저장된 데이터 원소들을 저장된 순서대로 한 번만 스캔하는 것만으로 수행되는 것을 특징으로 하는 선형 시간 Top-k 정렬방법
3 3
제 1항에 있어서, 상기 제 2 단계는, 새롭게 읽은 원소를 현재까지 구성되어 있는 최소 힙 구조의 말단 노드로서 삽입하고, 새롭게 삽입된 노드로부터 루트 노드에 이르는 경로를 따라가면서, 상기 경로 상에서 부모/자식 관계를 가지는 노드들 사이의 키 값을 비교하여 키 값이 더 작은 노드가 부모 노드가 되도록 트리 구조를 조정하는 과정을 통하여 O(klogk) 시간에 상기 초기 최소 힙 구조를 구성하는 것을 특징으로 하는 선형 시간 Top-k 정렬방법
4 4
제 1항에 있어서, 상기 제 4 단계는, 상기 원소 e의 키 값이 상기 루트 노드 r의 키 값보다 작을 경우는, 상기 제 7 단계로 바로 진행하여 상기 원소 e를 제거하는 것을 특징으로 하는 선형 시간 Top-k 정렬방법
5 5
제 1항에 있어서, 상기 제 6 단계는, 상기 제 5 단계에 의해 상기 topKHeap이 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작거나 같아야 한다는 최소 힙 구조의 조건을 위배하는 경우, 상기 topKHeap이 최소 힙 구조의 조건을 만족하도록 힙 재조정을 수행하며, 상기 재조정은 루트 노드부터 말단 노드에 이르는 경로 상에 존재하는 모든 부모/자식 관계를 가진 노드들에 대하여 반복적으로 수행되는 것을 특징으로 하는 선형 시간 Top-k 정렬방법
6 6
제 1항에 있어서, 상기 제 8 단계는, 전체 데이터 원소의 개수 n에서 상기 제 1 단계에서 초기 힙 구조를 구성하기 위해 읽어 들인 데이터 원소의 개수인 k를 뺀 n-k 만큼 상기 제 3 단계 내지 상기 제 7 단계의 과정이 반복 수행되도록 하는 것을 특징으로 하는 선형 시간 Top-k 정렬방법
7 7
삭제
8 8
대용량의 데이터를 처리해야 하는 검색 시스템 또는 분산 시스템에서 데이터를 중요도에 따라 나열했을 때 가장 중요한 상위 k개의 결과만을 출력하는 Top-k 질의 처리를 위해, 입력 데이터의 크기에 선형적으로 비례하는 선형 시간에 n개의 데이터 원소로부터 가장 작은 키 값을 가지는 k개의 데이터 원소를 구하기 위한 선형 시간 Top-k 정렬방법에 있어서, n개의 원소로 구성된 전체 데이터의 집합 S로부터 k개의 데이터를 읽어 들이고, 상기 집합 S에 속하는 데이터 원소 중에서 한번 읽은 데이터 원소는 다시 읽지 않도록 하기 위해 상기 집합 S로부터 읽은 상기 k개의 데이터를 제거하는 제 1 단계와, 결과로서 출력할 최대 힙 구조인 topKHeap을 빈 트리로 초기화하고, 상기 제 1 단계에서 읽은 상기 k개의 데이터를 상기 topKHeap에 입력하여 초기 최대 힙 구조를 구성하는 제 2 단계와, 상기 집합 S에 속하는 임의의 원소 e를 추출하는 제 3 단계와, 상기 제 3 단계에서 추출된 상기 원소 e의 키 값과 루트 노드 r의 키 값을 비교하는 제 4 단계와, 상기 제 4 단계에서, 상기 원소 e의 키 값이 상기 루트 노드 r의 키 값보다 작은 경우는, 상기 원소 e가 상기 루트 노드 r을 대치하는 제 5 단계와, 상기 제 5 단계에서 대치된 상기 루트 노드의 키 값과 그 자식 노드들의 키 값을 비교하여, 더 큰 키 값을 가지는 노드가 부모 노드가 되도록 상기 topKHeap을 재조정하는 제 6 단계와, 상기 집합 S로부터 읽은 상기 원소 e를 제거하는 제 7 단계와, 상기 집합 S가 공집합이 되어 더 이상 읽을 원소가 존재하지 않을 때까지 상기 제 3 단계 내지 상기 제 7단계의 처리를 반복 수행하는 제 8 단계와, 상기 제 8 단계에서, 상기 집합 S가 공집합이면, k개의 가장 작은 키 값을 가지는 데이터 원소들을 저장한 최대 힙 구조인 상기 topKHeap을 결과로서 출력하는 제 9 단계를 포함하고, 상기 제 9 단계는, 상기 k개의 데이터를 키 값이 작은 것부터 순차적으로 접근하기 위해, 상기 topKHeap에 저장된 상기 k개의 데이터를 키 값이 큰 것부터 출력한 뒤, 그 결과를 출력된 순서의 역순으로 읽도록 구성됨으로써, 상기 정렬방법의 시간 복잡도는, 각각 k개의 데이터로 초기 힙 구조를 구성하는 시간(O(klogk))과, n-k개 데이터를 읽어 들여 힙 구조를 재구성하는 시간(O((n-k)logk)) 및 k개의 데이터를 정렬하여 출력하는 시간(O(klogk))의 합으로 표현되고, 상수 c, c1 및 c2에 대하여, O(c1klogk + c2klogk + (n-k)logk) = O((n+ck)logk) (c = (c1+c2-1))이 되며, 여기서, c와 k는 상수이므로, 상기 시간 복잡도는, O((n+ck)logk) = O(n)이 되어, 상기 정렬방법 전체의 시간 복잡도가 전체 데이터 원소의 개수인 n에 선형적으로 비례하도록 구성된 것을 특징으로 하는 선형 시간 Top-k 정렬방법
9 9
제 8항에 있어서, 상기 정렬방법은, 입력 데이터 집합 S의 데이터 원소들을 읽고, 읽은 데이터 원소들을 집합 S에서 제거하는 모든 과정이 디스크와 같은 저장 장치에 저장된 데이터 원소들을 저장된 순서대로 한 번만 스캔하는 것만으로 수행되는 것을 특징으로 하는 선형 시간 Top-k 정렬방법
10 10
제 8항에 있어서, 상기 제 2 단계는, 새롭게 읽은 원소를 현재까지 구성되어 있는 최대 힙 구조의 말단 노드로서 삽입하고, 새롭게 삽입된 노드로부터 루트 노드에 이르는 경로를 따라가면서, 상기 경로 상에서 부모/자식 관계를 가지는 노드들 사이의 키 값을 비교하여 키 값이 더 큰 노드가 부모 노드가 되도록 트리 구조를 조정하는 과정을 통하여 O(klogk) 시간에 상기 초기 최대 힙 구조를 구성하는 것을 특징으로 하는 선형 시간 Top-k 정렬방법
11 11
제 8항에 있어서, 상기 제 4 단계는, 상기 원소 e의 키 값이 상기 루트 노드 r의 키 값보다 큰 경우는, 상기 제 7 단계로 바로 진행하여 상기 원소 e를 제거하는 것을 특징으로 하는 선형 시간 Top-k 정렬방법
12 12
제 8항에 있어서, 상기 제 6 단계는, 상기 제 5 단계에 의해 상기 topKHeap이 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크거나 같아야 한다는 최대 힙 구조의 조건을 위배하는 경우, 상기 topKHeap이 최대 힙 구조의 조건을 만족하도록 힙 재조정을 수행하며, 상기 재조정은 루트 노드부터 말단 노드에 이르는 경로 상에 존재하는 모든 부모/자식 관계를 가진 노드들에 대하여 반복적으로 수행되는 것을 특징으로 하는 선형 시간 Top-k 정렬방법
13 13
제 8항에 있어서, 상기 제 8 단계는, 전체 데이터 원소의 개수 n에서 상기 제 1 단계에서 초기 힙 구조를 구성하기 위해 읽어 들인 데이터 원소의 개수인 k를 뺀 n-k 만큼 상기 제 3 단계 내지 상기 제 7 단계의 과정이 반복 수행되도록 하는 것을 특징으로 하는 선형 시간 Top-k 정렬방법
14 14
삭제
15 15
청구항 1항 내지 6항 중 어느 한 항에 기재된 선형 시간 Top-k 정렬방법을 실행하도록 구성된 프로그램을 기록한 컴퓨터에서 판독 가능한 기록매체
16 16
청구항 8항 내지 13항 중 어느 한 항에 기재된 선형 시간 Top-k 정렬방법을 실행하도록 구성된 프로그램을 기록한 컴퓨터에서 판독 가능한 기록매체
17 17
삭제
18 18
삭제
지정국 정보가 없습니다
순번, 패밀리번호, 국가코드, 국가명, 종류의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 패밀리정보 - 패밀리정보 표입니다.
순번 패밀리번호 국가코드 국가명 종류
1 US08296306 US 미국 FAMILY
2 US20120271838 US 미국 FAMILY

DOCDB 패밀리 정보

순번, 패밀리번호, 국가코드, 국가명, 종류의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 패밀리정보 - DOCDB 패밀리 정보 표입니다.
순번 패밀리번호 국가코드 국가명 종류
DOCDB 패밀리 정보가 없습니다
순번, 연구부처, 주관기관, 연구사업, 연구과제의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 국가R&D 연구정보 정보 표입니다.
순번 연구부처 주관기관 연구사업 연구과제
1 교육과학기술부 한국과학기술원 도약연구사업(구 국가지정연구실) 유비쿼터스 소형 디바이스를 위한 맞춤형/경량 DB 엔진 기술 개발