[go: up one dir, main page]
More Web Proxy on the site http://driver.im/

KR20060095444A - 실체 검색 시스템 - Google Patents

실체 검색 시스템 Download PDF

Info

Publication number
KR20060095444A
KR20060095444A KR1020060002112A KR20060002112A KR20060095444A KR 20060095444 A KR20060095444 A KR 20060095444A KR 1020060002112 A KR1020060002112 A KR 1020060002112A KR 20060002112 A KR20060002112 A KR 20060002112A KR 20060095444 A KR20060095444 A KR 20060095444A
Authority
KR
South Korea
Prior art keywords
grid
entity
quad tree
raw
raw data
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
KR1020060002112A
Other languages
English (en)
Inventor
데이비드 알. 뷰어러
던캔 엠. 라우러
Original Assignee
마이크로소프트 코포레이션
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 마이크로소프트 코포레이션 filed Critical 마이크로소프트 코포레이션
Publication of KR20060095444A publication Critical patent/KR20060095444A/ko
Ceased legal-status Critical Current

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/50—Information retrieval; Database structures therefor; File system structures therefor of still image data
    • G06F16/58—Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually
    • G06F16/583—Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually using metadata automatically derived from the content
    • G06F16/5854—Retrieval characterised by using metadata, e.g. metadata not derived from the content or metadata generated manually using metadata automatically derived from the content using shape and object relationship
    • B—PERFORMING OPERATIONS; TRANSPORTING
    • B60—VEHICLES IN GENERAL
    • B60K—ARRANGEMENT OR MOUNTING OF PROPULSION UNITS OR OF TRANSMISSIONS IN VEHICLES; ARRANGEMENT OR MOUNTING OF PLURAL DIVERSE PRIME-MOVERS IN VEHICLES; AUXILIARY DRIVES FOR VEHICLES; INSTRUMENTATION OR DASHBOARDS FOR VEHICLES; ARRANGEMENTS IN CONNECTION WITH COOLING, AIR INTAKE, GAS EXHAUST OR FUEL SUPPLY OF PROPULSION UNITS IN VEHICLES
    • B60K6/00—Arrangement or mounting of plural diverse prime-movers for mutual or common propulsion, e.g. hybrid propulsion systems comprising electric motors and internal combustion engines ; Control systems therefor, i.e. systems controlling two or more prime movers, or controlling one of these prime movers and any of the transmission, drive or drive units
    • B60K6/20—Arrangement or mounting of plural diverse prime-movers for mutual or common propulsion, e.g. hybrid propulsion systems comprising electric motors and internal combustion engines ; Control systems therefor, i.e. systems controlling two or more prime movers, or controlling one of these prime movers and any of the transmission, drive or drive units the prime-movers consisting of electric motors and internal combustion engines, e.g. HEVs
    • B60K6/42—Arrangement or mounting of plural diverse prime-movers for mutual or common propulsion, e.g. hybrid propulsion systems comprising electric motors and internal combustion engines ; Control systems therefor, i.e. systems controlling two or more prime movers, or controlling one of these prime movers and any of the transmission, drive or drive units the prime-movers consisting of electric motors and internal combustion engines, e.g. HEVs characterised by the architecture of the hybrid electric vehicle
    • B60K6/44—Series-parallel type
    • B60K6/445—Differential gearing distribution type
    • B—PERFORMING OPERATIONS; TRANSPORTING
    • B60—VEHICLES IN GENERAL
    • B60K—ARRANGEMENT OR MOUNTING OF PROPULSION UNITS OR OF TRANSMISSIONS IN VEHICLES; ARRANGEMENT OR MOUNTING OF PLURAL DIVERSE PRIME-MOVERS IN VEHICLES; AUXILIARY DRIVES FOR VEHICLES; INSTRUMENTATION OR DASHBOARDS FOR VEHICLES; ARRANGEMENTS IN CONNECTION WITH COOLING, AIR INTAKE, GAS EXHAUST OR FUEL SUPPLY OF PROPULSION UNITS IN VEHICLES
    • B60K6/00—Arrangement or mounting of plural diverse prime-movers for mutual or common propulsion, e.g. hybrid propulsion systems comprising electric motors and internal combustion engines ; Control systems therefor, i.e. systems controlling two or more prime movers, or controlling one of these prime movers and any of the transmission, drive or drive units
    • B60K6/20—Arrangement or mounting of plural diverse prime-movers for mutual or common propulsion, e.g. hybrid propulsion systems comprising electric motors and internal combustion engines ; Control systems therefor, i.e. systems controlling two or more prime movers, or controlling one of these prime movers and any of the transmission, drive or drive units the prime-movers consisting of electric motors and internal combustion engines, e.g. HEVs
    • B60K6/22—Arrangement or mounting of plural diverse prime-movers for mutual or common propulsion, e.g. hybrid propulsion systems comprising electric motors and internal combustion engines ; Control systems therefor, i.e. systems controlling two or more prime movers, or controlling one of these prime movers and any of the transmission, drive or drive units the prime-movers consisting of electric motors and internal combustion engines, e.g. HEVs characterised by apparatus, components or means specially adapted for HEVs
    • B60K6/26—Arrangement or mounting of plural diverse prime-movers for mutual or common propulsion, e.g. hybrid propulsion systems comprising electric motors and internal combustion engines ; Control systems therefor, i.e. systems controlling two or more prime movers, or controlling one of these prime movers and any of the transmission, drive or drive units the prime-movers consisting of electric motors and internal combustion engines, e.g. HEVs characterised by apparatus, components or means specially adapted for HEVs characterised by the motors or the generators
    • B—PERFORMING OPERATIONS; TRANSPORTING
    • B60—VEHICLES IN GENERAL
    • B60K—ARRANGEMENT OR MOUNTING OF PROPULSION UNITS OR OF TRANSMISSIONS IN VEHICLES; ARRANGEMENT OR MOUNTING OF PLURAL DIVERSE PRIME-MOVERS IN VEHICLES; AUXILIARY DRIVES FOR VEHICLES; INSTRUMENTATION OR DASHBOARDS FOR VEHICLES; ARRANGEMENTS IN CONNECTION WITH COOLING, AIR INTAKE, GAS EXHAUST OR FUEL SUPPLY OF PROPULSION UNITS IN VEHICLES
    • B60K6/00—Arrangement or mounting of plural diverse prime-movers for mutual or common propulsion, e.g. hybrid propulsion systems comprising electric motors and internal combustion engines ; Control systems therefor, i.e. systems controlling two or more prime movers, or controlling one of these prime movers and any of the transmission, drive or drive units
    • B60K6/20—Arrangement or mounting of plural diverse prime-movers for mutual or common propulsion, e.g. hybrid propulsion systems comprising electric motors and internal combustion engines ; Control systems therefor, i.e. systems controlling two or more prime movers, or controlling one of these prime movers and any of the transmission, drive or drive units the prime-movers consisting of electric motors and internal combustion engines, e.g. HEVs
    • B60K6/22—Arrangement or mounting of plural diverse prime-movers for mutual or common propulsion, e.g. hybrid propulsion systems comprising electric motors and internal combustion engines ; Control systems therefor, i.e. systems controlling two or more prime movers, or controlling one of these prime movers and any of the transmission, drive or drive units the prime-movers consisting of electric motors and internal combustion engines, e.g. HEVs characterised by apparatus, components or means specially adapted for HEVs
    • B60K6/28—Arrangement or mounting of plural diverse prime-movers for mutual or common propulsion, e.g. hybrid propulsion systems comprising electric motors and internal combustion engines ; Control systems therefor, i.e. systems controlling two or more prime movers, or controlling one of these prime movers and any of the transmission, drive or drive units the prime-movers consisting of electric motors and internal combustion engines, e.g. HEVs characterised by apparatus, components or means specially adapted for HEVs characterised by the electric energy storing means, e.g. batteries or capacitors
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/29—Geographical information databases
    • B—PERFORMING OPERATIONS; TRANSPORTING
    • B60—VEHICLES IN GENERAL
    • B60Y—INDEXING SCHEME RELATING TO ASPECTS CROSS-CUTTING VEHICLE TECHNOLOGY
    • B60Y2200/00—Type of vehicle
    • B60Y2200/90—Vehicles comprising electric prime movers
    • B60Y2200/92—Hybrid vehicles
    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
    • Y02T—CLIMATE CHANGE MITIGATION TECHNOLOGIES RELATED TO TRANSPORTATION
    • Y02T10/00—Road transport of goods or passengers
    • Y02T10/60—Other road transportation technologies with climate change mitigation effect
    • Y02T10/62—Hybrid vehicles
    • Y—GENERAL TAGGING OF NEW TECHNOLOGICAL DEVELOPMENTS; GENERAL TAGGING OF CROSS-SECTIONAL TECHNOLOGIES SPANNING OVER SEVERAL SECTIONS OF THE IPC; TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS
    • Y02—TECHNOLOGIES OR APPLICATIONS FOR MITIGATION OR ADAPTATION AGAINST CLIMATE CHANGE
    • Y02T—CLIMATE CHANGE MITIGATION TECHNOLOGIES RELATED TO TRANSPORTATION
    • Y02T10/00—Road transport of goods or passengers
    • Y02T10/60—Other road transportation technologies with climate change mitigation effect
    • Y02T10/70—Energy storage systems for electromobility, e.g. batteries

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Databases & Information Systems (AREA)
  • Library & Information Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Data Mining & Analysis (AREA)
  • Transportation (AREA)
  • Combustion & Propulsion (AREA)
  • Chemical & Material Sciences (AREA)
  • Mechanical Engineering (AREA)
  • Remote Sensing (AREA)
  • Processing Or Creating Images (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
  • Image Processing (AREA)
  • Image Generation (AREA)

Abstract

지도와 같은 전자 문서에 있어서, 실체 검색 시스템은, 원시 쿼드 트리(quad-tree) 및 실체 쿼드 트리의 평행 또는 대응하는 그리드(grid)를 통하여, 원시 데이터를 실체 데이터와 결합시킨다. 실체 쿼드 트리 내의 특정 그리드와 결합하는 원시 쿼드 트리 내의 그리드에는 키가 할당된다.
전자 문서, 지도, 실체, 검색, 쿼드 트리

Description

실체 검색 시스템{ENTITY LOOKUP SYSTEM}
도 1은 평행 쿼드 트리 배열을 통하여 실체 데이터와 결합한 원시 데이터를 포함하는 지도와 같은 전자 문서를 나타낸 도면.
도 2는 원시 데이터를 실체 데이터와 관련시키는 원시 쿼드 트리 및 관련된 실체 쿼드 트리를 나타낸 도면.
도 3은 평행 쿼드 트리 배열을 이용하여 원시 데이터를 실체 데이터와 결합시키는 컴퓨터 또는 컴퓨팅 장치의 블록도.
도 4는 원시 데이터 그룹을 특정 실체 쿼드 트리 그리드와 관련시키는 것을 나타낸 도면.
도 5는 원시 그리드와 실체 그리드의 결합 및 더 높은 상세 레벨을 나타낸 도면.
도 6은 원시 쿼드 트리 내의 원시 그리드를, 평행 또는 대응하는 실체 쿼드 트리 내의 실체 그리드와 결합시키는 것을 나타낸 흐름도.
도 7은 주소 하이퍼링크 특징을 포함한 전자 문서를 생성하는 응용 프로그램이 실행될 수도 있는 컴퓨터 또는 컴퓨팅 장치의 상세한 구현의 블록도.
<도면의 주요 부분에 대한 부호의 설명>
100 : 컴퓨팅 장치
105 : 화면(디스플레이)
110 : 키보드
115 : 지도
202 : 원시 쿼드 트리
204 : 실체 쿼드 트리
본 발명은, 원시 데이터를, 원시 데이터를 기술하는 실체 데이터와 결합시키는 것에 관한 것이다.
공간 데이터 또는 원시 데이터로 지칭될 수도 있는 프리미티브(primitivies)는, 선, 곡선, 및 다각형과 같은, 기본 요소로서, 서로 조합하여 더 복잡한 그래픽 화상을 생성할 수 있다. 사상 응용(mapping application)에 의해 생성된 지도와 같은 전자 문서 환경에서, 원시 데이터는 지도 상의 위치를 규정할 수도 있다. 원시 데이터는 2차원 공간 내의 X-Y 규약과 같은 데카르트 좌표계에 의해 기술될 수도 있다.
원시 데이터 그룹은 특정 형상을 구성할 수도 있다. 지도 환경에서, 특정 형상(즉, 원시 데이터 그룹)은 시, 군, 주 등을 규정할 수도 있다. 실체 데이터는 원시 데이터 또는 원시 데이터 그룹과 결합할 수도 있다. 상기와 같은 실체 데이터는, 특정 원시 데이터 또는 원시 데이터 그룹에 관한 상세(정보)를 기술하거나 제공할 수 있다. 예를 들어, 실체 데이터는, 원시 데이터 그룹에 의해 규정된 특정 지역의, 이름, 인구 통계, 및 인구 수를 포함할 수도 있다.
특정 예에서, 프리미티브 그룹은 특정 해상도로 미국의 형상을 표현할 수도 있다. 서로 다른 프리미티브 집합을 이용하여, 더 높은 해상도로 미국의 형상을 표현할 수도 있다. 각각의 프리미티브 집합은, 서로 다른 상세 레벨(level of detail)로 기억될 필요가 있다. 상기와 같은 상세 레벨은, 쿼드 트리 배열에 의해 표현될 수도 있고, 여기서, 주어진 레벨은 크기가 같은 4개의 그리드로 분할된 이전 레벨의 그리드이다. 그 레벨에 할당된 프리미티브는, 프리미티브 자신이 교차하는 사분면과 결합된다. 후속 상세 레벨에서, 각각의 사분면은, 크기는 같지만 더 작은 4개의 사분면으로 다시 분할되고, 각각은 좌표 공간의 더 작은 부분을 비례하여 차지한다. 상기 레벨에 할당된 더 높은 상세 레벨의 프리미티브는, 프리미티브 자신이 겹치는 사분면과 다시 결합된다. 쿼드 트리 내의 그리드 분할은 극소 정도의 상세 레벨로 계속 진행할 수 있다. 또한, 각각의 상세 레벨에서는, 더 높은 레벨에서 적절한 표현을 갖지 않는 새로운 특징이 소개될 수도 있다. 일 예로서, 최하위 상세 레벨은 단지 미국에 대한 프리미티브만을 포함할 수도 있다. 차위 상세 레벨로 높아지면, 미국과 각각의 주에 대한 프리미티브를 포함하게 된다. 차위 상세 레벨로 높아지면, 미국과 모든 주에 대한 더 높은 해상도의 프리미티브를 포함하여, 군 등을 표현하는 프리미티브를 소개하게 된다.
실체 데이터를 이용하여, 미국, 텍사스주, 애머릴로시, 및 애머릴로 내의 거리를 표현하는 원시 데이터 또는 원시 데이터 그룹을 기술하는 경우에는, 각각의 원시 데이터 그룹에 대해 별개의 입력(entry)이 이루어져야 한다. 즉, 미국을 표현하는 원시 데이터 그룹은 실체 데이터에 대한 그 자신 고유의 입력을 갖게 되고, 텍사스주를 표현하는 원시 데이터 그룹은 실체 데이터에 대한 그 자신 고유의 입력을 갖게 되고, 애머릴로시를 표현하는 원시 데이터 그룹은 그 자신 고유의 데이터를 갖게 되며, 애머릴로 내의 거리를 표현하는 원시 데이터 그룹은 실체 데이터에 대한 그 자신 고유의 입력을 갖게 된다.
많은 경우, 공간 지향 조회(spatially directed query)를 통하여 정보를 검색하는 것이 필요하다. 상기와 같은 조회의 일 예는, 모든 프리미티브 및 주어진 좌표 공간의 일정 부분 집합과 교차하는 결합된 실체 데이터를 복귀시키는 것이다. 상기 조회를 만족시키는데 필요한 데이터를 검색하는데 최소량의 정보를 스캔하도록, 실체 데이터를 기억하는 것이 바람직하다. 또한, 검색 시간을 최소화하기 위해, 기억 매체 상의 물리적으로 가까운 위치에서 함께 검색될 수 있도록, 실체 데이터를 기억하는 것이 바람직하다.
상술한 바와 같이, 쿼드 트리 배열 내에 원시 데이터의 다수의 상세 레벨을 기억하는 경우에는, 원시 데이터 또는 원시 데이터 그룹과 결합하는 실체 데이터를 위한 적당한 기억 위치 및 참조 시스템을 결정하는 것이 필요할 수도 있다. 첫 번째 접근법은, 키를 이용하여 원시 데이터(즉, 원시 데이터 그룹)와 결합한 관계 테이블 내에 실체 데이터를 기억하는 것이다. 상술한 두 번째 접근법은, 원시 데이터(즉, 원시 데이터 그룹)의 각 결합을 이용하여 실체 데이터를 복제하는 것이다. 첫 번째 접근법은, 실체 데이터에 접근하는 경우 기억장치 집약성을 잃는 결점이 있으나, 두 번째 접근법은 실체 데이터의 낭비적인 복제를 필요로 한다.
지도와 같은 전자 문서에 있어서, 실체 검색 시스템은, 전자 문서 내에서 형상을 규정한 원시 데이터를 포위하는 그리드를 포함한 원시 쿼드 트리를 포함한다. 실체 검색 시스템은 원시 쿼드 트리 내의 그리드에 대응하는 그리드를 포함하고, 원시 쿼드 트리 내의 그리드와 실체 쿼드 트리 내의 그리드에 관한 결합이 이루어진다. 실체 쿼드 트리 내의 그리드는, 원시 쿼드 트리 내의 그리드에 의해 포위되는 원시 데이터에 관한 정보를 제공한다. 실체 검색 시스템을 이용하여, 2개의 쿼드 트리 간에서 탐색한다.
첨부된 도면을 참조하여, 상세한 설명을 설명한다. 도면에서, 참조 부호 중 맨 왼쪽 숫자(들)은, 그 참조 부호가 처음 나타나는 도면을 식별한다. 상이한 도면에서 동일한 참조 부호의 사용은 유사하거나 동일한 부분을 표시한다.
다음 개시 내용은, 원시 데이터 또는 원시 데이터 그룹이, 평행 쿼드 트리 배열을 통하여, 원시 데이터 또는 원시 데이터 그룹을 기술하는 실체 데이터와 결합하는 기술을 설명한다.
도 1은, 평행 쿼드 트리 배열을 통하여 실체 데이터와 결합하는 원시 데이터를 포함한 지도를 나타낸다. 컴퓨터 또는 컴퓨팅 장치(100)는, 화면(105)을 포함하고, 키보드(110)와 같은 입력 장치에 접속되거나 키보드(110)와 같은 입력 장치를 포함한다. 전자 문서는 디스플레이(105)를 통하여 컴퓨팅 장치(100) 상에 표시 된다. 본 예에서, 표시된 전자 문서는, 미국의 지도(115)이다. 컴퓨팅 장치(100)는, 데스크탑 PC(personal computer), 랩탑 PC, 태블릿 PC, PDA(personal digital assistant), 또는 스마트나 피쳐폰과 같은 여러 장치 중 하나일 수도 있다.
지도(115)는, 선, 점, 다각형 등과 같은 형상을 표현하는 프리미티브 또는 원시 데이터로도 알려진 공간 데이터로 이루어진다. 본 예에서, 원시 데이터 그룹은 미국을 규정하는 지도(115)를 구성한다. 또한, 지도(115)를 구성하는 원시 데이터 그룹의 부분 집합은, 미국 내의 주, 시, 거리 등을 규정할 수도 있다.
지도(115)는, 4개의 그리드로 분할될 수도 있는 공간의 일부이다. 4개의 그리드 각각은 4개의 그리드로 더 분할될 수도 있다. 이와 같은 그리드 분할은 더 계속될 수도 있다. 상기와 같은 그리드 분할 또는 배열을 쿼드 트리로 지칭하고, 아래에서 더 상세히 설명한다. 생성된 원시 쿼드 트리 내에 있는 각각의 특정 그리드는, 특정 원시 데이터 그룹을 포함한다. 원시 쿼드 트리 내에 있는 각각의 그리드에는, 상기 그리드를 원시 쿼드 트리 내의 다른 그리드와 구별하는 고유 번호 또는 표시가 주어진다.
실체 데이터는 원시 데이터 그룹에 관한 기술 또는 정보를 제공한다. 상기 기술 또는 정보는, 텍사스주를 표현하는 원시 데이터 그룹에 관하여, "텍사스"와 같은 원시 데이터 그룹과 결합한 이름을 포함할 수도 있다. 또한, 실체 데이터는, 특정 원시 데이터 그룹과 결합할 수도 있는, 인구 통계, 관광 명소, 역사 정보 등과 같은 어느 다른 데이터를 포함할 수도 있다.
실체 데이터에 대한 쿼드 트리는, 원시 데이터를 기술하는 쿼드 트리 배열과 평행하게 생성된다. 원시 데이터 그룹을 표현하는 각각의 원시 쿼드 트리 그리드의 경우, 평행 그리드는 실체 쿼드 트리 내에 표현된다. 실체 쿼드 트리 내의 평행 그리드는, 원시 쿼드 트리 내의 그리드와 일치하는 표시 또는 번호를 가질 수도 있다. 실체 쿼드 트리 내의 평행 그리드는, 실체 데이터가 기억될 수도 있는 기억 위치를 표현한다.
원시 쿼드 트리 내의 각 그리드 내에 있는 각각의 프리미티브는 키와 결합된다. 상기와 같은 키를 이용하여, 원시 데이터 그룹을 표현하는 특정 그리드를, 실체 쿼드 트리 내의 특정 그리드와 결합하고, 각각의 프리미티브와 결합한 실체 쿼드 트리 내에 특정 실체 데이터를 배치한다. 이와 같은 배열은, 아래에서 더 상세히 설명된다.
도 2는 원시 쿼드 트리 및 실체 쿼드 트리를 도시한다. 더욱 상세하게는, 실체 검색 시스템(200)은, 평행 원시 쿼드 트리(202) 및 실체 쿼드 트리(204)를 포함하고, 원시 쿼드 트리(202) 및 실체 쿼드 트리(204) 내에 대응하는 그리드가 존재한다.
원시 쿼드 트리(202)는, 선, 점, 다각형 등과 같은 형상을 표현한 원시 데이터가 존재하는 기하 공간을 표현한다. 사상 응용에 의해 생성된 지도(예를 들어, 지도(115))와 같은 전자 문서 환경에서, 상기와 같은 원시 데이터는, 국가, 주, 군, 시, 거리 등과 같은 지리적 위치를 표현할 수도 있다.
실체 쿼드 트리(204)는 원시 쿼드 트리(202)와 평행 또는 대응하는 쿼드 트리이다. 즉, 실체 쿼드 트리(204)에서 표현된 그리드는, 원시 쿼드 트리(202) 내 에 평행 또는 대응하는 그리드를 갖는다. 본 예에서, 실체 쿼드 트리(204) 내의 그리드는, 원시 쿼드 트리(202) 내의 그리드와 같이, 대응하는 표시 또는 번호를 갖는다. 실체 쿼드 트리(204)는, 특정 원시 데이터 또는 원시 데이터 그룹의 상세를 기술하거나 제공하는 데이터가 기억되는 기억장치나 메모리 내의 영역을 표현한다.
원시 쿼드 트리(202) 내의 기하 공간 및 실체 쿼드 트리(204) 내의 기억 영역을 기술하는 여러 상세 레벨을 제공할 수도 있다. 본 예에서, 최상위 상세 레벨은 "상세 레벨 0(206)"으로 표현되고, 차위 상세 레벨은 "상세 레벨 1(208)"로 표현되며, 최고 상세 레벨은 "상세 레벨 2(210)"로 표현된다. "상세 레벨 2(210)"를 넘어 더 높은 상세 레벨을 제공할 수도 있다.
실체 검색 시스템(200)은, 더 높은 상세 레벨의 그리드가 4개의 그리드로 분할되는 것을 제공한다. 본 예에서, 원시 쿼드 트리(202)의 경우, "상세 레벨 0(206)"은 공간(212)에 의해 표현된다. 원시 쿼드 트리(202)의 "상세 레벨 1(208)"은, 공간(212)을 4개의 그리드로 나누거나 분할하는 공간(214)에 의해 표현된다. 원시 쿼드 트리(202)의 "상세 레벨 2(210)"는, 공간(214)을 16개의 그리드로 더 나누거나 분할하는 공간(216)에 의해 표현된다. 이와 마찬가지로, 실체 쿼드 트리(204)의 경우, "상세 레벨 0(206)"은 공간(218)에 의해 표현된다. 실체 쿼드 트리(204)의 "상세 레벨 1(208)"은, 공간(218)을 4개의 그리드로 나누거나 분할하는 공간(220)에 의해 표현된다. 실체 쿼드 트리(204)의 "상세 레벨 2(210)"는, 공간(220)을 16개의 그리드로 더 나누거나 분할하는 공간(222)에 의해 표현된다.
실체 검색 시스템(200)에 의해 형성된 배열에서는, 원시 쿼드 트리(202) 및 실체 쿼드 트리(204)에 의해 평행 또는 대응하는 그리드가 제공된다. 예를 들어, "상세 레벨 0(206)"에서, 원시 쿼드 트리(202)의 "그리드 1(224)"은, 실체 쿼드 트리(204)의 "그리드 1(226)"에 대응한다(즉, 상기 그리드는 "그리드 1"인 동일 표시 또는 번호에 의해 식별된다). "상세 레벨 1(208)"에서, 공간(214)은 "그리드 2(228)", "그리드 3(230)", "그리드 4(232)", 및 "그리드 5(234)"를 포함한다. 공간(220)은 "그리드 2(236)", "그리드 3(238)", "그리드 4(240)", 및 "그리드 5(242)"를 포함한다. 또한, "상세 레벨 1(208)"의 경우, "그리드 2(228)"는 "그리드 2(236)"와 대응하고, "그리드 3(230)"은 "그리드 3(238)"과 대응하고, "그리드 4(232)"는 "그리드 4(240)"와 대응하며, "그리드 5(234)"는 "그리드 5(242)"와 대응한다.
"상세 레벨 2(210)"에서, 원시 쿼드 트리(202)의 공간(216)은 그리드(244 내지 274)를 포함하고, 실체 쿼드 트리(204)의 공간(222)은 그리드(276 내지 298)를 포함한다. 원시 쿼드 트리(202)의 공간(216) 내에 있는 그리드는, 실체 쿼드 트리(204)의 공간(222) 내에 대응하는 그리드를 갖는다.
도 3은 컴퓨팅 장치 또는 컴퓨터(100)를 더 상세히 도시한다. 컴퓨터(100)는, 데스크탑 PC(personal computer), 랩탑 PC, 태블릿 PC, PDA(personal digital assistant), 또는 스마트나 피쳐폰과 같은 여러 장치 중 하나일 수도 있다. 예시적인 컴퓨터(100) 구조는, 도 7을 참조하여 아래에서 더 상세히 설명된다.
컴퓨터(100)는, CPU(central processing unit) 또는 프로세서(300) 및 메모 리(305)를 포함한다. 프로세서(300)는, 시스템 버스(도시안함)를 통하여 메모리(305)에 접근한다. 메모리(305)는, 도 1에서 설명된 전자 문서 또는 지도(115)를 생성하는 응용 프로그램(310)을 포함한다.
전자 문서 또는 지도를 규정하는 원시 데이터는, 원시 데이터 기억장치(315)에 기억된다. 특히, 원시 데이터는, 상술한 원시 쿼드 트리의 형태로 기억되어 구조화된다. 또한, 아래에서 더 상세히 설명되는 바와 같이, 원시 데이터 기억장치(315)는, 각각의 원시 데이터 그룹 또는 원시 쿼드 트리 그리드와 결합하는 키를 기억한다. 상기와 같은 키를 이용하여, 실체 데이터에 대한 기억 위치를 표현하는 실체 쿼드 트리 내의 특정 그리드와 관련시킨다. 원시 데이터 그룹과 관련되거나 결합하는 상기 실체 데이터(즉, 원시 데이터 그룹과 결합하는 그리드)는, 실체 데이터 기억장치(320)에 기억된다. 특히, 실체 데이터는, 상술한 실체 쿼드 트리의 형태로 구조화되어 참조된다.
입출력 구성 요소(325)는, 컴퓨팅 장치(100) 내에 포함된다. 입출력 구성 요소(325)는, 사용자가, 실체 데이터 기억장치(320)에 기억된 실체 데이터와 같은 데이터에 접근하는 것을 허용한다. 특정 예로서, 사용자가, 지도(예를 들어, 지도(115)) 상의 한 점을 고르거나 선택하면, 선택된 점과 관련되는 실체 데이터가 제공된다.
도 4는, 원시 데이터 그룹과 실체 데이터 그리드 또는 위치의 예시적인 관계를 도시한다. 본 예에서, 원시 데이터 그룹(400)은 "상세 레벨 1(208)"로 텍사스주를 규정한다. 상이한 프리미티브 집합(405)은, "상세 레벨 2(210)"에서 텍사스 주를 규정한다. 그리드(410)는 원시 데이터 그룹(405)의 일부를 포함한다; 그러나, 그리드(410)가 원시 데이터 그룹(405)을 완전히 포위하지는 않는다.
공간(216)은, 원시 데이터 그룹(405)을 더 널리 포위하는 그리드를 제공한다. 따라서, 원시 쿼드 트리 그리드(410)를, 원시 데이터 그룹(405)을 기술하는 실체 쿼드 트리 그리드와 관련시킴에 있어서, 그리드(410)가 상주하는 "상세 레벨 2(210)"로부터, 원시 데이터 그룹(405)을 더 널리 포위하는 "상세 레벨 1(208)"까지의, 상세 레벨에 관한 델타가 결정된다. 상세 레벨의 델타는 상세 레벨 델타(415)에 의해 표현되고, 상기와 같은 델타는 "1"의 값을 갖는다. 다른 경우에는, 상세 레벨 델타가 "1"보다 큰 값일 수도 있다.
본 예에서는, 프리미티브 그룹(405)을 공간(216) 내의 하나 이상의 그리드에 의해 규정하지만, 차위 상세 레벨(즉, "상세 레벨 0(206)")로 올라가는 대신, "상세 레벨 1(208)"에서는 실체 그리드 결합을 수행하고, "상세 레벨 0(206)"에서는 실체 그리드 결합을 수행하지 않는다. 상기와 같은 시스템을 엄격히 따른다면, 어느 주어진 원시 그리드와 결합한 실체 그리드는, 그리드 자신, 또는 주어진 원시 그리드의 부모(parent) 그리드 중 하나와 동일한 범위로 된다. 이와 같이, 실체 데이터는 실체 그리드(420, 425, 430)에 기억된다. 모든 상세 레벨에서 모든 원시 표현들을 완전히 포위하는 최소 원시 그리드는 그리드(435)이다. 따라서, 실체 데이터는 실체 그리드(430)에 기억된다. 이는, 그리드 간의 분할선과 교차하는 프리미티브가 비교적 작은 경우에, 바람직하지 않은 결과를 갖게 된다. 상기 분할선이 첫 번째 상세 레벨의 분할선이었던 경우, 최소 포위 그리드는 "상세 레벨 0(206)" 에 있는 그리드로 된다. 이로 인해, 상기 레벨에서는, 너무 많은 실체 데이터가 기억되게 된다. 이와 같은 문제를 해결하기 위해, 주어진 원시 그리드와 결합하는 실체 그리드가 직계 부모 그리드의 형제(sibling) 그리드로 되는 것을 허용하는 준비가 이루어진다. 상기 예에서, 원시 그리드(410)의 직계 부모는, 실체 그리드(425)와 정상으로 결합하는 원시 그리드(440)이다. 각각의 프리미티브를 갖는 키는, 실체 데이터가 그리드(425)에 기억되는 것이 아니라 그리드(450)에 기억된다는 것을 표시하는 방향 플래그(445)를 포함한다. 이와 같은 방향 플래그는 "팬 값(fan value)"으로 지칭되고, 5개의 가능한 값을 갖는다: "북쪽, 남쪽, 서쪽, 동쪽, 또는 어느 방향도 아님(North, South, West, East, or None)". 본 예에서, 공간(220)의 그리드(410) 내에 있는 텍사스주(405)를 표현하는 프리미티브는, 오프셋 값(415)이 1인 키를 갖고, "서쪽"인 방향 플래그 또는 팬 값(445)을 갖게 된다. 이와 같은 준비가 없다면, 실체 데이터는 실체 그리드(430)에서, "상세 레벨 0(206)"으로 기억되게 된다. 이는, 데이터를 덜 균등하게 분산하는 결과를 갖고, 공간 지향 검색에 덜 효율적이므로, 바람직하지 않다.
본 예에서, 공간(216)의 그리드(440)는, 원시 데이터 그룹(400)의 부분 집합이다. 상기 그리드 내에 있는 프리미티브에 대한 키는, 0인 오프셋(실체 데이터가 동일 레벨에서 기억되는 것을 표시)을 갖고, 실체 데이터가 그리드(425) 대신 공간(218)의 그리드(450)에 기억되는 것을 표시하는, 왼쪽을 향하는 방향 플래그를 갖게 된다. 공간(216)의 그리드(455)에 기억된 프리미티브는, 0인 같은 레벨의 오프셋을 갖는 키를 포함하나, 방향 플래그를 포함하지는 않는다. 본 예에서는, 그리 드가 직사각형 또는 정사각형이므로, 팬 값은 "북쪽, 남쪽, 서쪽, 동쪽, 또는 어느 방향도 아님"일 수도 있다. 또한, 상기 시스템은 어느 다른 일정한 이음새없는(tileable) 그리드 시스템에도 적용된다. 다른 예의 그리드는, 특정 형상으로 서로 망형 구조를 이루는 육각형 또는 형상들을 포함할 수 있다.
그리드(450) 내의 실체 데이터는 "텍사스(460)"이다. 이 경우, "텍사스"는 원시 데이터 그룹(400)의 기술을 설명하거나 제공한다. 더욱 상세하게는, 그리드(450)는, 실체 데이터를 기억하는 장치의 메모리 내의 위치와 결합한다. 이 경우, 실체 데이터는 "텍사스"란 이름을 갖는다; 그러나, 상술한 바와 같이, 지리적 위치와 결합한 이름을 제외한 다른 실체 데이터와 같은 다른 정보 또는 기술을 제공할 수도 있다. 이는, 객체를 표현하는 모든 프리미티브에 동등하게 적용되는 어느 비공간적인 속성도 포함하게 된다.
본 예에서, (원시 데이터 그룹(405)의 부분 집합을 포함하는)그리드(410)에 대한 실체 기술은 실체 그리드(450)와 결합한다. 실체 쿼드 트리 그리드(450)에 도달하기 위해, 원시 쿼드 트리 그리드(410)와 키가 결합하고, 상기 키는, (상세 레벨 델타(415)에 의해 표현된 것과 같이)상세 레벨 델타 "1"을 갖고, 실체 쿼드 트리 그리드(425)로부터 실체 데이터 또는 기술을 포함하는 실체 쿼드 트리 그리드(450)로 이동하는, "서쪽"의 팬 값을 갖는다. 다른 경우, 키는 원시 쿼드 트리(202) 및 실체 쿼드 트리(204) 내의 그리드에 할당된 표시 또는 번호를 포함할 수도 있다.
또한, 다른 원시 쿼드 트리 그리드는 실체 쿼드 트리 그리드(450)와 결합할 수도 있다. 예를 들어, 원시 쿼드 트리 그리드(465)는, 상세 레벨 "1", 및 "서쪽"의 팬 값을 갖는 키(원시 쿼드 트리 그리드(410)와 동일한 키)를 갖게 된다. 원시 쿼드 트리 그리드(470)는, 상세 레벨 "1", 및 "어느 방향도 아님"의 팬 값으로 이루어진 키를 갖게 된다. 원시 쿼드 트리 그리드(475)는 원시 쿼드 트리 그리드(470)와 동일한 키를 갖게 된다. 실체 쿼드 트리 그리드(450)가 원시 쿼드 트리 그리드(455)에 대응하는 그리드이므로, 원시 쿼드 트리 그리드(475)는, 상세 레벨 값 "0" 및 "어느 방향도 아님"의 팬 값으로 이루어진 키를 갖게 된다.
도 5는, 더 높은 상세 레벨에서의 원시 그리드 및 실체 그리드 관계를 도시한다. 본 예에서, 원시 데이터 그룹(400)의 부분 집합은 원시 쿼드 트리(202)의 공간(220)의 그리드(500) 내에 상주한다. 그리드(500)는 그리드(510)를 포함하는 4개의 그리드로 분할된다.
애머릴로시를 표현하는 원시 데이터 그룹(505)은, 그리드(510) 내에 상주한다. 그리드(510)는, 4개의 그리드로 더 분할될 수도 있고, 그리드(510)는 그리드(515)를 포함한다. 원시 쿼드 트리(202)의 그리드(515)는, 애머릴로시를 표현하는 원시 데이터 그룹을 완전히 포위한다. 실체 쿼드 트리(204) 내의 대응하는 그리드는, 그리드(515)와 결합할 수도 있다. 애머릴로시에 관한 기술적인 데이터 또는 정보(즉, 애머릴로시를 표현하는 프리미티브 그룹(505))는, 실체 쿼드 트리(204) 내의 대응하는 그리드에 의해 기억 메모리에서 참조될 수도 있다. 이 경우, 그리드(515) 및 프리미티브 그룹(505)을, 실체 쿼드 트리(204) 내의 그리드와 관련시키는 키는, 상세 레벨 델타 "0" 및 "어느 방향도 아님"의 팬 값을 갖는다. 원시 쿼 드 트리 그리드(515) 및 이와 대응하는 실체 쿼드 트리(204) 내의 그리드 간에는, 직접적인 관계가 존재한다.
상술한 할당 시스템은 여러 이점을 갖는다. 물론, 이로 인해, 유사한 중요도, 크기, 및 공간 위치의 특징들에 관한 실체 데이터를 공통 기억 영역 내에 그룹화하게 된다. 이는, 다수의 공간 지향 조회를 하는데 매우 바람직하다. 공간적인 조회를 통하여 접근될 수 있는 특징들을 기억 매체 상에 순차적으로 기억하여, 검색 시간 속도를 빠르게 할 수 있다. 또한, 단일의 원시 그리드에서 참조할 수 있는 실체 데이터에 대한 기억 위치의 후보 집합이 매우 제한된다.
도 6은, 원시 쿼드 트리 내의 원시 그리드를, 평행 또는 대응하는 실체 쿼드 트리 내의 실체 그리드와 결합시키는 프로세스(600)를 도시한다. 상기 프로세스(600)는, 하드웨어, 소프트웨어, 펌웨어, 또는 그 조합으로 구현될 수 있는 동작 순서를 표현하는, 논리 흐름도 내의 블록 집합으로서 설명된다. 소프트웨어 환경에서, 상기 블록은, 하나 이상의 프로세서에 의한 실행시, 반복된 동작을 수행하는, 컴퓨터 명령을 표현한다. 상기 프로세스(600)는, 상술 및 후술하는 컴퓨팅 장치(100)를 참조하여 설명되고, 원시 데이터를 포함하는 지도와 같은 전자 문서를 생성하는 응용 프로그램을 구현한다. 흐름도로서 설명하지만, 일정 프로세스가 동시에 일어날 수도 있음을 알 수 있다.
블록(605)에서는, 원시 쿼드 트리 내의 특정 그리드가 식별된다. 상기 그리드는, 특정 형상을 규정하는 원시 데이터 그룹을 포함할 수도 있다. 지도 환경에서, 원시 데이터 그룹은, 국가, 주, 군, 시, 거리 등과 같은 지리적 위치를 표현할 수도 있다.
소정의 경우, 원시 쿼드 트리 내의 식별된 그리드는, 특정 형상을 규정하거나 지리적 위치를 표현하는 전체 원시 데이터 그룹을 포위하거나 포함한다(즉, 블록(610)의 "예" 갈림(branch) 다음).
블록(615)에서, 식별된 그리드가 전체 원시 데이터 그룹을 포위하거나 포함하는 경우, 평행 실체 쿼드 트리 내의 대응하는 그리드에 관한 결합이 이루어진다. 대응하는 그리드는, 원시 쿼드 트리 내의 식별된 그리드와 같이, 자신에게 할당된 동일한 표시 또는 번호를 갖는다.
다른 경우, 원시 쿼드 트리 내의 식별된 그리드는, 특정 형상을 규정하거나 지리적 위치를 표현하는 전체 원시 데이터 그룹을 포위하거나 포함하지 않는다(즉, 블록(610)의 "아니오" 갈림 다음).
특정한 경우, 원시 쿼드 트리 내의 식별된 그리드는, 원시 쿼드 트리 내의 다른 그리드와 함께, 원시 데이터 그룹을 포위하거나 포함하는 그리드 쌍을 구성한다(즉, 블록(620)의 "예" 갈림 다음). 블록(625)에서는, 원시 쿼드 트리 내의 식별된 그리드와 결합하는 팬 값에 관한 결정이 이루어진다. 팬 값은, 원시 쿼드 트리 내의 식별된 그리드와 관련된, 기술을 포함하거나 정보를 제공하는 실체 쿼드 트리 내의 특정 그리드에 도달하는데 이용되는 키의 일부일 수도 있다.
소정의 경우, 한 쌍으로서 다른 그리드와 결합하는 식별된 그리드는, 원시 데이터 그룹을 포위하거나 포함하지 않는다(즉, 블록(620)의 "아니오" 갈림 다음). 블록(630)에서는, 원시 쿼드 트리에서 하위 상세 레벨에 있는 그리드를 식별한다. 쿼드 트리 배열에서, 상기와 같은 그리드는, 이전에 식별된 그리드의 부모로 판단된다. 상기 하위 상세 레벨 그리드는, 쿼드 트리 배열 내에 있는, 이전에 식별된 그리드 및 3개의 다른 자손 그리드를 포함한다. 그리드 또는 그리드 쌍이 원시 데이터 그룹을 포함하거나 포위할 때까지, 하위 상세 레벨 그리드로 이동하는 반복이 일어날 수도 있다. 상술한 키는, 초기에 식별된 그리드로부터, 하위 상세 레벨 그리드 및 임의의 후속 또는 중간 부모 그리드까지, 상세 레벨에서의 증분(increment)을 포함할 수도 있다. 즉, 상기 키는, 초기에 식별된 그리드로부터, 원시 데이터 그룹을 포함하거나 포위하는 그리드 또는 그리드 쌍까지, 다수의 상세 레벨 값을 포함하게 된다.
컴퓨팅 장치
도 7은 컴퓨팅 장치 또는 컴퓨터(100)의 예시적인 구현을 더 상세히 도시한다. 더욱 상세하게는, 컴퓨터(100) 상에, 응용 프로그램이 구현될 수도 있고, 상술한 원시 데이터 및 실체 데이터 관계를 지원할 수도 있다. 컴퓨터(100)는, Window
Figure 112006001278547-PAT00001
상표 운영 체계로 구성될 수도 있다. 컴퓨터(100)는, 상술한 처리 장치 또는 프로세서(300), 역시 상술한 시스템 메모리 또는 메모리(305), 및 메모리(305)를 처리 장치 또는 프로세서(300)에 상호 접속하는 것을 포함하여, 여러 구성 요소를 상호 접속하는 시스템 버스(715)를 포함한다. 시스템 버스(715)는, 메모리 버스 또는 메모리 제어기, 주변 장치 버스, 및 로컬 버스를 포함하는, 여러 버스 구조 중 어느 하나의 버스 구조를 이용하여, 여러 버스 구조 중 어느 하나의 버스 구조로서 구현될 수도 있다.
메모리(305)는, ROM(720; read only memory) 및 RAM(725; random access memory)을 포함한다. BIOS(730; basic input/ouput system)는, ROM(720)에 기억된다.
컴퓨터(100)는 다음 드라이브 중 하나 이상을 갖는다: 하드 디스크 또는 하드 디스크 배열로부터 판독하고 이에 기입하기 위한 하드 디스크(730), 탈착 가능 자기 디스크(740)로부터 판독하고 이에 기입하기 위한 자기 디스크 드라이브(735), 및 CD ROM 또는 다른 광 매체 등의 탈착 가능 광 디스크(750)로부터 판독하고 이에 기입하기 위한 광 디스크 드라이브(745). 하드 디스크 드라이브(730), 자기 디스크 드라이브(735), 및 광 디스크 드라이브(745)는, 각각, 하드 디스크 드라이브 인터페이스(760), 자기 디스크 드라이브 인터페이스(765), 및 광 드라이브 인터페이스(770)에 의해 시스템 버스(715)에 접속된다. 상기 드라이브 및 이와 관련된 컴퓨터 판독 가능 매체는, 컴퓨터(100)를 위해, 컴퓨터 판독 명령, 데이터 구조, 프로그램 모듈 및 다른 데이터의 비휘발성 기억장치를 제공한다.
하드 디스크(730), 탈착 가능 자기 디스크(740), 및 탈착 가능 광 디스크(750)를 설명하지만, 다른 타입의 컴퓨터 판독 가능 매체를 이용하여, 데이터를 기억할 수 있다. 상기와 같은 다른 매체는, 자기 카세트, 플래시 메모리 카드, 디지털 비디오 디스크, 베르누이 카트리지, RAMs(random access memories), ROMs(read only memories) 등을 포함한다. 또한, 컴퓨터(100)는, 특히 단말기 서버로서 구현되는 경우, RAID(redundant array of independent disks) 기억장치 시스템과 같은, 자립형 시스템 상에 기억된 데이터를 처리하도록 구성될 수도 있다.
다수의 프로그램 모듈은, 하드 디스크(730), 자기 디스크(740), 광 디스크(750), ROM(720), 또는 RAM(725) 상에 기억될 수도 있다. 상기 프로그램은, 서버 운영 체계(775), 하나 이상의 응용 프로그램(310), 다른 프로그램 모듈(782), 및 프로그램 데이터(784)를 포함한다.
사용자는, 키보드(110) 및 마우스(788)와 같은 입력 장치를 통하여 컴퓨터(100)에 명령 및 정보를 입력할 수도 있다. 다른 입력 장치(도시안함)는, 마이크, 조이스틱, 게임 패드, 위성 방송 수신용 안테나, 스캐너 등을 포함할 수도 있다. 이들 및 다른 입력 장치는, 시스템 버스(715)에 연결되는 직렬 포트 인터페이스(790)를 통하여 처리 장치(300)에 접속되나, 다른 방법으로는, 병렬 포트, 게임 포트, USB(universal serial bus)와 같은, 다른 인터페이스에 의해 접속될 수도 있다.
또한, 모니터나 화면(105), 또는 다른 타입의 디스플레이는, 비디오 어댑터 카드(794)와 같은, 인터페이스를 통하여 시스템 버스(715)에 접속된다. 컴퓨터(100)는, 인터넷 접속과 같은, 네트워크(799) 상의 통신을 확립하기 위해, 네트워크 인터페이스나 어댑터(796), 모뎀(798) 또는 다른 수단을 갖는다. 또한, 모뎀(798)은 프로토콜 디코더 장치와의 접속을 용이하게 할 수도 있다. 또한, 화면(105)과, 키보드(110) 및 마우스(788)와 같은 입력 장치는, 각각, 비디오 어댑터 카드(794)와, 직렬 포트 인터페이스(790)를 통하여, 시스템 버스(715)에 접속된다.
본 발명에 따른 실체 검색 시스템은, 지도와 같은 전자 문서에 있어서, 원시 쿼드 트리 및 실체 쿼드 트리의 평행 또는 대응하는 그리드를 통하여 원시 데이터를 실체 데이터와 결합시키는 효과가 있다.
상술한 응용 및 전자 문서는, 평행 쿼드 트리를 이용하여, 원시 데이터를 실체 데이터와 결합시키는 것을 설명한다. 구조적인 특징 및/또는 방법론적인 작용에 특정한 언어로 본 발명을 설명하였지만, 설명된 특정한 특징 또는 작용에, 첨부된 청구항에서 규정되는 본 발명이 반드시 한정되는 것은 아님을 알 수 있다. 오히려, 특정한 특징 및 작용은, 청구된 본 발명을 구현하는 예시적인 형태로서 개시될 뿐이다.

Claims (20)

  1. 원시 데이터를 포위하는 그리드로 이루어진 원시 쿼드 트리(primitive quad-tree); 및
    상기 원시 쿼드 트리의 그리드와 실체 데이터(entity data)를 결합시키는, 대응하는 그리드로 이루어진 실체 쿼드 트리를 구비하는 것을 특징으로 하는 실체 검색 시스템.
  2. 제1항에 있어서,
    상기 원시 데이터는, 전자 문서 내에 형상들을 규정하기 위해 그룹화되는 것을 특징으로 하는 실체 검색 시스템.
  3. 제1항에 있어서,
    상기 원시 쿼드 트리의 그리드는, 전자 문서 내에 특정 형상을 포위하도록 그룹화되어, 상기 실체 쿼드 트리 내의 특정 그리드가, 특정 형상에 관한 실체 데이터를 제공하고, 함께 그룹화되는 원시 쿼드 트리의 그리드와 결합하는 것을 특징으로 하는 실체 검색 시스템.
  4. 제1항에 있어서,
    상기 원시 쿼드 트리 내의 그리드 쌍은, 형상을 규정하는 원시 데이터를 포 위하고, 실체 쿼드 트리 내의 특정 그리드와 결합하는 것을 특징으로 하는 실체 검색 시스템.
  5. 제1항에 있어서,
    상기 원시 쿼드 트리 내의 각각의 그리드에 키를 할당하여, 상기 원시 쿼드 트리 내의 그리드를, 실체 쿼드 트리 내의 그리드와 결합시키는 것을 특징으로 하는 실체 검색 시스템.
  6. 제5항에 있어서,
    상기 키는, 특정 형상을 규정한 원시 데이터를 포위하는 그리드 쌍의 일부인 원시 쿼드 트리 내의 그리드에 관한 팬 값을 포함하는 것을 특징으로 하는 실체 검색 시스템.
  7. 제5항에 있어서,
    상기 키는, 상기 원시 쿼드 트리 내의 그리드의 그리드 레벨과, 원시 쿼드 트리 내의 그리드에 대한 실체 데이터를 제공하는 실체 쿼드 트리 내의 그리드의 그리드 레벨 간의 차이를 규정하는 상세 레벨 값을 포함하는 것을 특징으로 하는 실체 검색 시스템.
  8. 제5항에 있어서,
    상기 키는, 상기 원시 쿼드 트리 내의 그리드와, 상기 원시 쿼드 트리 내의 그리드에 대한 실체 데이터를 제공하는 실체 쿼드 트리 내의 그리드 사이의 그리드 표시 값 간의 차이를 규정하는 표시 값을 포함하는 것을 특징으로 하는 실체 검색 시스템.
  9. 원시 쿼드 트리 내에 있는 원시 데이터의 그리드를 식별하는 단계;
    상기 원시 데이터의 그리드가, 특정 형상을 규정하는 원시 데이터 그룹을 포위하는지 여부를 결정하는 단계; 및
    상기 원시 데이터의 그리드를, 상기 원시 쿼드 트리와 평행한 실체 쿼드 트리 내의 그리드와 결합시키는 단계를 포함하는 것을 특징으로 하는 방법.
  10. 제9항에 있어서,
    상기 원시 데이터는 지도 상의 지리적 위치를 표현하는 것을 특징으로 하는 방법.
  11. 제9항에 있어서,
    상기 원시 데이터의 그리드는, 원시 데이터 그룹을 포위하는 한 쌍의 그리드 중 하나인 것을 특징으로 하는 방법.
  12. 제11항에 있어서,
    상기 원시 데이터의 그리드에 팬 값이 할당되고,
    상기 팬 값은, 원시 데이터의 그리드를, 실체 쿼드 트리 내의 그리드와 결합시키는 단계를 더 규정하는 것을 특징으로 하는 방법.
  13. 제9항에 있어서,
    상기 결합시키는 단계는, 원시 데이터의 그리드에 키를 할당함으로써 수행되고,
    상기 키는, 원시 데이터의 그리드와, 실체 쿼드 트리 내의 그리드 간의 그리드 레벨에서의 차이를 규정하는 상세 레벨 값을 포함하는 것을 특징으로 하는 방법.
  14. 제9항에 있어서,
    상기 결합시키는 단계는, 원시 데이터의 그리드에 키를 할당함으로써 수행되고,
    상기 키는, 원시 데이터의 그리드와 실체 쿼드 트리 내의 그리드의 그리드 표시 값 간의 차이를 규정하는 표시 값을 포함하는 것을 특징으로 하는 방법.
  15. 제9항에 있어서,
    상기 결합시키는 단계에서, 실체 쿼드 트리 내의 그리드는, 원시 데이터의 그리드에 관한 기술적인 정보를 제공하는 것을 특징으로 하는 방법.
  16. 컴퓨터 상에서 이용하기 위한 기억 매체로서, 상기 컴퓨터 상에서 실행시,
    전자 문서 내의 형상들을 표현한 원시 데이터를 포위하는 원시 쿼드 트리 내의 그리드를 식별하는 단계;
    상기 원시 쿼드 트리 내의 그리드에 대응하는 그리드를 포함한 실체 쿼드 트리 내에, 원시 데이터를 규정하는 정보를 기억하는 단계; 및
    상기 원시 쿼드 트리 내의 그리드를, 실체 쿼드 트리 내의 그리드와 결합시키는 단계
    를 구비하는 작용을 수행하는 명령을 갖는 것을 특징으로 하는 기억 매체.
  17. 제16항에 있어서,
    상기 그리드를 식별하는 단계는, 상세 레벨 값 및 표시 값을 포함하는 것을 특징으로 하는 기억 매체.
  18. 제16항에 있어서,
    상기 그리드를 식별하는 단계는, 형상들을 표현한 원시 데이터를 포위하는 그리드 쌍을 식별하는 단계를 포함하고,
    상기 그리드를 결합시키는 단계는, 실체 쿼드 트리 내의 그리드를, 원시 쿼드 트리 내의 그리드 쌍과 결합시키는 단계를 포함하는 것을 특징으로 하는 기억 매체.
  19. 제16항에 있어서,
    상기 결합시키는 단계는, 원시 쿼드 트리 내의 각각의 그리드에 할당되는 키를 이용하여 수행되고,
    상기 키는, 원시 쿼드 트리 내의 그리드와, 원시 쿼드 트리 내의 그리드에 관한 정보를 제공하는 실체 쿼드 트리 내의 그리드 간의 상세 레벨 차이를 규정하는 것을 특징으로 하는 기억 매체.
  20. 제19항에 있어서,
    상기 원시 쿼드 트리 내의 그리드가, 전자 문서 내의 형상을 표현한 원시 데이터를 포위하는 그리드 쌍 중 하나인 경우, 상기 키는 팬 값을 포함하는 것을 특징으로 하는 기억 매체.
KR1020060002112A 2005-02-28 2006-01-09 실체 검색 시스템 Ceased KR20060095444A (ko)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US11/068,292 2005-02-28
US11/068,292 US7650345B2 (en) 2005-02-28 2005-02-28 Entity lookup system

Publications (1)

Publication Number Publication Date
KR20060095444A true KR20060095444A (ko) 2006-08-31

Family

ID=35763640

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020060002112A Ceased KR20060095444A (ko) 2005-02-28 2006-01-09 실체 검색 시스템

Country Status (7)

Country Link
US (1) US7650345B2 (ko)
EP (1) EP1720107A3 (ko)
JP (1) JP4885558B2 (ko)
KR (1) KR20060095444A (ko)
CN (1) CN1828593B (ko)
BR (1) BRPI0600155A (ko)
MX (1) MXPA06001609A (ko)

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR100917768B1 (ko) * 2007-11-29 2009-09-21 팅크웨어(주) 공간 질의의 검색 영역 확장 방법 및 상기 방법을 수행하기위한 시스템

Families Citing this family (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US8639725B1 (en) 2011-01-31 2014-01-28 Google Inc. Methods for efficiently querying multiple points in an indexed quadtree
US8856184B1 (en) 2011-01-31 2014-10-07 Google Inc. Methods and systems for encoding the maximum resolution data level for a quadtree
CN102622434B (zh) * 2011-12-31 2014-06-25 华为数字技术（成都）有限公司 数据存储方法、查找方法及装置
US10360294B2 (en) * 2015-04-26 2019-07-23 Sciome, LLC Methods and systems for efficient and accurate text extraction from unstructured documents
CN108304593B (zh) * 2018-04-19 2020-12-29 北京星球时空科技有限公司 纸质地图与电子地图互动显示的方法
CN116912042B (zh) * 2023-09-14 2023-11-28 南京川尔文科技有限公司 用于景点管理系统的处理方法及装置

Family Cites Families (11)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6031544A (en) * 1997-02-28 2000-02-29 Adobe Systems Incorporated Vector map planarization and trapping
US6728775B1 (en) * 1997-03-17 2004-04-27 Microsoft Corporation Multiple multicasting of multimedia streams
KR100319151B1 (ko) * 1999-02-01 2002-01-05 구자홍 다중레벨 이미지 데이터 생성 방법과 다중레벨 이미지 데이터를 이용한 이미지 검색방법
US6684219B1 (en) * 1999-11-24 2004-01-27 The United States Of America As Represented By The Secretary Of The Navy Method and apparatus for building and maintaining an object-oriented geospatial database
US20020107918A1 (en) * 2000-06-15 2002-08-08 Shaffer James D. System and method for capturing, matching and linking information in a global communications network
FI20001534A0 (fi) * 2000-06-28 2000-06-28 Nokia Mobile Phones Ltd Menetelmä ja järjestely paikkatiedon järjestämiseksi, valitsemiseksi ja näyttämiseksi solukkopuhelinjärjestelmässä ja solukkoverkon päätelaite
JP2002041554A (ja) * 2000-07-26 2002-02-08 Denso Corp 施設に関する施設情報の通信方法、通信システム、サーバおよび移動端末
US7239311B2 (en) * 2002-09-26 2007-07-03 The United States Government As Represented By The Secretary Of The Navy Global visualization process (GVP) and system for implementing a GVP
JP2006521033A (ja) * 2003-03-19 2006-09-14 シンクウェア システムズ コーポレーション 移動通信端末機を用いたナビゲーションシステムおよび方法
US7178416B2 (en) * 2003-07-08 2007-02-20 Alexeter Technologies, Llc. Radio frequency identification (RFID) test information control and tracking system
WO2005114484A1 (en) * 2004-05-19 2005-12-01 Metacarta, Inc. Systems and methods of geographical text indexing

Cited By (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR100917768B1 (ko) * 2007-11-29 2009-09-21 팅크웨어(주) 공간 질의의 검색 영역 확장 방법 및 상기 방법을 수행하기위한 시스템

Also Published As

Publication number Publication date
BRPI0600155A (pt) 2007-07-31
EP1720107A3 (en) 2011-03-09
JP2006244480A (ja) 2006-09-14
MXPA06001609A (es) 2006-09-20
EP1720107A2 (en) 2006-11-08
US20060195458A1 (en) 2006-08-31
JP4885558B2 (ja) 2012-02-29
US7650345B2 (en) 2010-01-19
CN1828593B (zh) 2010-11-03
CN1828593A (zh) 2006-09-06

Similar Documents

Publication Publication Date Title
US10089331B2 (en) System and method for storing a dataset of image tiles
US20060218114A1 (en) System and method for location based search
CN114020756B (zh) 遥感影像实时地图服务发布方法和装置
CA2827920C (en) Map creation
KR20060095444A (ko) 실체 검색 시스템
CN103995861A (zh) 一种基于空间关联的分布式数据装置、方法及系统
Lee et al. Implementation of an open platform for 3D spatial information based on WebGL
van Oosterom et al. Data structures for continuous generalisation: tGAP and SSC
US10013474B2 (en) System and method for hierarchical synchronization of a dataset of image tiles
CN110941587B (zh) 基于附加文件的空间矢量数据存储方法及坐标系转换系统
Varma et al. A data structure for spatio-temporal databases
CN116883575B (zh) 建筑群渲染方法、装置、计算机设备和存储介质
CN113157988A (zh) 由ofd格式文件表示地理信息的方法和装置
Novak et al. Digitizing historical maps and their presentation in online map collections
CN117282100A (zh) 地图设计方法和相关设备
Barrett Application of the linear quadtree to astronomical databases
Sperber Quadtree and octree
Youngren et al. A multi-resolution HEALPix data structure for spherically mapped point data
XIAO et al. Integration method of TINs and Grids for multi-resolution surface modeling
Zhao et al. A hierarchical organization approach of multi-dimensional remote sensing data for lightweight Web Map Services
Blower et al. Fast regridding of large, complex geospatial datasets
US20080250309A1 (en) Method for loading and displaying gridded data by determining the usefulness of a particular vertex
JP2001060262A (ja) 大規模画像のディジタル画像情報データベースシステム
Moore et al. Out-of-Core Digital Terrain Elevation Data (DTED) Visualization
CN119379820A (zh) 实景三维系统地理实体时空编码方法、系统、设备及介质

Legal Events

Date Code Title Description
PA0109 Patent application

Patent event code: PA01091R01D

Comment text: Patent Application

Patent event date: 20060109

PG1501 Laying open of application
A201 Request for examination
PA0201 Request for examination

Patent event code: PA02012R01D

Patent event date: 20110104

Comment text: Request for Examination of Application

Patent event code: PA02011R01I

Patent event date: 20060109

Comment text: Patent Application

E902 Notification of reason for refusal
PE0902 Notice of grounds for rejection

Comment text: Notification of reason for refusal

Patent event date: 20120524

Patent event code: PE09021S01D

E601 Decision to refuse application
PE0601 Decision on rejection of patent

Patent event date: 20120903

Comment text: Decision to Refuse Application

Patent event code: PE06012S01D

Patent event date: 20120524

Comment text: Notification of reason for refusal

Patent event code: PE06011S01I