Distributed computation of Approximate Nearest Neighbors

Distributed computation of Approximate Nearest Neighbors

기타 소스코드

1.0.0

다운로드

대략적인 가장 가까운 이웃의 분산 계산

이 프로젝트는 Wikimedia Foundation과의 외부 협업에서 컴퓨터 과학 석사 학위를위한 마스터 논문 작업 "대략적인 이웃의 분산 계산"을 언급합니다. 이 작업은 Wikipedia의 이미지 업로드 서비스를보다 효율적으로 만들고, 가장 가까운 이웃의 계산을 배포하고, 임시 솔루션을 개발하고, 기존 가능성을 탐색하고, Wikimedia 데이터 세트 내에서 유사한 이미지의 분산 검색을 수행하도록 조정하는 방법을 연구하는 데 중점을 둡니다.

이 저장소는 무엇입니까?

이 저장소는 내 목적에 가장 적합한 것을 찾기 위해 유사성 (코사인) 검색을 수행하기위한 여러 라이브러리의 구현을 포함하기위한 것입니다. 다양한 구현은 이전에 노출 된 사용 사례를 기반으로합니다.

가장 가까운 이웃

KNN :이 라이브러리는 근사치가 아니며 내 연구 사용 사례에 비효율적이지 않으며, Sklearn과 함께 구현은 근사된 라이브러리와 비교 목적으로 만 제공되었습니다. KNN 내부에는 데이터 구조를 생성하지 않고 단일 벡터와 전체 데이터 세트 간의 선형 비교를 실행하는 무차별적인 버전이 있습니다.
성가신 :이 도서관은 Spotify를 대신하여 Erik Bernhardsson이 작성한 Ann 버전을 구현합니다.
FAISS :이 라이브러리는 Facebook (현재 META) 연구팀에 의해 효율적인 유사성 검색 및 조밀 한 벡터 클러스터링을 위해 만들어졌습니다.
SPTAG :이 라이브러리는 Microsoft에서 Diskann이라는 이전 라이브러리의 대체 버전으로 만든 대규모 벡터 대략 가장 가까운 이웃 검색을 위해 설계되었습니다. 다른 기술과 달리이 솔루션에는 RAM 메모리 및 물리 디스크 사용이 포함되며, 정보를 얼마나 많이 저장하는지 효율적으로 관리합니다.

가장 가까운 이웃을 배포했습니다

Distributed-Faiss :이 라이브러리는 이미 다루어졌지만 분산 버전은 아닙니다. 이 알고리즘은 매우 효율적이지만 단일 시스템에서 실행 된 이전에 분석 한 제안에 새로운 추가 기능을 추가하지 않습니다. 그러나이 라이브러리를 특별하게 만드는 것은 여러 컴퓨터에 매우 간단한 방식으로 배포 할 수 있다는 것입니다.
Distributed-SPTAG :이 라이브러리는 이미 다루어졌지만 분산 버전은 아닙니다. 이 알고리즘은 매우 효율적이지만 단일 시스템에서 실행 된 이전에 분석 한 제안에 새로운 추가 기능을 추가하지 않습니다. 그러나이 라이브러리를 특별하게 만드는 것은 여러 컴퓨터에 매우 간단한 방식으로 배포 할 수 있다는 것입니다.
MILVUS :이 라이브러리는 유사성 검색 및 AI 구동 응용 프로그램을위한 효율적인 시스템 및 아키텍처를 제공하는 데 중점을 둔 벡터 데이터베이스를 구현합니다. Milvus가 만족시키려는 요구는 거대한 동적 데이터 세트에서 작동 할 수있는 완벽한 시스템을 제공하여 GPU에서도 분산 된 방식으로 실행할 수있는 솔루션을 제공하는 것입니다. 이 작업을 수행하기 위해 Milvus는 이미 FAISS로 설명 된 라이브러리를 구축하여 사용 사례에 필요한 변경 사항을 변경했습니다.

그것이 어떻게 구성되어 있는지

이 프로젝트는 파일을 쉽게 구성하고 내 탐색을 간단하게 만들기 위해 정확한 방법으로 구성되었습니다.

알고리즘 :이 폴더 내에서 모든 구현을 찾을 수 있습니다.
- 각각의 라이브러리 :
  - config.py :이 파일에는 라이브러리의 올바른 작동에 필요한 구성이 포함되어 있습니다.
  - init.py :이 파일에는 데이터 세트를 읽고 데이터 구조를 훈련하고 인덱스 생성을위한 코드가 포함되어 있습니다.
  - Search.py :이 파일에는 검색을 수행하고 결과 항목을 반환하기위한 코드가 포함되어 있습니다.
    - 기타 파일 : Chronometer.py, mocks.py
데이터 세트 : 메모리에 저장된 데이터 세트 및 데이터 구조 가이 폴더 내부에 삽입됩니다.
- 압축 :이 폴더에서는 삽입 된 예제에서 볼 수 있듯이 압축 데이터 세트를 삽입 할 수 있습니다. 모든 wikimedia 데이터 세트를 포함하는 links.txt라는 파일을 알 수 있습니다.
- 압축 압축 :이 폴더에서는 감압 된 데이터 세트를 삽입 할 수 있습니다. 여기에서 라이브러리의 올바른 기능을 위해 필터링되고 분해됩니다.
- 이미지 :이 폴더 내에서 데이터 세트에서 추출한 벡터에 해당하는 이미지를 찾을 수 있습니다.
- 벡터 :이 폴더 내에서 데이터 세트에서 추출한 이미지에 해당하는 벡터를 찾을 수 있습니다.
- formatdatasets.bash :이 파일,이 readme.md에 따른 실행 파일에는 벡터/ 폴더 내부의 벡터를 벡터와 이미지/ 폴더 내부의 해당 이미지를 움직이는 벡터를 벡터로 이동하는 데 모든 데이터 세트를 분해하는 코드가 포함되어 있습니다. 이 파일은 formatdatasets.py를 사용하여 .csv 파일을 이진 형식으로 변환하여 모든 프로젝트의 속도를 높입니다.
문서 : 논문을 쓰는 동안 얻은 문서

실행 방법

일부 데이터 세트를 다운로드하십시오

압축 된 폴더로 이동하여 wget -i links.txt 실행하여 Wikimedia 데이터 세트 (이미지, 벡터)를 다운로드하십시오.
wikimedia 데이터 세트 케이스 gunzip *.gz 에서 감압 아카이브
데이터 세트 폴더로 이동하여 readme.md를 따르십시오

라이브러리 가져 오기 / 설치 / 컴파일

먼저 알고리즘 폴더로 이동하여 pip install -r requirements.txt 사용하여 일반 요구 사항을 설치하십시오.

KNN : pip install scikit-learn 하거나 Brute-Force 버전을 사용하려는 경우 아무것도 설치하지 마십시오.
짜증 : pip install annoy
Faiss : Conda 튜토리얼을 따르십시오
SPTAG : 소스 코드를 통해이 라이브러리를 컴파일하거나 Docker를 사용할 수 있습니다. 나는 다음 명령을 실행하여 후자의 솔루션을 개인적으로 권장합니다.
```
 set GIT_LFS_SKIP_SMUDGE=1 
git clone --recurse-submodules https://github.com/microsoft/SPTAG
cd SPTAG
docker build -t sptag .
```
Distributed -Faiss : 저장소를 복제하십시오 ( set_index_parameter 또는 set_index_parameters 메서드를 사용하여 검색 단계에 정밀도를 추가하기 위해 내 PR을 사용하려는 경우이 저장소를 복제 한 다음 폴더를 입력 한 다음 pip install -e .
분산-스파이 : SPTAG 에 대한 지침을 따르십시오
MILVUS : pip install pymilvus 다음 MILVUS는 Docker Compose 또는 Kubernetes (테스트를위한 Milvus 독립형) 또는 Helm + Kubernetes (생산을위한 Milvus 클러스터)와 함께 설치할 수 있습니다.

ANN 라이브러리를 실행하십시오

라이브러리를 실행하기 전에 다양한 config.py 파일을 사용자 정의합니다

python init.py
python search.py

분산 된 라이브러리를 실행하십시오

라이브러리를 실행하기 전에 다양한 config.py 파일을 사용자 정의합니다

분산 푸스 :
1. Discovery_Config.txt 파일을 사용자 정의하십시오.
2. 각 서버에서 실행하십시오 python init_server.py
3. 클라이언트 python init_client.py 에서 실행하십시오
4. 클라이언트 python search.py 에서 실행하십시오
분산-스파 그타 :
1. 각 서버로 이동하여 config.py 파일 (start_metadata_offset에 대한주의)를 사용자 정의하고 python init.py 실행하십시오.
2. 이전에 생성 된 인덱스를 호스팅하는 서버로 이동하십시오. 라이브러리의 릴리스 폴더에서 Service.ini 파일을 가져오고 사용자 정의하고 명령을 실행합니다 ./server -m socket -c service.ini
3. 집계 자로 식별하는 기계로 이동하십시오. 라이브러리의 릴리스 폴더에서 Aggregator.ini 파일을 가져 와서 사용자 정의하고 명령을 실행하십시오 ./aggregator
4. 클라이언트로 이동하여 config.py 파일을 사용자 정의하고 python search.py 실행하십시오.
밀버 :
1. python init.py
2. python search.py