CAGRA: Highly Parallel Graph Construction and Approximate Nearest Neighbor Search for GPU 이전의 Graph 기반 Vector 검색은 CPU 기반이었다. 이번에 리뷰할 논문인 CAGRA는 NVIDIA에서 나왔는데 GPU를 이용해서 가속이 가능한 Graph 알고리즘이다. 이전에 다른 ...
문자열 검색 알고리즘 말 그대로 주어진 텍스트에서 특정 문자열을 찾는 알고리즘에 대한 간단한 포스팅을 할까한다. 찾아보니까 문자열 탐색 알고리즘은 좀 많고, 컴파일러에서 쓰이는 오토마톤 기반 매칭도 있지만 그런것들은 제외하고 단순구현, KMP, Boyer-Moore 방식만 포스팅해보도록 하겠다. 1. 단순 구현 사실 어떤 문제가 주어지면 가장 먼저...
유클리드 호제법(Euclidean algorithm) 그냥 기본 알고리즘 리마인드 겸 포스팅하는 것이다. 1. 개요 간단히 말해서 두 자연수 간의 최대공약수를 찾는 알고리즘이다. 명시적으로 기술된 가장 오래된 알고리즘으로서도 알려져 있으며, 기원전 300년경에 쓰인 《원론》 제7권, 명제 1부터 3까지에 해당한다. 2. 방법 방법은 매우 간단하...
SVFusion 이번에 리뷰해볼 논문은 VLDB 26’에 발표된 CPU와 GPU를 동시에 사용하는 실시간 Vector DB에 대해 발표된 SVFusion이다. 벡터 검색 연구를 하는 입장으로써 GPU까지 사용하는 논문이 우후죽순처럼 나오는 가운데, CPU와 GPU를 같이 사용해볼 방법이 없을까?하고 고민하고 있다가 교수님께서 권해주셔서 보게 된 논문...
LSM Tree(Log-structured merge-tree) 1. 개요 먼저 LSM Tree(Log-Structured Merge-Tree)를 한 마디로 표현하자면 데이터베이스 시스템에서 고속 쓰기(high insert volume) 워크로드를 효율적으로 처리하기 위해 설계된 디스크 기반 데이터 구조이다. 데이터 베이스의 구조로 그냥 B트리나 B...
KV-SSD 1. 개요 KV-SSD(Key-Value Solid State Drive)는 전통적인 블록 기반 인터페이스 대신 키-밸류 인터페이스를 직접 제공하는 차세대 저장장치다. 이는 데이터센터 및 클라우드 환경의 규모 확대에 따라 CPU가 블록 변환 작업에 과부하를 겪는 문제를 해결하기 위해 개발되었다. 2. 기술 원리 및 구조 1) 소프트웨어 ...
블름 필터(Bloom Filter) 1. 개요 블룸필터는 1970년 Burton Howard Bloom이 제안한 확률론적(probabilistic) 데이터 구조로, 어떤 원소가 집합에 속할 수도 있다(false positive 가능) 또는 확실히 속하지 않는다(false negative 불가능)는 반환이 가능한 구조이다. 메모리 효율성과 연산 속도의...
AI 에이전트 1. 개요 최근 AI가 발달하면서 AI를 활용한 많은 서비스들이 AI 에이전트라는 이름을 많이 달고 나온다. 그런데 여기서 말하는 AI 에이전트란 무엇일까? AWS 공식 홈페이지에서 말하는 AI 에이전트는 환경과 상호 작용하고, 데이터를 수집하고, 데이터를 사용하여 사전 결정된 목표를 달성하기 위해 필요한 작업을 스스로 결정해서 수행할...
Torch extension 사용법 1. 개요 원래 GPU를 구동할 수 있는 코드는 C++을 이용해서만 짤 수 있었다. 하지만 개발간 Python이 매우 많이 사용됨으로 인해, C++로 짜여진 커널을 Python에서 구동할 수 있으면 좋겠다는 니즈가 생겼고 이로 인해 많은 라이브러리들이 CUDA 커널을 지원하기 시작했다. 이번에는 많은 라이브러리들...
Spatial keyword queries 1. 개요 이전까지의 포스팅은 단순히 공간 혹은 길에 대해서 거리만을 고려하여 검색했다면, 이번 포스팅은 지리적 위치와 텍스트 정보를 결합한 Geo-Textual 데이터를 질의하는 법에 대한 내용이다. 여기서 말하는 텍스트 정보는 크게 두 가지로 나뉜다. 정적 데이터 위치를 포함한 웹페이지,...