Fast Approximate Similarity Join in Vector Databases

Summary: SimJoin exploits join-window reuse to speed up approximate similarity joins in vector databases, beating per-point range queries. Join-window order optimization, k-similarity support, and a proximity-graph index; experiments show large speedups. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h6cdb73c81cc2cf1f
Venue: SIGMOD
Year: 2025
Pagerank: 5.336718e-05
Overall Rank: 8,408 | 43.47%
DOI: 10.1145/3725403

Incoming Non-self Citations Over Time

Authors

1. Jiadong Xie (Chinese University of Hong Kong)
2. Jeffrey Xu Yu (Chinese University of Hong Kong)
3. Yingfan Liu (Xidian University)

BibTeX Citation

@inproceedings{xie_sigmod25,
        title = {{Fast Approximate Similarity Join in Vector Databases}},
        author = {Xie, Jiadong and Yu, Jeffrey Xu and Liu, Yingfan},
        series = {{SIGMOD} '25},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3725403},
        url = {https://dl.acm.org/doi/10.1145/3725403},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,608	MorphingDB: A Task-Centric AI-Native DBMS for Model Management and Inference	2026	SIGMOD	4.9793485e-05
10,910	TEngineDB-V: An OLAP-Native Vector Search System for Large-k Workloads at Tencent	2026	VLDB	4.9793485e-05
11,028	Advances of Query Processing in Vector Databases	2026	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
74	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00037091678
146	Efficient Processing of Spatial Joins Using R-trees	1993	SIGMOD	0.00029061754
194	Milvus: A Purpose-Built Vector Data Management System	2021	SIGMOD	0.00025636725
345	A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search	2021	VLDB	0.00020445545
804	RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search	2024	SIGMOD	0.00013832333
1,170	Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases	2023	SIGMOD	0.0001171991
1,421	V-SMART-Join: A Scalable MapReduce Framework for All-Pair Similarity Joins of Multisets and Vectors	2012	VLDB	0.00010726757
1,996	Epsilon Grid Order: An Algorithm for the Similarity Join on Massive High-Dimensional Data	2001	SIGMOD	9.216723e-05
2,362	Streaming Similarity Search over one Billion Tweets using Parallel Locality-Sensitive Hashing	2013	VLDB	8.5746436e-05
2,464	Output-optimal Parallel Algorithms for Similarity Joins	2017	PODS	8.4260608e-05
4,050	Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search	2025	VLDB	6.8298981e-05
7,560	Cache-oblivious High-performance Similarity Join	2019	SIGMOD	5.4962229e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,030	Efficient Similarity Join and Search on Multi-Attribute Data	2015	SIGMOD
2	2,382	DeepJoin: Joinable Table Discovery with Pre-trained Language Models	2023	VLDB
3	2,921	Leveraging Set Relations in Exact Set Similarity Join	2017	VLDB
4	9,628	Efficient and Accurate SimRank-based Similarity Joins: Experiments, Analysis, and Improvement	2024	VLDB
5	201	Efficient set joins on similarity predicates	2004	SIGMOD
6	11,497	Similarity Joins of Sparse Features	2024	SIGMOD
7	9,905	DiskJoin: Large-scale Vector Similarity Join with SSD	2026	SIGMOD
8	11,339	Extensible and Robust Evaluation of Similarity Queries	2025	VLDB
9	13,985	Exploiting Database Similarity Joins for Metric Spaces	2012	VLDB
10	4,150	Efficient Top-K SimRank-based Similarity Join	2015	VLDB