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

이번 장에서는 기본적인 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..