CRAFT: Corpus Relatedness Analysis using Fourier Transforms

Abstract

A fundamental challenge in data management is the efficient discovery of term relationships from massive, unstructured text corpora—a critical first step in knowledge-graph construction. This discovery task faces prohibitive computational barriers: the quadratic O ( N 2 ) complexity of an all-pairs analysis and the intractability of processing the full term-document matrix. While dimensionality reduction via embeddings offers a partial solution, the resulting vector proximity often captures broad thematic similarity, failing to isolate the precise co-occurrence signals required for high-quality relation extraction. This paper introduces CRAFT, a system that overcomes these limitations by recasting term-relatedness discovery as a scalable signal-processing problem. CRAFT's methodology decouples the discovery process from both the term-document matrix and quadratic-time comparisons. First, it employs a randomized Fourier transform to sketch term-occurrence signals directly into a low-dimensional complex space, a process that provably preserves the inner products essential for correlation analysis without materializing the underlying matrix. Second, to break the quadratic barrier, CRAFT leverages the inherent sparsity of term relationships by formulating discovery as a compressed-sensing task. This enables the recovery of significant correlations for any given term directly from its compressed sketch via an efficient Orthogonal Matching Pursuit algorithm, obviating the need for an all-pairs comparison. Our end-to-end implementation and comprehensive experimental evaluation show that CRAFT outperforms modern baselines in both efficiency and precision, enabling high-quality relation discovery at a previously infeasible scale.