배치형 오라클 쿼리를 통한 개체 해상도 (Entity Resolution)

우리는 한 번에 제한된 레코드 배치를 처리하고, 동일한 실제 세계의 개체 (entity)를 참조하는 것들을 클러스터링 (clustering)하는 오라클 (oracle)을 고려합니다. 우리는 단일 배치보다 훨씬 더 큰 크기의 데이터셋에서, 그리고 특정 개체의 모든 레코드가 포함된 배치가 보장되지 않는 상황에서, 이러한 오라클을 어떻게 질의하여 개체를 해상 (resolve)할 것인지 연구합니다. 우리는 매 단계에서 가능한 최고의 재현율 (recall)을 달성하는 동시에, 비용 (오라클 호출 횟수)을 완전히 제어할 수 있는 종량제 (pay-as-you-go) 접근 방식을 목표로 합니다. 우리는 이 문제를 배치형 개체 해상도 (batched entity resolution)로 공식화하고, 최적의 배치를 선택하는 것이 NP-hard임을 증명하며, 개체 크기에 대한 자연스러운 조건 하에서 최적의 솔루션을 제공합니다. 마지막으로, 우리는 6개의 데이터셋에서 우리의 접근 방식을 평가하고 최신 기술 (state-of-the-art) 베이스라인 (baselines) 대비 우수성을 보여줍니다.