초록

용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

본 논문에서는 다차원 데이터의 유사도 검색을 효과적으로 수행하기 위한 색인 구조를 제안한다. 제안하는 색인 구조는 차원의 저주 현상을 극복하기 위한 벡터 근사 기반의 색인 구조이다. 제안하는 색인 구조는 부모 노드를 기준으로 KDB-트리와 유사한 영역 분할 방식으로 분할하고 분할된 각 영역은 데이터의 분포 특성에 따라 동적 비트를 할당하여 벡터 근사화된 영역을 표현한다. 따라서, 하나의 노드 안에 않은 영역 정보를 저장하여 트리의 깊이를 줄일 수 있다. 또한 다차원의 특징 벡터 공간에 상대적인 비트를 할당하기 때문에 군집화되어 있는 데이터에 대해서 효과적이다 제안하는 색인 구조의 우수성을 보이기 위해 다양한 실험을 통하여 성능의 우수성을 입증한다.

본 논문에서는 다차원 데이터의 유사도 검색을 효과적으로 수행하기 위한 색인 구조를 제안한다. 제안하는 색인 구조는 차원의 저주 현상을 극복하기 위한 벡터 근사 기반의 색인 구조이다. 제안하는 색인 구조는 부모 노드를 기준으로 KDB-트리와 유사한 영역 분할 방식으로 분할하고 분할된 각 영역은 데이터의 분포 특성에 따라 동적 비트를 할당하여 벡터 근사화된 영역을 표현한다. 따라서, 하나의 노드 안에 않은 영역 정보를 저장하여 트리의 깊이를 줄일 수 있다. 또한 다차원의 특징 벡터 공간에 상대적인 비트를 할당하기 때문에 군집화되어 있는 데이터에 대해서 효과적이다 제안하는 색인 구조의 우수성을 보이기 위해 다양한 실험을 통하여 성능의 우수성을 입증한다.

AI 본문요약

엑셀 다운로드 AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

• 연구 주제
• 연구 방법
• 연구 결과

문제 정의

• 己본 논문에서는 기존에 제안된 벡터 근사 기법 의 문제점을 해결하기 위한 새로운 다차원 색인 구조를 제안한다. 제안하는 색인 구조에서는 KD8-트리와 유사한 영역 분할을 수행하고 각각의 분할된 영역에 대해 실제 데이터가 존재하는 영역에 대해서 근사화룔 수행한다.
• 본 논문에서는 차원의 저주 현상을 해결하기 위한 벡 터 근사 기반의 다차원 색인 구조를 제안하였다. 제안하는 색인 구조는 하위 노드 영역을 부모 노드를 기준으로 상대적으로 표현하고 각각의 영역은 데이터 분포 특성에 따라 동적인 비트를 할당하여 근사화한다.

제안 방법

• 성능 평가를 위해 각각 임의로 생성된 10만개의 랜덤 데이터 집합과 코렐 이미지에서 추출된 실제 데이터 집합을 사용한다. ABA-트리의 검색 성능을 평가하기 위해서 가장 대표적인 유사성 검색 질의인 k-최근접 질의와 범위 질의를 수 행하여 수행 시간을 측정한다. 검색 시간은 질의를 50번 수행한 평균 값을 이용한다.
• 즉, 겹침 영역이 없이 분할된 영역은 정적인 비 트로 할당하여 표현하지 않고 자식 영역의 분포 뜩성을 고려하여 直과적으로 표현할 수 있는 동적 비트를 할당 하여 자식 영역 정보童 좀더 정확하고 食과적으로 표현 한다. 분할된 영역 내에 BMB賦 표현하기 위한 비트 수룔 결정하기 위해 실제 데이터들이 존재하는 영역과 비트 형태로 근사화한 BMBBe 차이養 이용하여 계산한 다, 그림 3과 같이 중간 노드에서 분할된 두 개의 영역 이 존재할 때 분할된 영역에 대한 BMBR을 표현하면 표 1과 같다.
• 제안하는 ABA■■트리는 다차원 색인 구조의 문제점을 해결하기 위해 다차원 데이터 공간을 KDB-토리와 유사한 영역 분할 기법을 이용하여 분할된 영역에 동적 비트 를 할당하는 벡터 근사화 트리이다. 기존에 제안된 색인 구조는 벡터 근사화 기법을 수행하기 위해 전체 영역 또는 분할된 일부 영역에 고정된 비트를 할당하여 노드의 팬아뭇을 증가시켰다.
• 본 논문에서는 차원의 저주 현상을 해결하기 위한 벡 터 근사 기반의 다차원 색인 구조를 제안하였다. 제안하는 색인 구조는 하위 노드 영역을 부모 노드를 기준으로 상대적으로 표현하고 각각의 영역은 데이터 분포 특성에 따라 동적인 비트를 할당하여 근사화한다. 또한 차원의 증가에 따른 영역들 사이의 겹침 영역을 감소시키기 위해 영역 분할 방식을 사용한다.
• 己본 논문에서는 기존에 제안된 벡터 근사 기법 의 문제점을 해결하기 위한 새로운 다차원 색인 구조를 제안한다. 제안하는 색인 구조에서는 KD8-트리와 유사한 영역 분할을 수행하고 각각의 분할된 영역에 대해 실제 데이터가 존재하는 영역에 대해서 근사화룔 수행한다. 또한 하위 노드는 부모 노드릁 기준으로 상대적으로 표현하며 데이터의 분포 특성에 따라 동적으로 비트를 할당한다.

대상 데이터

• 8敝 CPU와 256MB의 윈도우즈 2000 시스템 환경에서 C언어룔 이용하여 구현한다. 성능 평가를 위해 각각 임의로 생성된 10만개의 랜덤 데이터 집합과 코렐 이미지에서 추출된 실제 데이터 집합을 사용한다. ABA-트리의 검색 성능을 평가하기 위해서 가장 대표적인 유사성 검색 질의인 k-최근접 질의와 범위 질의를 수 행하여 수행 시간을 측정한다.
• 실험 평가률 위해 제안하는 ABA-트리와 CS-트리를 Pentium-IV 1.8敝 CPU와 256MB의 윈도우즈 2000 시스템 환경에서 C언어룔 이용하여 구현한다. 성능 평가를 위해 각각 임의로 생성된 10만개의 랜덤 데이터 집합과 코렐 이미지에서 추출된 실제 데이터 집합을 사용한다.

이론/모형

• 제안하는 색인 구조는 하위 노드 영역을 부모 노드를 기준으로 상대적으로 표현하고 각각의 영역은 데이터 분포 특성에 따라 동적인 비트를 할당하여 근사화한다. 또한 차원의 증가에 따른 영역들 사이의 겹침 영역을 감소시키기 위해 영역 분할 방식을 사용한다. 성능 평가 결과 제안하는 색인 구조는 기존에 제안된 CS-트리보다 약 40%정도의 검색 성능이 향상됨을 보였다.

성능/효과

• Z1 러나 이러한 기법들은 특정 영 역에 데이터들이 군집화되어 있을 경우 분할된 영역들 사이에 선별력이 감소될 수 있다. 따라서 제안하는 색인 구조에서는 분할된 영역에 고정된 비트를 할당하는 것이 아니라 데이터의 분포 상태에 대한 동적으로 비트를 할 당하는 MBR)를 나타낸다. 기존의 데이터 분 할 기반의 색인 구조는 차원이 증가할수록 분할된 영역 들 사이에 겹침 영역이 증가되어 검색 성능이 저하될 수 있다.
• 또한 차원의 증가에 따른 영역들 사이의 겹침 영역을 감소시키기 위해 영역 분할 방식을 사용한다. 성능 평가 결과 제안하는 색인 구조는 기존에 제안된 CS-트리보다 약 40%정도의 검색 성능이 향상됨을 보였다.
• 제안하는 ABA-트리의 전체적인 검색 성능은 기존에 제안된 CS-트리보다 약 40%정도의 성능 항상을 보이고 있다. 제안하는 색안 구조는 단말 노드로의 검색에 있어서 KDB-트리와 같은 영역 분할 방식으로 표현된 노드로 인해서 접근해야 할 노드를 감소시켜 페이지의 접근 횟 수가 감소시키고 엔트리 내에 저장되는 MBR 정보롤 비 트 MBR로 표현함으로서 팬아웃이 증가하게 된다.
• 제안하는 ABA-트리의 전체적인 검색 성능은 기존에 제안된 CS-트리보다 약 40%정도의 성능 항상을 보이고 있다. 제안하는 색안 구조는 단말 노드로의 검색에 있어서 KDB-트리와 같은 영역 분할 방식으로 표현된 노드로 인해서 접근해야 할 노드를 감소시켜 페이지의 접근 횟 수가 감소시키고 엔트리 내에 저장되는 MBR 정보롤 비 트 MBR로 표현함으로서 팬아웃이 증가하게 된다. 이와 같이 접근해야 할 페이지의 감소와 팬아뭇의 증가는 유 사성 기반의 검색 시간을 단축시킨다.

본문요약 정보가 도움이 되었나요? 예 아니오 제출

이 논문을 인용한 문헌

더보기