ekzhu/datasketch

해결하는 문제

매우 큰 데이터셋을 매우 빠르게 처리하고 검색할 수 있는 방법을 제공합니다. 전체 데이터셋을 메모리에 저장하거나 처리할 필요 없이, 매우 큰 양의 데이터에서 유사성과 카디널리티(고유 요소의 수)를 계산하는 문제를 해결합니다.

작동 방식

이 라이브러리는 데이터의 압축된 표현을 생성하기 위해 '스케치'라고 불리는 확률적 데이터 구조를 사용합니다. 데이터의 특성을 추정하기 위해 여러 알고리즘을 구현합니다:

• MinHash 및 Weighted MinHash: Jaccard 유사도와 카디널리티를 추정하는 데 사용됩니다.
• HyperLogLog 및 HyperLogLog++: 고유 요소의 수(카디널리티)를 추정하는 데 사용됩니다.

이러한 스케치를 효율적으로 검색하기 위해, 선형 시간보다 낮은 쿼리 시간(서브라인어)을 가능하게 하는 다양한 인덱스를 제공합니다. 예를 들어, 임계값 기반 유사성 검색에 사용하는 지역 민감 해싱(LSH), 사용자 정의 메트릭의 상위 K 쿼리에 사용하는 HNSW가 있습니다.

대상 사용자

10억 규모의 데이터셋에서 고속 유사성 검색 또는 고유 항목 수를 세야 하는 데이터 엔지니어 및 소프트웨어 개발자.

주요 특징

• 확률적 효율성: 메모리 손실을 최소화하고 높은 속도로 대규모 데이터를 처리합니다.
• 확장 가능한 저장소: LSH 인덱스용으로 Redis와 Cassandra를 저장 레이어로 지원합니다.
• 다양한 인덱싱: Jaccard 임계값, 상위 K 쿼리 등 다양한 쿼리 유형에 대응하는 LSH, LSHBloom, LSH Forest, HNSW를 제공합니다.
• 유연한 스킴: 데이터셋 크기에 따라 메모리와 속도를 최적화할 수 있는 여러 순열 스킴(예: affine32, affine64)을 제공합니다.