CNN(Continuous Nearest Neighbor) 1. 개요 연속 최근접 이웃 쿼리는 쿼리 선분(query segment)을 따라 이동하면서 각 구간별로 가장 가까운 데이터 포인트를 찾는 문제이다. 목표는 데이터셋을 한 번만 순회하여 모든 분할 지점(split points)과 각 구간의 최근접 이웃을 찾는 것이다. 아래의 그림을 보자 ...

RNN(Reverse nearest neighbor) 1. 개요 RNN은 Query q에 대해 어떤 점 p가 p의 최근접이 q인 경우 p를 q의 역최근접 이웃으로 간주하는 개념으로, 직관적으로 q가 특정 점들의 NN이 되는 집합을 찾는 문제를 말한다. q의 가장 최근접이 p일 때 q 역시 p의 가장 최근접이 아닌가 하고 그냥 언뜻 생각하면 그렇게 생...

Road Network 1. 개요 이전까지 공간 데이터 베이스에 관련된 포스팅은 직선거리에 대한 내용이었다. 하지만 실제 우리가 거리와 공간에 대해서 질의할 때 얻는 답변은 실제로 우리가 가고자하는 곳에 어떤 도로나 길을 타고 갔을 때 얼마나 가야 가장 가깝게 도착할 수 있는지 등에 대한 내용이다. 2. Graph Modeling of Road ...

Spatial join 1. 개요 두 공간이 겹치는 것을 어떻게 판별할 수 있을까? 이번에 포스팅할 내용은 점 혹은 객체가 서로 다른 R 트리나 서로 다른 Hash 기반 index에 있을 때 관계를 확인하는 방법에 대한 내용이다. 해당 관계가 교차인지 포함인지 근접인지는 실질적으로 체크를 해봐야하나 일단 이번 포스팅에서는 교차 기반으로 설명하겠다. ...

Vector DB - Re-rank 1. 개요 이전에 ANN(approximate nearest neighbor)에 대해서 포스팅한 적이 있다. 하지만 이 ANN의 경우 대부분 Single vector retrieval을 대상으로 하는 방식이다. 여기서 말하는 Single vector retrieval이란 검색 대상인 Document들은 각각 하나...

K-means 1. 개요 데이터를 여러 그룹으로 나누는 분할법의 일종이다. 초기에 K개의 중심점을 선정하여 해당 중심점을 기준으로 각 점들과의 거리를 계산하여 가까운 중심점에 할당하여 K개의 클러스터를 만들어내는 식이다. 이 알고리즘은 자율 학습의 일종으로, 레이블이 달려 있지 않은 입력 데이터에 레이블을 달아주는 역할을 수행한다. 2. 절차 가...

Muvera 1. 문제 정의 Neural embedding 모델은 현대 정보 검색 파이프라인의 핵심 구성 요소가 되었다. 이는 어떤 문서를 임베딩 벡터화 했을 때 다수의 문서 중에서 가장 거리가 가까운 값일 수록 해당 문서에 가깝다는 것이 알려졌기 때문이다. 이러한 원리를 이용하여 데이터를 벡터화하여 벡터화한 데이터를 Search하는 방법들이 많이 ...

CUDA Stream 간 동기화 이전에 cuda 문법에 대해서 포스팅한 적이 있다. 이번에는 Stream 동기화에 대해서 좀 더 알아보도록 하겠다. 1. 개요 GPU를 잘 사용한다는 것은 GPU를 100% 활용한다는 것이다. 일반적으로 Branch가 적고 Memory coalescing을 지키며 Warp Occupancy가 높고, Shared M...

Ethereum 1. 개요 비트코인은 사토시 나카모토의 백서에서 시작되었지만 이더리움은 비탈릭 부테린(Vitalik Buterin)의 2013년 작성된 백서에서 시작된 프로젝트로 비트코인에 이은 2세대 암호화폐이다. 블록체인을 ‘화폐’뿐 아니라 다양한 프로그램(스마트 계약)을 돌리는 플랫폼으로 확장하는게 목표이다. 화폐 단위는 이더(ETH)이며 비트...

M-tree 1. 개요 앞서 포스팅했던 Space-driven 방식이나 Data-driven 방식의 경우에는 한 가지 공통점이 있다. 바로 차원의 저주에 취약하다는 점이다. 차원의 저주라는 것은 차원이 늘어나면 늘어날 수록 어떤 방식이든 간에 데이터가 넓게 퍼져버리는 것이다. 이렇게 데이터가 넓게 퍼져버리면 결론적으로 전체 Scan하는 것과 다...