# Xling: A Learned Filter Framework for Accelerating High-Dimensional Approximate Similarity Join

arXiv: https://arxiv.org/abs/2402.13397 · HTML: https://mlsanity.com/paper/2402.13397/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 51 references that are in the map.
- First posted on arXiv 20 Feb 2024.

## Builds on (most cited first, 15 of 15)

- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [The Case for Learned Index Structures](https://mlsanity.com/paper/1712.01208/) (2017)
- [Practical and Optimal LSH for Angular Distance](https://mlsanity.com/paper/1509.02897/) (2015)
- [A Model for Learned Bloom Filters, and Optimizing by Sandwiching](https://mlsanity.com/paper/1901.00902/) (2019)
- [Efficient Joinable Table Discovery in Data Lakes: A High-Dimensional Similarity-Based Approach](https://mlsanity.com/paper/2010.13273/) (2020)
- [Serving Deep Learning Models with Deduplication from Relational Databases](https://mlsanity.com/paper/2201.10442/) (2022)
- [LIDER: An Efficient High-dimensional Learned Index for Large-scale Dense Passage Retrieval](https://mlsanity.com/paper/2205.00970/) (2022)
- [Consistent and Flexible Selectivity Estimation for High-Dimensional Data](https://mlsanity.com/paper/2005.09908/) (2020)
- [Monotonic Cardinality Estimation of Similarity Selection: A Deep Learning Approach](https://mlsanity.com/paper/2002.06442/) (2020)
- [It's AI Match: A Two-Step Approach for Schema Matching Using Embeddings](https://mlsanity.com/paper/2203.04366/) (2022)
- [EmbedJoin: Efficient Edit Similarity Joins via Embeddings](https://mlsanity.com/paper/1702.00093/) (2017)
- [Place Deduplication with Embeddings](https://mlsanity.com/paper/1910.04861/) (2019)
- [Distance Sensitive Bloom Filters Without False Negatives](https://mlsanity.com/paper/1607.05451/) (2016)
- [Em-K Indexing for Approximate Query Matching in Large-scale ER](https://mlsanity.com/paper/2111.04070/) (2021)
- [Learned Accelerator Framework for Angular-Distance-Based High-Dimensional DBSCAN](https://mlsanity.com/paper/2302.03136/) (2023)

## Abstract (arXiv)

Similarity join finds all pairs of close points within a given distance threshold. Many similarity join methods have been proposed, but they are usually not efficient on high-dimensional space due to the curse of dimensionality and data-unawareness. We investigate the possibility of using metric space Bloom filter (MSBF), a family of data structures checking if a query point has neighbors in a multi-dimensional space, to speed up similarity join. However, there are several challenges when applying MSBF to similarity join, including excessive information loss, data-unawareness and hard constraint on the distance metric. In this paper, we propose Xling, a generic framework to build a learning-based metric space filter with any existing regression model, aiming at accurately predicting whether a query point has enough number of neighbors. The framework provides a suite of optimization strategies to further improve the prediction quality based on the learning model, which has demonstrated significantly higher prediction quality than existing MSBF. We also propose XJoin, one of the first filter-based similarity join methods, based on Xling. By predicting and skipping those queries without enough neighbors, XJoin can effectively reduce unnecessary neighbor searching and therefore it achieves a remarkable acceleration. Benefiting from the generalization capability of deep learning models, XJoin can be easily transferred onto new dataset (in similar distribution) without re-training. Furthermore, Xling is not limited to being applied in XJoin, instead, it acts as a flexible plugin that can be inserted to any loop-based similarity join methods for a speedup.