대용량 데이터에 대한 Knn 검색?

Question

대용량 데이터 세트에서 knn 검색을 수행하는 데 관심이 있습니다.

libs : ANN과 FLANN이 있지만, 전적으로 메모리 (RAM)에 맞지 않는 데이터베이스가있는 경우 어떻게 검색을 구성해야합니까?

Answer 1

인덱스가 메모리에 비해 얼마나 큰지에 달려 있다고 생각합니다. 여기에 처음으로 자발적인 아이디어는 다음과 같습니다

1. 그것이 수십 배의 RAM의 크기, 내가 예를 들어, 사용하여 내 데이터를 클러스터하려고 것이었다 가정하면, (플란넬에서 구현) 계층 적 클러스터링 나무. 나무의 구현을 수정하여 분기를 메모리에 유지하고 디스크에 나뭇잎 (클러스터)을 저장합니다. 따라서 매번 적절한 클러스터를로드해야합니다. 그런 다음이를 다양한 방법으로 최적화하려고 할 수 있습니다.

2. 크기가 크지 않다면 (RAM의 두 배 크기라고 가정) 데이터 세트를 두 부분으로 나누고 각각에 대해 하나의 색인을 만듭니다. 따라서 각 데이터 집합에서 가장 가까운 이웃을 찾아서 선택해야합니다.

Answer 2

귀하의 데이터가 매우 고차원인지 아닌지에 따라 다릅니다. 비교적 저 차원 인 경우 디스크 상에 기존 R-Tree 구현 (예 : Spatialite)을 사용할 수 있습니다.

더 높은 차원의 데이터 인 경우 X-Trees을 사용할 수 있지만 내 머리 꼭대기에있는 디스크상의 구현에 대해서는 알지 못합니다.

또는을 디스크 지속성과 함께 구현할 수 있습니다 (예 : mmap 사용).