잘지내자, 우리 잘지내자, 우리

이번 장에서는 쿼리 실행에 대한 원칙에 대해 배워보자. 쿼리에 답하기 위한 cost(비용)은 다음 두 가지에 영향을 받는다. 파티셔닝 원칙(Partitioning principle) 쿼리 실행 알고리즘(Query execution algorithm) 파티셔닝 원칙은 지난 블로그에서 다뤘으니, 이번에는 쿼리 실행 알고리즘에 대하여 다뤄보겠다. 알고리즘들을 보기 앞서, Hypothetical Index Organiztion에 대해 알아볼 필요가 있다. Hypothetical의 사전적 의미는 '가상의'라는 뜻으로, 직역하자면 '가상의 인덱스 구성'이라고 볼 수 있겠다. 일반적인 Array를 생각해보면, 각 배열에는 한개의 object가 존재한다. 하지만 위계질서(hierarchy)를 가진 entries로 노드..

이번 장에서는 기본적인 partitioning 원칙에 대해 다뤄보자. 거리 공간 M=(D,d)에 대하여 총 세 가지의 기본 분류 방법을 다뤄볼것이다. 1. Ball Partitioning 아주 기본적이고 간단한 방법이이다. 반지름 dm을 기준으로 안/ 밖에 속하는 object로 구분한 것이다. 좀 더 발전한 방법으로 Multi - way ball partitioning도 있다. 안과 밖의 두 집합으로 나누는 것이 아니라, 안/중간/밖 이렇게 세 부분으로 분류를 한다. 2. Generalized Hper-plane Partitioning Ball Partitioning이 원을 기준으로 구역이 나뉘었다면, Generalized hyper-plane Partitioning은 직선을 기준으로 로 구역이 나뉜다...

이번 장에서는 여러 유형의 쿼리에 대해서 다뤄보겠다. 1. Range query - 범위 쿼리 쿼리 q로부터 r반경에 있는 data들을 가져온다. 내 호텔로부터 2키로 반경 내에 있는 모든 박물관을 검색하는것을 예로 들 수 있다. R(q,r)에서 q : 내 호텔, r : 2km가 되겠다. 2. Nearest Neighbor Query The nearest neighbor query - 최근접 이웃 쿼리 쿼리로부터 가장 가까운 data를 '하나만' 검색한다. 내 호텔에서 가장 가까운 박물관을 검색하는 것을 예로 들 수 있다. K-nearest neighbor query - 근접 이웃 쿼리 쿼리로부터 가까운 순서대로 k개의 data를 검색한다. 내 호텔에서 가까운 순서대로 5개의 박물관을 검색하는 것을 예로..

Metric Space의 정의 거리 공간( metric space)은 두 점 사이의 거리가 정의된 공간이다. 거리의 정의에 따라 표준적인 위상상을 갖는다. Metric space M =(D,d)의 정의는 다음과 같다. M = (D,d) - Data domain D - Total (distance) function d: D * D -> [0,무한) 즉 데이터의 집합 D와, 데이터 간의 거리를 표현하는 function 'd'가 정의된 공간이라 할 수 있다. 이 거리공간은 다음과 같은 조건을 만족시켜야 한다. 위 조건들을 간단히 설명하자면, - 거리공간에서 서로 다른 두 점 사이의 거리는 음수가 될 수 없고(p1) - 임의의 점 x에서 y까지의 거리는 y에서 x까지의 거리와 같으며(p2) - 같은 두 점 사이..

본 카테고리에서 다루는 내용은 'Similarity Searching in Multimedia Data'라는 과목의 시험을 준비하며 공부한 내용을 기록한 것이다. 모든 내용은 prof. Ing. Pavel Zezula, CSc. 교수의 강의자료에서 발췌하였다. 이 과목의 목차는 다음과 같다. Part 1 : Metric searching in a nutshell Foundations of metric space searching Survey of existing approaches Part 2 : Metric searching in large collections Centralized index structures Approximate similarity search Parallel and distrib..