Snoopy: Effective and Efficient Semantic Join Discovery via Proxy Columns

• URL: http://arxiv.org/abs/2502.16813v1
• Date: Mon, 24 Feb 2025 03:48:00 GMT
• Title: Snoopy: Effective and Efficient Semantic Join Discovery via Proxy Columns
• Abstract summary: This paper presents a novel column-level semantic join discovery framework, Snoopy, to bridge effectiveness and efficiency.<n>Experiments on four real-world datasets demonstrate that Snoopy outperforms SOTA column-level methods by 16% in Recall@25 and 10% in NDCG@25.
• Score: 26.053055662905283
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Semantic join discovery, which aims to find columns in a table repository with high semantic joinabilities to a query column, is crucial for dataset discovery. Existing methods can be divided into two categories: cell-level methods and column-level methods. However, neither of them ensures both effectiveness and efficiency simultaneously. Cell-level methods, which compute the joinability by counting cell matches between columns, enjoy ideal effectiveness but suffer poor efficiency. In contrast, column-level methods, which determine joinability only by computing the similarity of column embeddings, enjoy proper efficiency but suffer poor effectiveness due to the issues occurring in their column embeddings: (i) semantics-joinability-gap, (ii) size limit, and (iii) permutation sensitivity. To address these issues, this paper proposes to compute column embeddings via proxy columns; furthermore, a novel column-level semantic join discovery framework, Snoopy, is presented, leveraging proxy-column-based embeddings to bridge effectiveness and efficiency. Specifically, the proposed column embeddings are derived from the implicit column-to-proxy-column relationships, which are captured by the lightweight approximate-graph-matching-based column projection.To acquire good proxy columns for guiding the column projection, we introduce a rank-aware contrastive learning paradigm. Extensive experiments on four real-world datasets demonstrate that Snoopy outperforms SOTA column-level methods by 16% in Recall@25 and 10% in NDCG@25, and achieves superior efficiency--being at least 5 orders of magnitude faster than cell-level solutions, and 3.5x faster than existing column-level methods.

Related papers

• MosaicJoin: Compact Semantic Sketches for Value-Level Join Discovery [8.85894971478123]
  Join discovery is a core task in dataset search, enabling users to find columns that can be joined with a given query column.<n>Recent approaches discover semantically joinable columns but face a fundamental trade-off.<n>We present MosaicJoin, a value-level semantic join discovery method that balances this trade-off.
  arXiv  Detail & Related papers  (2026-07-23T19:55:19Z)
• Alignment-Guided Largest Table Overlap Size Estimation [11.275866569459502]
  Fast estimation of the size of the largest overlap between tables enables blocking and query-by-table retrieval in large table repositories.<n>We propose ALORE, a scalable and domain-robust overlap ratio estimator built on three principles.<n> Experiments on multiple datasets spanning diverse domains and scales, including a large real-world corpus beyond prior benchmarks, show that ALORE outperforms the state of the art.
  arXiv  Detail & Related papers  (2026-07-03T07:38:43Z)
• HyperJoin: LLM-augmented Hypergraph Link Prediction for Joinable Table Discovery [27.204701078044252]
  We propose a large language model (LLM)-augmented Hypergraph framework for joinable table discovery.<n>Specifically, we first construct a hypergraph to model tables using both the intra-table hyperedges and the LLM-augmented inter-table hyperedges.<n>We then design HIN, a Hierarchical Interaction Network that learns expressive column representations through bidirectional message passing over columns and hyperedges.
  arXiv  Detail & Related papers  (2026-01-03T00:54:55Z)
• QJoin: Transformation-aware Joinable Data Discovery Using Reinforcement Learning [11.61186748860627]
  We introduce QJoin, a reinforcement-learning framework that learns and reuses transformation strategies across join tasks.<n>For 19,990 join tasks in NYC+Chicago open, Qjoin reduces runtime by up to 7.4% (13,747 datasets s) by using reusing.
  arXiv  Detail & Related papers  (2025-12-02T06:05:48Z)
• Gem: Gaussian Mixture Model Embeddings for Numerical Feature Distributions [2.6536517304571636]
  We propose a method called Gem (Gaussian mixture model embeddings) that creates embeddings that build on numerical value distributions from columns. We generate embeddings for three numerical data properties: distributional, statistical, and contextual. We compare Gem with several baseline methods for numeric only and numeric + context tasks, showing that Gem consistently outperforms the baselines on four benchmark datasets.
  arXiv  Detail & Related papers  (2024-10-09T23:40:58Z)
• CART: A Generative Cross-Modal Retrieval Framework with Coarse-To-Fine Semantic Modeling [53.97609687516371]
  Cross-modal retrieval aims to search for instances, which are semantically related to the query through the interaction of different modal data.<n>Traditional solutions utilize a single-tower or dual-tower framework to explicitly compute the score between queries and candidates.<n>We propose a generative cross-modal retrieval framework (CART) based on coarse-to-fine semantic modeling.
  arXiv  Detail & Related papers  (2024-06-25T12:47:04Z)
• Adaptive Retrieval and Scalable Indexing for k-NN Search with Cross-Encoders [77.84801537608651]
  Cross-encoder (CE) models which compute similarity by jointly encoding a query-item pair perform better than embedding-based models (dual-encoders) at estimating query-item relevance. We propose a sparse-matrix factorization based method that efficiently computes latent query and item embeddings to approximate CE scores and performs k-NN search with the approximate CE similarity.
  arXiv  Detail & Related papers  (2024-05-06T17:14:34Z)
• A Reinforcement-Learning-Based Multiple-Column Selection Strategy for Column Generation [33.03891490706789]
  Column generation is one of the most successful approaches for solving large-scale linear programming problems. We propose a novel reinforcement-learning-based (RL) multiple-column selection strategy. Our approach is evaluated on two sets of problems: the cutting stock problem and the graph coloring problem.
  arXiv  Detail & Related papers  (2023-12-21T11:35:10Z)
• Fair Column Subset Selection [6.004035936737586]
  We consider a setting where the matrix rows are partitioned into two groups, and the goal is to choose a subset of columns that minimizes the maximum error reconstruction of both groups. In certain scenarios it is unavoidable to choose columns separately for each group, resulting in double the expected column count. We propose a deterministic leverage-score sampling strategy for the fair setting and show that sampling a column subset of minimum size becomes NP-hard in the presence of two groups.
  arXiv  Detail & Related papers  (2023-06-07T15:00:38Z)
• Learnable Pillar-based Re-ranking for Image-Text Retrieval [119.9979224297237]
  Image-text retrieval aims to bridge the modality gap and retrieve cross-modal content based on semantic similarities. Re-ranking, a popular post-processing practice, has revealed the superiority of capturing neighbor relations in single-modality retrieval tasks. We propose a novel learnable pillar-based re-ranking paradigm for image-text retrieval.
  arXiv  Detail & Related papers  (2023-04-25T04:33:27Z)
• DeepJoin: Joinable Table Discovery with Pre-trained Language Models [10.639106014582756]
  Existing approaches target equi-joins, the most common way of combining tables for creating a unified view. Deepjoin is a deep learning model for accurate and efficient joinable table discovery. Deepjoin is even more accurate than an exact solution to semantic joins when evaluated with labels from experts.
  arXiv  Detail & Related papers  (2022-12-15T02:40:57Z)
• ECO-TR: Efficient Correspondences Finding Via Coarse-to-Fine Refinement [80.94378602238432]
  We propose an efficient structure named Correspondence Efficient Transformer (ECO-TR) by finding correspondences in a coarse-to-fine manner. To achieve this, multiple transformer blocks are stage-wisely connected to gradually refine the predicted coordinates. Experiments on various sparse and dense matching tasks demonstrate the superiority of our method in both efficiency and effectiveness against existing state-of-the-arts.
  arXiv  Detail & Related papers  (2022-09-25T13:05:33Z)
• Compactness Score: A Fast Filter Method for Unsupervised Feature Selection [66.84571085643928]
  We propose a fast unsupervised feature selection method, named as, Compactness Score (CSUFS) to select desired features. Our proposed algorithm seems to be more accurate and efficient compared with existing algorithms.
  arXiv  Detail & Related papers  (2022-01-31T13:01:37Z)
• Two-way Spectrum Pursuit for CUR Decomposition and Its Application in Joint Column/Row Subset Selection [9.649210683629127]
  The problem of simultaneous column and row subset selection is addressed in this paper. An iterative approach is proposed to capture the most structural information of columns/rows via selecting a subset of actual columns/rows. We demonstrate the application of TWSP for joint channel and sensor selection in cognitive radio networks.
  arXiv  Detail & Related papers  (2021-06-13T13:16:15Z)
• Conjoined Dirichlet Process [63.89763375457853]
  We develop a novel, non-parametric probabilistic biclustering method based on Dirichlet processes to identify biclusters with strong co-occurrence in both rows and columns. We apply our method to two different applications, text mining and gene expression analysis, and demonstrate that our method improves bicluster extraction in many settings compared to existing approaches.
  arXiv  Detail & Related papers  (2020-02-08T19:41:23Z)
• Clustering Binary Data by Application of Combinatorial Optimization Heuristics [52.77024349608834]
  We study clustering methods for binary data, first defining aggregation criteria that measure the compactness of clusters. Five new and original methods are introduced, using neighborhoods and population behavior optimization metaheuristics. From a set of 16 data tables generated by a quasi-Monte Carlo experiment, a comparison is performed for one of the aggregations using L1 dissimilarity, with hierarchical clustering, and a version of k-means: partitioning around medoids or PAM.
  arXiv  Detail & Related papers  (2020-01-06T23:33:31Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.