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. 절차 가...

ESPN 텍사스 대학교 사람들이 쓴 논문이다. 제목부터 ESPN이라는 미국 사람 아니면 알아듣지 못할 드립을 던져놓고(ESPN은 미국 연예 및 스포츠 채널이름이다) 시작하는 이 논문은 멀티 벡터 검색에 대한 논문이다. 1. 배경지식과 문제 정의 최신 신경망 IR 시스템은 fine-tuning된 LLM을 활용하여 텍스트 문서를 dense vector ...

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하는 것과 다...

R-tree에서 최근접 이웃 검색 1. 개요 Vector DB에서 말하는 그 최근접 이웃이 맞다. 하지만 ANN을 다루는 것과 달리 공간 데이터 베이스에서는 진짜로 제일 가까운 값을 반환해주어야한다. 이를 위한 방법에 대해서 이번 포스팅간에 알아보겠다. 2. Depth-first Search 쿼리를 Q라고 하자. 이 Q에서 가장 가까운 점 또는 객체...