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: h7022027279b39015
Venue: SIGMOD
Year: 2015
Pagerank: 5.6147056e-05
Overall Rank: 7,032 | 52.74%
DOI: 10.1145/2723372.2723733

Incoming Non-self Citations Over Time

Authors

1. Guoliang Li (Tsinghua University)
2. Jian He (Tsinghua University)
3. Dong Deng (Tsinghua University)
4. Jian Li (Tsinghua University)

BibTeX Citation

@inproceedings{li_sigmod15,
        title = {{Efficient Similarity Join and Search on Multi-Attribute Data}},
        author = {Li, Guoliang and He, Jian and Deng, Dong and Li, Jian},
        series = {{SIGMOD} '15},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2723372.2723733},
        url = {https://dl.acm.org/doi/10.1145/2723372.2723733},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,655	Falcon: Scaling Up Hands-Off Crowdsourced Entity Matching to Build Cloud Services	2017	SIGMOD	9.9694129e-05
4,109	Smurf: Self-Service String Matching Using Random Forests	2019	VLDB	6.7994518e-05
4,147	Local Similarity Search for Unstructured Text	2016	SIGMOD	6.7771533e-05
4,690	Learned Cardinality Estimation for Similarity Queries	2021	SIGMOD	6.4667478e-05
5,279	MATE: Multi-Attribute Table Extraction	2022	VLDB	6.1973533e-05
6,400	Human-in-the-loop Data Integration	2017	VLDB	5.7962311e-05
9,136	Balance-Aware Distributed String Similarity-Based Query Processing System	2019	VLDB	5.2213971e-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
108	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.00033040246
125	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD	0.00030462671
262	Record Linkage: Similarity Measures and Algorithms	2006	SIGMOD	0.00022811258
929	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00013014029
965	Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search	2012	SIGMOD	0.00012810695
1,062	VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams	2007	VLDB	0.00012208031
1,307	Entity Resolution with Iterative Blocking	2009	SIGMOD	0.00011078699
1,934	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB	9.341845e-05
2,074	Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance	2010	SIGMOD	9.0821759e-05
2,223	String Similarity Joins: An Experimental Evaluation	2014	VLDB	8.8105347e-05
3,256	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD	7.4855571e-05
3,817	Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints	2010	VLDB	7.0039415e-05
4,441	Incremental Maintenance of Length Normalized Indexes for Approximate String Matching	2009	SIGMOD	6.5966903e-05
6,608	A Pivotal Prefix Based Filtering Algorithm for String Similarity Search	2014	SIGMOD	5.73402e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,350	An Efficient Partition Based Method for Exact Set Similarity Joins	2016	VLDB
2	8,117	Efficient and Tunable Similar Set Retrieval	2001	SIGMOD
3	3,817	Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints	2010	VLDB
4	6,974	A Scalable Index for Top-k Subtree Similarity Queries	2019	SIGMOD
5	8,416	Fast Approximate Similarity Join in Vector Databases	2025	SIGMOD
6	6,140	Scaling Similarity Joins over Tree-Structured Data	2015	VLDB
7	3,110	Similarity Evaluation on Tree-structured Data	2005	SIGMOD
8	2,923	Leveraging Set Relations in Exact Set Similarity Join	2017	VLDB
9	201	Efficient set joins on similarity predicates	2004	SIGMOD
10	965	Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search	2012	SIGMOD