Efficient Similarity Join and Search on Multi-Attribute Data

Summary: Introduces a prefix tree index enabling holistic pruning across multiple attributes for similarity join and search. With a cost model, greedy and budget-based multi-tree strategies plus a hybrid verifier yield strong empirical gains. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4954
Venue: SIGMOD
Year: 2015
Pagerank: 4.8250163e-05
Overall Rank: 7,106 | 50.62%
DOI: 10.1145/2723372.2723733

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,176	Falcon: Scaling Up Hands-Off Crowdsourced Entity Matching to Build Cloud Services	2017	SIGMOD	9.3729351e-05
4,247	Local Similarity Search for Unstructured Text	2016	SIGMOD	6.3180334e-05
4,397	Smurf: Self-Service String Matching Using Random Forests	2019	VLDB	6.2142485e-05
5,477	Learned Cardinality Estimation for Similarity Queries	2021	SIGMOD	5.4856699e-05
6,268	MATE: Multi-Attribute Table Extraction	2022	VLDB	5.1288179e-05
7,667	Human-in-the-loop Data Integration	2017	VLDB	4.6791871e-05
9,831	Balance-Aware Distributed String Similarity-Based Query Processing System	2019	VLDB	4.2710095e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
125	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.00044946098
140	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD	0.00042289025
321	Record Linkage: Similarity Measures and Algorithms	2006	SIGMOD	0.00027524716
1,203	VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams	2007	VLDB	0.00013317317
1,232	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00013133604
1,396	Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search	2012	SIGMOD	0.00012215253
1,408	Entity Resolution with Iterative Blocking	2009	SIGMOD	0.00012162791
2,387	Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance	2010	SIGMOD	8.9075095e-05
2,588	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB	8.4872437e-05
2,729	String Similarity Joins: An Experimental Evaluation	2014	VLDB	8.2175463e-05
3,779	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD	6.7709545e-05
4,215	Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints	2010	VLDB	6.3464157e-05
4,878	Incremental Maintenance of Length Normalized Indexes for Approximate String Matching	2009	SIGMOD	5.8537044e-05
6,730	A Pivotal Prefix Based Filtering Algorithm for String Similarity Search	2014	SIGMOD	4.9436522e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,041	An Efficient Partition Based Method for Exact Set Similarity Joins	2016	VLDB	6.5048916e-05
7,521	Efficient and Tunable Similar Set Retrieval	2001	SIGMOD	4.7135369e-05
4,215	Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints	2010	VLDB	6.3464157e-05
5,624	A Scalable Index for Top-k Subtree Similarity Queries	2019	SIGMOD	5.4049016e-05
8,899	Fast Approximate Similarity Join in Vector Databases	2025	SIGMOD	4.4229886e-05
6,240	Scaling Similarity Joins over Tree-Structured Data	2015	VLDB	5.1362097e-05
3,206	Similarity Evaluation on Tree-structured Data	2005	SIGMOD	7.3855924e-05
3,461	Leveraging Set Relations in Exact Set Similarity Join	2017	VLDB	7.0696567e-05
248	Efficient set joins on similarity predicates	2004	SIGMOD	0.00030888982
1,396	Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search	2012	SIGMOD	0.00012215253