beowolx/rensa

해결하는 문제

Rensa는 대규모 데이터 세트 간의 유사성을 추정하고, 유사한 중복 문서를 식별하는 고성능 방법을 제공합니다. datasketch 및 FastSketch와 같은 기존 라이브러리보다 훨씬 빠른 대안으로 설계되었습니다.

작동 방식

Rensa는 랜덤 해시 함수를 사용하여 집합의 컴팩트한 "서명"을 생성하는 MinHash를 구현합니다. 두 서명 간의 일치하는 슬롯 비율이 원래 집합의 자카르드 유사도를 추정합니다.

Rensa는 두 가지 변형을 제공합니다:

• R-MinHash: 모듈러 감소 대신 곱셈-시프트 해싱(64비트 곱셈-덧셈의 상위 32비트 사용)을 사용하는 고유한 변형으로, CPU 오버헤드와 메모리 사용량을 줄입니다.
• C-MinHash: 공식 논문 기반의 변형으로, 더 작은 파라미터 세트에서 두 단계 기법을 사용해 여러 슬롯을 유도하여 더 엄격한 분산 한계를 제공합니다.

이 프로젝트는 Rust로 작성되었으며 Python 바인딩을 제공하며, 비암호화 해싱, 요소의 배치 처리, MiMalloc 할당자 사용과 같은 여러 저수준 최적화를 적용했습니다.

대상 사용자

표준 Python 구현이 너무 느린 대규모 데이터셋에서 유사성 추정 또는 중복 검출이 필요한 데이터 엔지니어 및 ML 실무자

주요 특징

• 극도의 속도: datasketch보다 최대 608배 빠르고, FastSketch보다 11배 빠릅니다.
• 메모리 효율성: R-MinHash 서명은 32비트 정수를 사용하여 64비트 구현 대비 메모리 요구량을 절반으로 줄입니다.
• LSH 통합: 모든 쌍을 비교하지 않고도 효율적인 후보 검색을 위한 국소 민감성 해싱(LSH)을 포함합니다.
• 스트리밍 지원: 지속적인 데이터 스트림용 내장 중복 제거 기능을 제공합니다.
• 유연한 API: 일괄 처리와 인크리멘탈 업데이트 모두를 지원합니다.