맞춤기술찾기

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

이전대상기술

디스크 기반의 연결요소 그래프 질의 처리방법(Method for processing connected components graph interrogation based on disk)

  • 기술번호 : KST2016018136
  • 담당센터 : 대구기술혁신센터
  • 전화번호 : 053-550-1450
상담신청 PDF 받기
요약, Int. CL, CPC, 출원번호/일자, 출원인, 등록번호/일자, 공개번호/일자, 공고번호/일자, 국제출원번호/일자, 국제공개번호/일자, 우선권정보, 법적상태, 심사진행상태, 심판사항, 구분, 원출원번호/일자, 관련 출원번호, 기술이전 희망, 심사청구여부/일자, 심사청구항수의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 서지정보 표입니다.
요약 본 발명은 메모리에 적재되지 않은 크기의 큰 그래프도 디스크 기반 순차 지향 병렬 처리 접근 방식을 사용하여 빠르고 확장성 있는 그래프를 처리할 수 있도록 한 디스크 기반의 연결요소 그래프 질의 처리방법에 관한 것으로서, 상기 방법은, 상기 초고속 디스크와 메모리데 대한 접근 전략 중 속성 데이터와 그래프 위상 데이터 모두에 대하여 순차 디스크 접근 전략과 랜덤 메모리 접근 전략을 사용하여 디스크 기반의 그래프로 표현하여 연결 요소 그래프 질의를 처리하는 것이다.
Int. CL G06F 17/30 (2006.01)
CPC G06F 16/1847(2013.01) G06F 16/1847(2013.01) G06F 16/1847(2013.01)
출원번호/일자 1020150050350 (2015.04.09)
출원인 재단법인대구경북과학기술원
등록번호/일자
공개번호/일자 10-2016-0121009 (2016.10.19) 문서열기
공고번호/일자 문서열기
국제출원번호/일자
국제공개번호/일자
우선권정보
법적상태 등록
심사진행상태 수리
심판사항
구분 신규
원출원번호/일자
관련 출원번호
심사청구여부/일자 Y (2015.04.09)
심사청구항수 10

출원인

번호, 이름, 국적, 주소의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 인명정보 - 출원인 표입니다.
번호 이름 국적 주소
1 재단법인대구경북과학기술원 대한민국 대구 달성군 현

발명자

번호, 이름, 국적, 주소의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 인명정보 - 발명자 표입니다.
번호 이름 국적 주소
1 김민수 대한민국 대구광역시 달서구
2 박힘찬 대한민국 충청남도 계룡시

대리인

번호, 이름, 국적, 주소의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 인명정보 - 대리인 표입니다.
번호 이름 국적 주소
1 특허법인 무한 대한민국 서울특별시 강남구 언주로 ***, *층(역삼동,화물재단빌딩)

최종권리자

번호, 이름, 국적, 주소의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 인명정보 - 최종권리자 표입니다.
번호 이름 국적 주소
1 재단법인대구경북과학기술원 대한민국 대구 달성군 현
번호, 서류명, 접수/발송일자, 처리상태, 접수/발송일자의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 행정처리 표입니다.
번호 서류명 접수/발송일자 처리상태 접수/발송번호
1 [특허출원]특허출원서
[Patent Application] Patent Application		 2015.04.09 수리 (Accepted) 1-1-2015-0348392-54
2 선행기술조사의뢰서
Request for Prior Art Search		 2016.03.10 수리 (Accepted) 9-1-9999-9999999-89
3 선행기술조사보고서
Report of Prior Art Search		 2016.05.10 수리 (Accepted) 9-1-2016-0019922-13
4 의견제출통지서
Notification of reason for refusal		 2016.05.17 발송처리완료 (Completion of Transmission) 9-5-2016-0354880-01
5 [지정기간연장]기간연장(단축, 경과구제)신청서
[Designated Period Extension] Application of Period Extension(Reduction, Progress relief)		 2016.07.18 수리 (Accepted) 1-1-2016-0693057-12
6 [지정기간연장]기간연장(단축, 경과구제)신청서
[Designated Period Extension] Application of Period Extension(Reduction, Progress relief)		 2016.08.17 수리 (Accepted) 1-1-2016-0796756-45
7 [지정기간연장]기간연장(단축, 경과구제)신청서
[Designated Period Extension] Application of Period Extension(Reduction, Progress relief)		 2016.09.19 수리 (Accepted) 1-1-2016-0900520-41
8 [지정기간연장]기간연장(단축, 경과구제)신청서
[Designated Period Extension] Application of Period Extension(Reduction, Progress relief)		 2016.10.17 수리 (Accepted) 1-1-2016-1003678-28
9 지정기간연장 관련 안내서
Notification for Extension of Designated Period		 2016.10.19 발송처리완료 (Completion of Transmission) 1-5-2016-0151572-39
10 [명세서등 보정]보정서
[Amendment to Description, etc.] Amendment		 2016.11.10 보정승인간주 (Regarded as an acceptance of amendment) 1-1-2016-1100715-28
11 [대리인선임]대리인(대표자)에 관한 신고서
[Appointment of Agent] Report on Agent (Representative)		 2017.01.13 수리 (Accepted) 1-1-2017-0042374-13
12 의견제출통지서
Notification of reason for refusal		 2017.03.30 발송처리완료 (Completion of Transmission) 9-5-2017-0228777-63
13 [거절이유 등 통지에 따른 의견]의견(답변, 소명)서
[Opinion according to the Notification of Reasons for Refusal] Written Opinion(Written Reply, Written Substantiation)		 2017.05.18 수리 (Accepted) 1-1-2017-0473671-66
14 [명세서등 보정]보정서
[Amendment to Description, etc.] Amendment		 2017.05.18 보정승인간주 (Regarded as an acceptance of amendment) 1-1-2017-0473670-10
15 등록결정서
Decision to grant		 2017.09.29 발송처리완료 (Completion of Transmission) 9-5-2017-0691551-90
16 출원인정보변경(경정)신고서
Notification of change of applicant's information		 2018.12.18 수리 (Accepted) 4-1-2018-5260250-39
17 출원인정보변경(경정)신고서
Notification of change of applicant's information		 2020.06.18 수리 (Accepted) 4-1-2020-5134633-04
번호, 청구항의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 청구항 표입니다.
번호 청구항
1 1
초고속 디스크 기반의 연결요소 그래프 질의 처리방법에 있어서, 상기 초고속 디스크와 메모리에 대한 접근 전략 중 속성 데이터와 그래프 위상 데이터 모두에 대하여 기 설정된 디스크의 순차 접근 방식 및 랜덤 메모리 접근 방식을 사용하여 연결 요소 그래프를 처리하는 것이고, 상기 메모리는, 연결 요소를 저장하는 컴포넌트 ID 벡터(Component ID Vector) 공간, 연결요소 질의 처리에 핵심적으로 사용되는 디스조인트(Disjoint)한 셋(Set)을 저장하는 디스조인트 셋 벡터(Disjoint Set Vector) 공간을 포함하는,초고속 디스크 기반의 연결요소 그래프 질의 처리방법
2 2
제1항에 있어서, 상기 메모리는, 대규모 병렬화에서 빠르고 효율적인 BFS 탐색을 도와주는 방문 유무 정보를 저장하는 비지티드 비트맵 어레이(Visited Bitmap Array) 공간 및 연산을 위해 청크(Chunk) 단위로 디스크에서 위상 정보를 읽어오는 청크 버퍼 풀(Chunk Buffer Pool)을 더 포함하고, 상기 초고속 디스크는 상기 메모리의 용량보다 큰 규모의 그래프 데이터의 위상 데이터를 다수의 슬롯티드 페이지 형태로 저장하는 것인 초고속 디스크 기반의 연결 요소 그래프 질의 처리 방법
3 3
제1항에 있어서,상기 그래프의 처리는 UNION과 FIND 연산을 이용하여 처리하는 것인 초고속 디스크 기반의 연결 요소 그래프 질의 처리 방법
4 4
제3항에 있어서, 상기 UNION과 FIND 연산은, 그래프 기반 데이터베이스를 전체적으로 한번만 스캔하여 UNION과 FIND 연산을 사용하여 연결 요소 처리를 수행하는 것인 초고속 디스크 기반의 연결 요소 그래프 질의 처리 방법
5 5
제4항에 있어서,상기 UNION과 FIND 연산을 사용하여 연결 요소의 처리는, 처리가 필요하지 않은 부분인 백워드 엣지의 확인을 생략함으로써 낭비되는 데이터 접근의 양을 줄이는 백워드 엣지(backward edges) 생략 기법, 그래프 순회 초기 단계에서 많은 CPU 코어가 활성화되지 않고 유휴 상태로 존재하는 성능 저하 문제를 해결하는 여러 개의 시작점을 두는 기법, 무작위적인 그래프 위상정보로 인한 CPU 캐시 미스가 발생시키는 속도 저하를 해결하는 페이지 수준 캐시 친화적 처리 기법을 포함하는 것인 초고속 디스크 기반의 연결 요소 그래프 질의 처리 방법
6 6
제1항에 있어서, 디스크 기반의 그래프로 표현은, 초고속 디스크에서 그래프의 위상 데이터를 순차적으로 접근 가능하도록 슬롯티드 페이지 구조로 사용하는 것인 초고속 디스크 기반의 연결 요소 그래프 질의 처리방법
7 7
제1항에 있어서, 상기 초고속 디스크로부터 그래프 데이터를 순차 접근 전략 사용한 연결 요소 질의의 처리는, chunk-by-chunk 단위로 오직 한번 씩만 스캔하여 첫 번째 chunk의 페이지를 불러온 후, 두 번째 페이지를 비동기적으로 로딩하여 처리하는 것인 초고속 디스크 기반의 연결 요소 그래프 질의 처리방법
8 8
제5항에 있어서, 상기 처리가 필요하지 않은 부분인 백워드 엣지의 확인을 생략함으로써 낭비되는 데이터 접근의 양을 줄이는 백워드 엣지(backward edges) 생략 기법은, 그래프 데이터베이스를 순차적으로 스캔하는 동안에 이전 chunk의 정보로부터 다음 chunk에서 유용한 정보를 전파함으로써 개별적으로 불필요게 생성될 수 있는 디스코인트 셋을 방지하는 것인 초고속 디스크 기반의 연결 요소 그래프 질의 처리방법
9 9
제5항에 있어서, 상기 그래프 순회 초기 단계에서 많은 CPU 코어가 활성화되지 않고 유휴 상태로 존재하는 성능 저하 문제를 해결하는 여러 개의 시작점을 두는 기법은, 하나의 시작점을 가지고 BFS등의 그래프 탬색을 하는 경우, 그래프 탐색의 첫 번째 단계 동안에 병렬로 실행될 충분한 후손이 만들어지지 않아 초기 단계에서 완전하게 CPU코어를 활용하지 못하는 것을 방지하기 위해 여러 개의 탐색 시작 모드를 구성하는 것인 초고속 디스크 기반의 연결 요소 그래프 질의 처리방법
10 10
제5항에 있어서, 상기 무작위적인 그래프 위상정보로 인한 CPU 캐시 미스가 발생시키는 속도 저하를 해결하는 페이지 수준 캐시 친화적 처리 기법은, 그래프 데이터의 무작위적인 위상 정보로부터의 캐시 미스로 인해 병렬 처리 성능저하를 방지하기 위해 각 쓰레드는 오직 자신이 담당하는 페이지 집합내에서만 순회를 하되, 해당 영역을 벗어나는 순회에 대해서는 다른 쓰레드에게 순회 권한을 넘겨서 계속 진행하는 것인 초고속 디스크 기반의 연결 요소 그래프 질의 처리방법
지정국 정보가 없습니다
패밀리정보가 없습니다
순번, 연구부처, 주관기관, 연구사업, 연구과제의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 국가R&D 연구정보 정보 표입니다.
순번 연구부처 주관기관 연구사업 연구과제
1 미래창조과학부 대구경북과학기술원 신진연구자지원 빅 그래프를 위한 SSD 기반의 효율적인 연결요소 분석 방법