Nexus: 메타데이터만을 이용하여 반복적인 저차원 행렬 완성 기법을 통해 조인 그래프 추론

Nexus: Inferring Join Graphs from Metadata Alone via Iterative Low-Rank Matrix Completion

자동으로 조인 관계를 추론하는 것은 효과적인 데이터 검색, 통합, 질의 및 재사용을 위한 중요한 과제입니다. 그러나 특히 데이터 값에 대한 접근이 제한적인 기업 환경에서 대규모 및 복잡한 스키마에서 이러한 관계를 정확하고 효율적으로 식별하는 것은 어려울 수 있습니다. 본 논문에서는 메타데이터만 사용할 수 있는 경우 조인 그래프 추론 문제를 제안합니다. 실제 스키마의 대규모 데이터 세트에 대한 경험적 연구를 수행한 결과, 조인 그래프를 인접 행렬로 표현할 때 두 가지 중요한 특징을 나타냅니다. 즉, 높은 희소성과 저차원 구조입니다. 이러한 새로운 관찰을 바탕으로, 조인 그래프 추론을 저차원 행렬 완성 문제로 정의하고, 메타데이터만 사용하는 엔드 투 엔드 솔루션인 Nexus를 제안합니다. 정확도를 더욱 향상시키기 위해, 대규모 언어 모델을 활용하여 저차원 행렬 완성 및 조인 후보 확률을 개선하는 새로운 Expectation-Maximization 알고리즘을 제안합니다. 광범위한 실험 결과, Nexus는 실제 생산 데이터 세트를 포함한 네 가지 데이터 세트에서 기존 방법보다 훨씬 뛰어난 성능을 보였습니다. 또한, Nexus는 빠른 모드로 작동하여 최대 6배의 속도 향상을 제공하며, 실제 환경에 적용하기 위한 실용적이고 효율적인 솔루션을 제공합니다.

Automatically inferring join relationships is a critical task for effective data discovery, integration, querying and reuse. However, accurately and efficiently identifying these relationships in large and complex schemas can be challenging, especially in enterprise settings where access to data values is constrained. In this paper, we introduce the problem of join graph inference when only metadata is available. We conduct an empirical study on a large number of real-world schemas and observe that join graphs when represented as adjacency matrices exhibit two key properties: high sparsity and low-rank structure. Based on these novel observations, we formulate join graph inference as a low-rank matrix completion problem and propose Nexus, an end-to-end solution using only metadata. To further enhance accuracy, we propose a novel Expectation-Maximization algorithm that alternates between low-rank matrix completion and refining join candidate probabilities by leveraging Large Language Models. Our extensive experiments demonstrate that Nexus outperforms existing methods by a significant margin on four datasets including a real-world production dataset. Additionally, Nexus can operate in a fast mode, providing comparable results with up to 6x speedup, offering a practical and efficient solution for real-world deployments.