맞춤기술찾기

홈으로 가기
맞춤기술찾기
이전대상기술
프린트하기

이전대상기술

공간 분할 트리의 최소 데이터-불균등 커버를 이용한 다차원 히스토그램 방법 및 이를 실행하기 위한 프로그램이 저장된 기록매체

  • 기술번호 : KST2015113873
  • 담당센터 : 대전기술혁신센터
  • 전화번호 : 042-610-2279
상담신청 PDF 받기
요약, Int. CL, CPC, 출원번호/일자, 출원인, 등록번호/일자, 공개번호/일자, 공고번호/일자, 국제출원번호/일자, 국제공개번호/일자, 우선권정보, 법적상태, 심사진행상태, 심판사항, 구분, 원출원번호/일자, 관련 출원번호, 기술이전 희망, 심사청구여부/일자, 심사청구항수의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 서지정보 표입니다.
요약 본 발명은 다차원 데이터에 대한 질의의 선택도, 즉 질의의 결과 크기를 추정하는 데 이용되는 공간 분할 트리의 최소 데이터-불균등 커버를 이용한 다차원 히스토그램 방법 및 상기 다차원 히스토그램 방법을 실행하기 위한 프로그램이 기록된 기록매체에 관한 것이다. 보다 상세하게는, ⒜ 데이터베이스 시스템이 외부로부터 히스토그램 생성을 위한 정보를 입력받은 후, 상기 히스토그램 생성을 위한 정보를 토대로 공간 분할 트리를 형성하는 단계; ⒝ 상기 데이터베이스 시스템이 공간 분할 트리의 최소 데이터-불균등 커버(Minimal Data-Skew Cover)를 토대로 다차원 히스토그램을 형성하는 단계; 및 ⒞ 상기 데이터베이스 시스템이 외부로부터 질의를 입력받은 후, 상기 다차원 히스토그램 및 상기 질의를 토대로 질의 선택도를 추정하는 단계; 를 포함한다. 아울러, 본 발명은 상기 본 발명에 따른 다차원 히스토그램 방법을 실행하기 위한 프로그램이 기록된 저장매체를 포함한다.본 발명은 종래의 다차원 히스토그램 방법과 달리 데이터 객체가 균등하게 분포되지 않은 상황에서도 영역 질의의 선택도에 대한 추정값 계산의 정확성을 확보하는 효과가 있다.다차원 히스토그램, 최적화, 데이터베이스 질의 처리, 선택도 추정
Int. CL G06F 17/00 (2006.01) G06F 17/30 (2006.01)
CPC
출원번호/일자 1020090124523 (2009.12.15)
출원인 한국과학기술원
등록번호/일자 10-1117709-0000 (2012.02.10)
공개번호/일자 10-2011-0067781 (2011.06.22) 문서열기
공고번호/일자 (20120224) 문서열기
국제출원번호/일자
국제공개번호/일자
우선권정보
법적상태 소멸
심사진행상태 수리
심판사항
구분 신규
원출원번호/일자
관련 출원번호
심사청구여부/일자 Y (2009.12.15)
심사청구항수 10

출원인

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

발명자

번호, 이름, 국적, 주소의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 인명정보 - 발명자 표입니다.
번호 이름 국적 주소
1 김명호 대한민국 대전광역시 유성구
2 노요한 대한민국 대전광역시 유성구
3 김재호 대한민국 경기도 이천시
4 손진현 대한민국 경기도 용인시 수지구

대리인

번호, 이름, 국적, 주소의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 인명정보 - 대리인 표입니다.
번호 이름 국적 주소
1 이은철 대한민국 서울특별시 송파구 법원로**길 **, A동 *층 ***호 (문정동, H비지니스파크)(*T국제특허법률사무소)

최종권리자

번호, 이름, 국적, 주소의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 인명정보 - 최종권리자 표입니다.
번호 이름 국적 주소
1 한국과학기술원 대전광역시 유성구
번호, 서류명, 접수/발송일자, 처리상태, 접수/발송일자의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 행정처리 표입니다.
번호 서류명 접수/발송일자 처리상태 접수/발송번호
1 [특허출원]특허출원서
[Patent Application] Patent Application		 2009.12.15 수리 (Accepted) 1-1-2009-0773569-99
2 선행기술조사의뢰서
Request for Prior Art Search		 2011.01.12 수리 (Accepted) 9-1-9999-9999999-89
3 선행기술조사보고서
Report of Prior Art Search		 2011.02.21 수리 (Accepted) 9-1-2011-0016060-74
4 의견제출통지서
Notification of reason for refusal		 2011.03.09 발송처리완료 (Completion of Transmission) 9-5-2011-0131538-09
5 [지정기간연장]기간연장(단축, 경과구제)신청서
[Designated Period Extension] Application of Period Extension(Reduction, Progress relief)		 2011.05.04 수리 (Accepted) 1-1-2011-0332142-90
6 [거절이유 등 통지에 따른 의견]의견(답변, 소명)서
[Opinion according to the Notification of Reasons for Refusal] Written Opinion(Written Reply, Written Substantiation)		 2011.06.08 수리 (Accepted) 1-1-2011-0428310-37
7 [명세서등 보정]보정서
[Amendment to Description, etc.] Amendment		 2011.06.08 보정승인간주 (Regarded as an acceptance of amendment) 1-1-2011-0428312-28
8 거절결정서
Decision to Refuse a Patent		 2011.11.24 발송처리완료 (Completion of Transmission) 9-5-2011-0686575-49
9 [거절이유 등 통지에 따른 의견]의견(답변, 소명)서
[Opinion according to the Notification of Reasons for Refusal] Written Opinion(Written Reply, Written Substantiation)		 2011.12.23 수리 (Accepted) 1-1-2011-1029569-75
10 [명세서등 보정]보정서(재심사)
Amendment to Description, etc(Reexamination)		 2011.12.23 보정승인 (Acceptance of amendment) 1-1-2011-1029570-11
11 등록결정서
Decision to Grant Registration		 2012.01.26 발송처리완료 (Completion of Transmission) 9-5-2012-0050632-05
12 출원인정보변경(경정)신고서
Notification of change of applicant's information		 2013.02.01 수리 (Accepted) 4-1-2013-5019983-17
13 출원인정보변경(경정)신고서
Notification of change of applicant's information		 2014.12.24 수리 (Accepted) 4-1-2014-5157968-69
14 출원인정보변경(경정)신고서
Notification of change of applicant's information		 2014.12.24 수리 (Accepted) 4-1-2014-5157993-01
15 출원인정보변경(경정)신고서
Notification of change of applicant's information		 2014.12.24 수리 (Accepted) 4-1-2014-5158129-58
16 출원인정보변경(경정)신고서
Notification of change of applicant's information		 2019.04.24 수리 (Accepted) 4-1-2019-5081392-49
17 출원인정보변경(경정)신고서
Notification of change of applicant's information		 2020.05.15 수리 (Accepted) 4-1-2020-5108396-12
18 출원인정보변경(경정)신고서
Notification of change of applicant's information		 2020.06.12 수리 (Accepted) 4-1-2020-5131486-63
번호, 청구항의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 청구항 표입니다.
번호 청구항
1 1
질의(Query)의 선택도(Selectivity)를 추정하기 위하여 공간 분할 트리를 이용한 다차원 히스토그램 방법에 있어서, ⒜ 데이터베이스 시스템이 외부로부터 히스토그램 생성을 위한 정보를 입력받은 후, 상기 히스토그램 생성을 위한 정보를 토대로 공간 분할 트리를 형성하는 단계; 및⒝ 상기 데이터베이스 시스템이 공간 분할 트리의 최소 데이터-불균등 커버(Minimal Data-Skew Cover)를 토대로 다차원 히스토그램을 형성하는 단계; 를 포함하고,상기 ⒝ 단계는,(b-1) 상기 데이터베이스 시스템이 상기 공간 분할 트리 내 포함된 노드(Node)를 토대로 상기 공간 분할 트리의 커버(Cover)를 탐색하는 단계;(b-2) 상기 데이터베이스 시스템이 임의의 공간 분할 트리의 커버(Cover)에 대해, 상기 임의의 공간 분할 트리의 커버(Cover) 내 포함된 노드의 수가 최대 허용 버킷 수보다 작은지 여부 및 상기 임의의 공간 분할 트리의 커버(Cover)내 포함된 각 노드의 노드 데이터 불균등 값의 합계가 최소인지 여부에 의해 최소 데이터-불균등 커버(Minimal Data-Skew Cover)를 판단하는 단계; 및(b-3) 상기 데이터베이스 시스템이 상기 최소 데이터-불균등 커버(Minimal Data-Skew Cover) 내에 포함된 노드를 토대로 하여 다차원 히스토그램의 버킷을 형성함으로써 다차원 히스토그램으로 생성하는 단계; 를 포함하고,상기 ⒜ 단계는,(a-1) 상기 데이터베이스 시스템이 외부로부터 전체 데이터 공간, 데이터 집합 및 최대 허용 버킷 수를 상기 히스토그램 생성을 위한 정보로 입력받은 후, 상기 전체 데이터 공간 및 데이터 집합을 소정의 크기를 갖는 적어도 하나 이상의 구역으로 분할하는 단계; (a-2) 상기 데이터베이스 시스템이 상기 소정의 크기를 갖는 적어도 하나 이상의 구역 내 포함된 데이터 객체의 최소 경계 영역(MBR)을 획득하고, 획득된 최소 경계 영역(MBR)을 토대로 공간 분할 트리 내 포함되는 노드(Node)를 생성하여 공간 분할 트리를 형성하는 단계; 및(a-3) 상기 공간 분할 트리 내 포함된 노드(Node) 별로 노드 데이터 불균등값을 계산하는 단계; 를 포함하고,상기 (b) 단계 이후에,⒞ 상기 데이터베이스 시스템이 외부로부터 질의를 입력받은 후, 상기 다차원 히스토그램 및 상기 질의를 토대로 질의의 선택도를 추정하는 단계; 를 더 포함하고,상기 ⒞ 단계는, 외부로부터 영역 질의(Range Query)가 입력된 경우, 상기 데이터베이스 시스템이 다음과 같은 수식에 의해 상기 영역 질의(Range Query)의 선택도에 대한 추정값을 계산함으로써 질의의 선택도를 추정하는 것을 특징으로 하는 질의의 선택도를 추정하기 위하여 공간 분할 트리를 이용한 다차원 히스토그램 방법
2 2
제 1 항에 있어서, 상기 히스토그램 생성을 위한 정보는, 전체 데이터 공간, 데이터 집합, 최대 허용 버킷 수 및 인덱스 구조 중 어느 하나 이상을 포함하는 질의의 선택도를 추정하기 위하여 공간 분할 트리를 이용한 다차원 히스토그램 방법
3 3
삭제
4 4
제 1 항에 있어서, 상기 (a-1) 단계는,2진 공간 분할(Binary Space Partitioning) 방식 및 완전 4진 트리 분할(Complete Quadtree Partitioning) 방식 중 어느 하나의 방식에 의해 전체 데이터 공간 및 데이터 집합을 소정의 크기를 갖는 적어도 하나 이상의 구역으로 분할하는 것을 특징으로 하는 질의의 선택도를 추정하기 위하여 공간 분할 트리를 이용한 다차원 히스토그램 방법
5 5
제 2 항에 있어서, 상기 ⒜ 단계는,(a''-1) 상기 데이터베이스 시스템이 외부로부터 인덱스 구조, 데이터 집합 및 최대 허용 버킷 수를 상기 히스토그램 생성을 위한 정보로 입력받은 후, 상기 데이터 집합 및 인덱스 구조에 기반하여 공간 분할 트리를 형성하는 단계; 및(a''-2) 상기 공간 분할 트리에 포함된 노드(Node) 별로 노드 데이터 불균등 값을 계산하는 단계; 를 포함하는 질의의 선택도를 추정하기 위하여 공간 분할 트리를 이용한 다차원 히스토그램 방법
6 6
삭제
7 7
제 1 항에 있어서, 상기 다차원 히스토그램의 버킷은, 초월평면(Hyperrectangle) 형태로 형성되는 질의의 선택도를 추정하기 위하여 공간 분할 트리를 이용한 다차원 히스토그램 방법
8 8
삭제
9 9
질의의 선택도를 추정하기 위하여 공간 분할 트리를 이용하는 다차원 히스토그램 방법을 실행하기 위한 프로그램이 저장된 기록매체에 있어서, 상기 다차원 히스토그램 방법은,⒜ 데이터베이스 시스템이 외부로부터 히스토그램 생성을 위한 정보를 입력받은 후, 이를 토대로 공간 분할 트리를 형성하는 단계; 및⒝ 상기 데이터베이스 시스템이 공간 분할 트리의 최소 데이터-불균등 커버(Minimal Data-Skew Cover)를 토대로 다차원 히스토그램을 형성하는 단계; 를 포함하고,상기 ⒝ 단계는,(b-1) 상기 데이터베이스 시스템이 상기 공간 분할 트리 내 포함된 노드(Node)를 토대로 상기 공간 분할 트리의 커버(Cover)를 탐색하는 단계;(b-2) 상기 데이터베이스 시스템이 임의의 공간 분할 트리의 커버(Cover)에 대해, 상기 임의의 공간 분할 트리의 커버(Cover) 내 포함된 노드의 수가 최대 허용 버킷 수보다 작은지 여부 및 상기 임의의 공간 분할 트리의 커버(Cover)내 포함된 각 노드의 노드 데이터 불균등 값의 합계가 최소인지 여부에 의해 최소 데이터-불균등 커버(Minimal Data-Skew Cover)를 판단하는 단계; 및(b-3) 상기 데이터베이스 시스템이 상기 최소 데이터-불균등 커버(Minimal Data-Skew Cover) 내에 포함된 노드를 토대로 하여 다차원 히스토그램의 버킷을 형성함으로써 다차원 히스토그램을 생성하는 단계; 를 포함하고,상기 ⒜ 단계는,(a-1) 상기 데이터베이스 시스템이 외부로부터 전체 데이터 공간, 데이터 집합 및 최대 허용 버킷 수를 상기 히스토그램 생성을 위한 정보로 입력받은 후, 상기 전체 데이터 공간 및 데이터 집합을 소정의 크기를 갖는 적어도 하나 이상의 구역으로 분할하는 단계; (a-2) 상기 데이터베이스 시스템이 상기 소정의 크기를 갖는 적어도 하나 이상의 구역 내 포함된 데이터 객체의 최소 경계 영역(MBR)을 획득하고, 획득된 최소 경계 영역(MBR)을 토대로 공간 분할 트리 내 포함되는 노드(Node)를 생성하여 공간 분할 트리를 형성하는 단계; 및(a-3) 상기 공간 분할 트리 내 포함된 노드(Node) 별로 노드 데이터 불균등 값을 계산하는 단계; 를 포함하고,상기 (b) 단계 이후에,⒞ 상기 데이터베이스 시스템이 외부로부터 질의를 입력받은 후, 상기 다차원 히스토그램 및 상기 질의를 토대로 질의의 선택도를 추정하는 단계; 를 더 포함하고,외부로부터 영역 질의(Range Query)가 입력된 경우, 상기 데이터베이스 시스템이 다음과 같은 수식에 의해 상기 영역 질의(Range Query)의 선택도에 대한 추정값을 계산함으로써 질의의 선택도를 추정하는 것을 특징으로 하는 질의의 선택도를 추정하기 위하여 공간 분할 트리를 이용한 다차원 히스토그램 방법을 실행하기 위한 프로그램이 저장된 기록매체
10 10
제 9 항에 있어서, 상기 히스토그램 생성을 위한 정보는, 전체 데이터 공간, 데이터 집합, 최대 허용 버킷 수 및 인덱스 구조 중 어느 하나 이상을 포함하는 질의의 선택도를 추정하기 위하여 공간 분할 트리를 이용하는 다차원 히스토그램 방법을 실행하기 위한 프로그램이 저장된 기록매체
11 11
삭제
12 12
제 9 항에 있어서,상기 (a-1) 단계는,2진 공간 분할(Binary Space Partitioning) 방식 및 완전 4진 트리 분할(Complete Quadtree Partitioning) 방식 중 어느 하나의 방식에 의해 전체 데이터 공간 및 데이터 집합을 소정의 크기를 갖는 적어도 하나 이상의 구역으로 분할하는 것을 특징으로 하는 질의의 선택도를 추정하기 위하여 공간 분할 트리를 이용한 다차원 히스토그램 방법을 실행하기 위한 프로그램이 저장된 기록매체
13 13
제 10 항에 있어서, 상기 ⒜ 단계는,(a''-1) 상기 데이터베이스 시스템이 외부로부터 인덱스 구조, 데이터 집합 및 최대 허용 버킷 수를 상기 히스토그램 생성을 위한 정보로 입력받은 후, 상기 데이터 집합 및 인덱스 구조에 기반하여 공간 분할 트리를 형성하는 단계; 및(a''-2) 상기 공간 분할 트리에 포함된 노드(Node) 별로 노드 데이터 불균등 값을 계산하는 단계; 를 포함하는 질의의 선택도를 추정하기 위하여 공간 분할 트리를 이용하는 다차원 히스토그램 방법을 실행하기 위한 프로그램이 저장된 기록매체
14 14
삭제
15 15
제 9 항에 있어서, 상기 다차원 히스토그램의 버킷은, 초월평면(Hyperrectangle) 형태로 형성되는 것을 특징으로 하는 질의의 선택도를 추정하기 위하여 공간 분할 트리를 이용하는 다차원 히스토그램 방법을 실행하기 위한 프로그램이 저장된 기록매체
16 16
삭제
지정국 정보가 없습니다
순번, 패밀리번호, 국가코드, 국가명, 종류의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 패밀리정보 - 패밀리정보 표입니다.
순번 패밀리번호 국가코드 국가명 종류
1 US20110145244 US 미국 FAMILY

DOCDB 패밀리 정보

순번, 패밀리번호, 국가코드, 국가명, 종류의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 패밀리정보 - DOCDB 패밀리 정보 표입니다.
순번 패밀리번호 국가코드 국가명 종류
1 US2011145244 US 미국 DOCDBFAMILY
순번, 연구부처, 주관기관, 연구사업, 연구과제의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 국가R&D 연구정보 정보 표입니다.
순번 연구부처 주관기관 연구사업 연구과제
1 교육과학기술부 한국연구재단 기초과학연구사업 (세부사업명: 도약연구지원사업) Life Logging Memory Management 기술개발(1단계/3차)