SimilaritySearch.jl

유사성 검색 .JL

유사성 검색 .jl은 가장 가까운 이웃 검색을위한 라이브러리입니다. 특히, 메트릭 함수를 사용하는 빠르고 유연한 검색 인덱스 인 SearchGraph, 의 구현이 포함되어 있습니다. 대부분의 기능 및 구조에서 멀티 스레딩을 지원하도록 설계되었습니다.

패키지는 다음과 같은 색인을 제공합니다.

• ParallelExhaustiveSearch : 각 쿼리가 사용 가능한 모든 스레드를 사용하여 해결되는 무차별 인력 검색 인덱스.
• ExhaustiveSearch : 무차별 인력 검색 인덱스, 각 쿼리는 단일 스레드를 사용하여 해결됩니다.
• SearchGraph : 병렬 구성이있는 대략적인 검색 지수.

주요 함수 세트는 다음과 같습니다.

• search : 단일 쿼리를 해결합니다.
• searchbatch : 일련의 쿼리를 해결합니다.
• allknn : 계산 $ k $ 인덱스의 모든 요소에 가장 가까운 이웃.
• neardup : 메트릭 데이터 세트에서 거의 중독성을 제거합니다.
• closestpair : 메트릭 데이터 세트에서 가장 가까운 쌍을 계산합니다.

이러한 기능의 정확한 정의와 전체 기능 및 구조 세트는 문서에서 찾을 수 있습니다.

Julia의 유사성 검색 생태계

현재 가장 가까운 이웃 검색 전용 패키지가 있습니다. 예를 들어 NearestNeighbors.jl 이웃 보어 (Jl), RegionTrees.jl 와 JuliaNeighbors 는 KD-Tree, 볼 트리, 오트리, BK 트리, VP- 트리 및 기타 다차원 및 메트릭 구조와 같은 검색 구조를 구현합니다. 이 구조는 정확한 유사성 쿼리를 해결하도록 설계되었으므로 저 차원 데이터에 매우 잘 작동합니다.

FAISS 라이브러리 Faiss.jl 의 래퍼 인 제품 정량화 체계를 사용하는 Rayuela.jl 과 같은 대략적인 유사성 검색을 수행하는 몇 가지 패키지가 있습니다. FAISS 라이브러리는 HNSW 지수의 산업 강도 구현과 함께 제품 양자화 체계 및 지역에 민감한 해싱 체계의 고성능 구현을 제공합니다. NearestNeighborDescent.jl pynndescent 뒤에있는 검색 알고리즘을 구현합니다.

SimilaritySearch.jl .JL 패키지는 멀티 스레딩 시스템과 실무자를위한 사용을 단순화하는 독특한 자동 조정 기능을 활용하도록 설계된 검색 구조 및 알고리즘으로 생태계를 풍부하게하려고합니다. 이러한 기능은 Julia 프로그래밍 언어 역학 및 성능으로 인해 간결하고 효율적으로 구현됩니다. 성능 특성과 관련하여, 검색 성능이나 결과 품질을 줄이지 않고 유사한 접근법에 비해 시공 시간이 크게 줄어 듭니다.

유사성 검색 설치

패키지를 다음과 같이 설치할 수 있습니다

] add SimilaritySearch . jl

또한 다음과 같이 테스트 세트를 실행할 수 있습니다.

] test SimilaritySearch

도서관 사용

예제를 참조하십시오. Jupyter 및 Pluto 노트북 목록과 사용법을 보여주는 일부 스크립트를 찾을 수 있습니다.

기여하다

기부금을 환영합니다. 문서화 및 구현 기부금에 대한 풀 요청을 작성하십시오. 문제는 필요한 정보로 문제를 작성하십시오 (아래 참조) 이미 솔루션이있는 경우 풀 요청도 제공하십시오.

문제

최소한의 재현 가능한 예를 제공하는 패키지의 문제를보고합니다. 문제가 데이터 의존적 인 경우, 재생산에 필요한 데이터를 제공하는 것을 잊지 마십시오.

SearchGraph 의 한계

주요 검색 구조 인 SearchGraph, 몇 가지 특성을 가진 그래프이며, 그 중 다수는 데이터 세트가 인덱싱되는 것으로 유발됩니다. 알려진 한계 중 일부는 이러한 특성과 관련이 있습니다. 예를 들어:

• 메트릭 거리는 잘 작동합니다. 반면에 반 메트릭은 작동해야하지만 라우팅 기능은 아직 특성화되지 않습니다.
• 대안에 비해 꽤 잘 수행 되더라도 Levenshtein 거리와 같은 개별 메트릭 및 가능한 값이 거의없는 다른 사람들도 낮은 성능을 얻을 수 있습니다.
• 거의 다중 복제물 ( 매우 가까운 요소)이있을 때 비슷한 일이 발생합니다. 이 경우, 거의 다중 복제물을 제거하고 근처 물체와 관련된 가방 에 넣어야합니다.
• 매우 높은 차원의 데이터 세트는 정점 당 모서리 수의 긴 꼬리 분포를 생성합니다. 극단적 인 경우, 당신은 넓은 동네를 가지며 단일 엣지 경로를 풍요롭게해야합니다.

구조 및 알고리즘에 대해

다음 원고는 SearchGraph 지수 (패키지 버전 0.6 )를 설명하고 벤치마킹합니다.

 @article{tellezscalable,
  title={A scalable solution to the nearest neighbor search problem through local-search methods on neighbor graphs},
  author={Tellez, Eric S and Ruiz, Guillermo and Chavez, Edgar and Graff, Mario},
  journal={Pattern Analysis and Applications},
  pages={1--15},
  publisher={Springer}
}

현재 알고리즘 (버전 0.8 및 0.9 )은 다음 원고에서 설명되고 벤치마킹됩니다.

@misc{tellez2022similarity,
      title={Similarity search on neighbor's graphs with automatic Pareto optimal performance and minimum expected quality setups based on hyperparameter optimization}, 
      author={Eric S. Tellez and Guillermo Ruiz},
      year={2022},
      eprint={2201.07917},
      archivePrefix={arXiv},
      primaryClass={cs.IR}
}

이 패키지는 Joss 논문에도 설명되어 있습니다.

Eric S. Tellez와 Guillermo Ruiz. SimilaritySearch.jl : Julia의 가장 가까운 이웃 인덱스를 자동으로 튜닝했습니다 . 오픈 소스 소프트웨어 저널 https://doi.org/10.21105/joss.04442.

약 v0.9.x 시리즈

이 버전의 알고리즘은 v0.8과 동일하지만 API 호환성을 중단합니다.

• 이제 Polyester 패키지를 사용하여 스레드 대신 멀티 스레딩을 처리합니다.@Threads
• 프로세스가 여러 스레드로 시작되면 다중 스레딩 메소드가 기본적으로 활성화됩니다. V0.8에서는 반대였습니다
• allknn 이제 알고리즘을 단순화하고 효율성을 향상시키기 위해 자체 참조를 보존합니다 (V0.8의 allknn 자동으로 자체 참조를 제거합니다)

기타 :

• 기능 문서 및 벤치 마크를 추가합니다
• SearchGraph 그래프 가지 치기 방법을 추가합니다
• timedsearchbatch 함수를 제거합니다

약 v0.10.x 시리즈

SearchGraph 구조를 다양한 워크로드 및 응용 프로그램으로 쉽게 조정할 수 있습니다. 예를 들어,

• 시공 매개 변수에 대한 더 많은 제어
• 로드 및 저장
• REFACTORS는 Structs에서 일관되도록 API를 검색합니다

작업 예제에 대해서는 https://github.com/sadit/samilitysearchdemos 및 https://github.com/sadit/simalitysearch.jl/blob/main/testsearchgraph.jl을 참조하십시오.

약 v0.11 시리즈

주요 리팩토링을 소개합니다. 특히, 대부분의 기능에 대해 컨텍스트 객체를 명시 적으로 사용합니다. 또한 간단한 로깅 절차도 소개합니다. 그러나 기본 컨텍스트 객체의 암시 적 사용을 사용하여 많은 공개 기능에서 호환성을 보존합니다.