hnswlib wasm

hnswlib-wasm

C ++로 작성된 HNSWLIB 인덱스 라이브러리의 WASM (WebAssembly) 버전입니다. 이 WASM 포트는 EMCC WASM 컴파일러를 사용하여 @shravansunder에 의해 만들어졌습니다. 여기에서 저장소를 참조하십시오.

라이브러리 hnswlib-node에서 영감을 얻었습니다. @yoshoku는 HNSWLIB-Node에 대한 훌륭한 문서를 제공했습니다. 감사합니다, @yoshoku!

참고 :이 라이브러리는 아직 초기에 있습니다! 브라우저에서 HNSWLIB를 실행 해야하는 사용 케이스를 위해 구축되고 있습니다.

hnswlib-wasm 계층 적 탐색 가능한 작은 세계 그래프를 기반으로 가장 가까운 이웃 검색을 구현하는 hnswlib에 대한 WASM 바인딩을 제공합니다. 브라우저에서 작동하며 Emscripten으로 컴파일됩니다.

설치

$ yarn add hnswlib-wasm

여기에서 NPM 패키지를 참조하십시오.

선적 서류 비치

• HNSWLIB-NODE 용 @YOSHOKU의 HNSWLIB-NODE API 문서는 API에 대한 정확한 설명을 제공합니다. API의 TypeScript 정의는 WASM과 작동하도록 수정되었습니다. 문서는 라이브러리가 진행됨에 따라 업데이트되며 더 많은 예제가 추가됩니다.
• 주요 차이점은 인덱스를로드하고 저장하는 것입니다. indexedDB (브라우저)를 지원하고 emscripten의 FS를 사용하여 가상 파일 시스템 및 IDBF를 통해 인덱스를 저장하고로드합니다.
• @yoshoku ChangeLog의 자세한 내용은 hnswlib-node 의 ChangElog를 참조하십시오.

용법

먼저 라이브러리의 런타임 인스턴스를 만듭니다.

 import { loadHnswlib } from 'hnswlib-wasm' ;

const lib = await loadHnswlib ( ) ;

다음은 인덱스를로드하거나 존재하지 않는 경우 새 인덱스를 생성하는 전체 예입니다.

  const filename = 'ghost.dat' ;
  const { loadHnswlib } = await import ( 'hnswlib-wasm' ) ;
  this . hnswlib = await loadHnswlib ( ) ;
  this . hnswlib . EmscriptenFileSystemManager . setDebugLogs ( true ) ;
  this . vectorHnswIndex = new this . hnswlib . HierarchicalNSW ( 'cosine' , 1536 ) ;
  await syncFileSystem ( 'read' ) ;

  const exists = this . hnswlib . EmscriptenFileSystemManager . checkFileExists ( filename ) ;
  if ( ! exists ) {
    this . vectorHnswIndex . initIndex ( 100000 , 48 , 128 , 100 ) ;
    this . vectorHnswIndex . setEfSearch ( 32 ) ;
    this . vectorHnswIndex . writeIndex ( 'ghost.dat' ) ;
  } else {
    this . vectorHnswIndex . readIndex ( filename , 100000 , true ) ;
    this . vectorHnswIndex . setEfSearch ( 32 ) ;
  }

인덱스를 만들고 그렇게 사용할 수 있습니다.

 // Here you're creating a new index with the L2 distance metric and 1000 as the max number of elements
const hnswIndex = lib . HierarchicalNSW ( 'l2' , 100 ) ;

// Initialize the index with the dimensions (1536), m, efConstruction. See the section below on parameters for more details. These cannot be changed after the index is created.
index . initIndex ( 1536 , 36 , 16 , 200 ) ;

// Set efSearch parameters. This can be changed after the index is created.
index . setEfSearch ( efSearch ) ;

// Now you can add items to the index, labels are returned as an array for the vectors.  It will reuse deleted labels if possible based on the second parameter.
const labels = index . addItems ( vectors , true ) ;

// Now you can search the index
const result1 = index . searchKnn ( vectors [ 10 ] , 10 , undefined ) ;

// You can also search the index with a label filter
const labelFilter = ( label : number ) => {
  return label >= 10 && label < 20 ;
}
const result2 = index . searchKnn ( testVectorData . vectors [ 10 ] , 10 , labelFilter ) ;

더 많은 사용 예제를 추가 할 예정입니다.

현재 테스트 폴더의 HierarchicalNSW.test.ts 파일을 참조하고 HNSWLIB-NODE API 문서를 참조하십시오.

확장 된 IDBFS (IndexedDB) 지원

hnswlib-wasm 라이브러리는 브라우저에 검색 인덱스를 저장하고 관리하기 위해 IndexEdDB (IDBFS)에 대한 확장 된 지원을 제공합니다. 이를 통해 웹 환경에서 검색 색인을 쉽게 저장하고로드 할 수 있으며 EMCC 파일 시스템에서 JavaScript 메모리로 데이터를 이동할 필요가 없습니다. emscripten의 FS를 사용하여 가상 파일 시스템을 통해 인덱스를 저장하고로드합니다. 가상 파일 시스템은 IDBFS와 동기화됩니다.

IDBF로 검색 지수를 저장 및로드합니다

검색 인덱스를 저장하려면 writeIndex 메소드를 사용하십시오.

 await index . writeIndex ( 'savedIndex' ) ;

이전에 저장된 검색 인덱스를로드하려면 readIndex 메소드를 사용하십시오.

 await index . readIndex ( 'savedIndex' , false ) ; 

EMScripten 파일 시스템을 IDBFS와 동기화합니다

syncFs 메소드는 EMScripten 파일 시스템을 지속적인 스토리지 IDBFS와 동기화하는 데 사용됩니다. 이 메소드를 사용하여 파일 시스템의 영구 소스에서 데이터를 저장하거나 읽을 수 있습니다.

 await lib . EmscriptenFileSystemManager . syncFS ( true , emscripten :: val :: undefined ( ) ) ; // Read data from the persistent source
await lib . EmscriptenFileSystemManager . syncFS ( false , emscripten :: val :: undefined ( ) ) ; // Save data to the persistent source 

HNSWLIB-WASM에 대한 HNSW 알고리즘 매개 변수

이 섹션에서는 HNSW 알고리즘 매개 변수에 대한 개요와 HNSWLIB-WASM 라이브러리를 사용할 때 성능에 미치는 영향을 제공합니다. HNSW (Hierarchical Navigable Small World)는 고차원 공간에서 효율적인 유사성 검색을위한 그래프 기반 인덱스 구조입니다.

pinecone.io의 이미지

검색 품질과 인덱스 크기 또는 시공 시간 간의 트레이드 오프를 제어하기 위해 조정할 수있는 여러 매개 변수가 있습니다. 다음은 주요 매개 변수입니다.

검색 매개 변수 : efsearch

EFSearch는 검색 중에 사용되는 가장 가까운 이웃에 대한 동적 목록의 크기입니다. EFSearch 값이 높을수록 검색이 더 정확하지만 느린 검색으로 이어집니다. EFSearch는 가장 가까운 이웃 k 쿼리 수보다 낮게 설정할 수 없으며 k와 데이터 세트의 크기 사이의 값이 될 수 있습니다.

건축 매개 변수 : m

M은 인덱스 구성 중에 모든 새로운 요소에 대해 생성 된 양방향 링크의 수입니다. M의 합리적인 범위는 2-100입니다. 높은 M 값은 고유 차원 및/또는 높은 리콜을 가진 데이터 세트에서 더 잘 작동하는 반면, 낮은 M 값은 고유 차원 및/또는 낮은 리콜을 가진 데이터 세트에서 더 잘 작동합니다. 매개 변수는 또한 저장된 요소 당 대략 m * 8-10 바이트 인 알고리즘 메모리 소비를 결정합니다.

건축 매개 변수 : efconstruction

EFConstruction은 인덱스 구조 시간과 정확도를 제어합니다. efconstruction 값이 커지면 시공 시간이 길지만 인덱스 품질이 향상됩니다. 어느 시점에서 EFConstruction의 증가는 지수의 품질을 향상시키지 않습니다. 선택한 efconstruction 값이 적절한 지 확인하려면 efsearch = efconstruction에서 가장 가까운 이웃 검색에 대한 리콜을 측정하십시오. 리콜이 0.9보다 낮 으면 개선의 여지가 있습니다.

hnswlib-wasm에 대한 매개 변수 선택

HNSWLIB-WASM을 사용하는 경우 데이터 세트 크기 및 차원을 기반으로 M, EFSEARCH 및 EFCONSSTUCUCTURUCTUCOUCTUCTION에 적절한 값을 선택해야합니다. HNSWLIB-WASM이 브라우저에서 실행 중이므로 사용 가능한 메모리 및 성능 제한을 고려해야합니다. 몇 가지 권장 사항은 다음과 같습니다.

중:

대부분의 사용 사례에 적합하므로 12-48 범위의 값을 선택하십시오. 특정 데이터 세트의 최적 값을 찾기 위해 실험해야 할 수도 있습니다.

efsearch :

M에 가까운 값으로 시작하여 검색 속도와 정확도 사이의 원하는 트레이드 오프에 따라 조정하십시오. 낮은 값은 더 빠르지 만 덜 정확하지만 더 높은 값은 더 정확하지만 느리게됩니다.

efconstruction :

예상 쿼리 볼륨을 고려 하여이 값을 설정하십시오. 낮은 쿼리 볼륨을 예상하면 EFConstruction의 값이 높을수록 검색 시간에 최소한의 영향을 최소화하여 리콜을 개선하여 특히 M 값이 낮을 때.

M 값이 높을수록 인덱스의 메모리 사용량이 증가하므로 HNSWLIB-WASM의 매개 변수를 선택할 때 성능 및 메모리 제약 조건을 균형을 유지해야합니다.

자원

Pinecone으로 HNSW를 배우십시오

PENECONE의 벡터 인덱스

pinecone.io의 이미지

다른 메모

특허

HNSWLIB-WASM은 Apache-2.0 라이센스의 조건에 따라 오픈 소스로 제공됩니다.

기여

구축하려면

 yarn install
make rebuild
yarn build

테스트합니다

 yarn test

먼저 @shravansunder에 문의하십시오!