이론적 보장을 가진 겹침 집합 유사성 조인

이 논문은 두 집합 모음과 상수 c가 주어졌을 때, c개의 공통 요소를 공유하는 데이터 세트 내 모든 집합 쌍을 찾는 겹침 제약이 있는 집합 유사성 조인 문제를 연구합니다. 이는 정보 검색, 데이터 마이닝 및 기계 학습 등 많은 분야에서 기본적인 작업입니다. 기존 방법의 모든 시간 복잡도는 O(n²)이며, 여기서 n은 모든 집합의 총 크기입니다. 본 논문에서는 O(n² - 1/c * k^(1/2c)) = o(n²) + O(k)의 시간 복잡도를 가진 크기 인식 알고리즘을 제안합니다. 여기서 k는 결과의 수입니다. 크기 인식 알고리즘은 모든 집합을 크기에 따라 작고 큰 집합으로 나누고 별도로 처리합니다. 우리는 기존 방법을 사용하여 큰 집합을 처리하고, 이 논문에서 작은 집합에 집중할 수 있습니다. 작은 집합의 실제 성능을 크게 개선하기 위해 여러 최적화 휴리스틱을 개발했습니다. 작은 집합과 큰 집합 사이의 크기 경계는 효율성에 중요한 요소이므로, 적절한 크기 경계를 신중하게 선택하는 효과적인 경계 선택 알고리즘을 제안합니다. 이는 실제에 매우 잘 작동합니다. 실제 데이터 세트에 대한 실험 결과는 우리의 방법이 높은 성능을 달성하고 최첨단 접근 방식을 최대 한 자릿수까지 초월함을 보여줍니다.