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.6173605e-05
Overall Rank: 7,030 | 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,654	Falcon: Scaling Up Hands-Off Crowdsourced Entity Matching to Build Cloud Services	2017	SIGMOD	9.9739611e-05
4,107	Smurf: Self-Service String Matching Using Random Forests	2019	VLDB	6.8026037e-05
4,147	Local Similarity Search for Unstructured Text	2016	SIGMOD	6.7803631e-05
4,688	Learned Cardinality Estimation for Similarity Queries	2021	SIGMOD	6.4697463e-05
5,276	MATE: Multi-Attribute Table Extraction	2022	VLDB	6.2002884e-05
6,397	Human-in-the-loop Data Integration	2017	VLDB	5.7989499e-05
9,126	Balance-Aware Distributed String Similarity-Based Query Processing System	2019	VLDB	5.22387e-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.0003305531
125	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD	0.00030470848
262	Record Linkage: Similarity Measures and Algorithms	2006	SIGMOD	0.00022821392
929	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00013020115
963	Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search	2012	SIGMOD	0.00012816649
1,061	VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams	2007	VLDB	0.00012213729
1,307	Entity Resolution with Iterative Blocking	2009	SIGMOD	0.000110838
1,933	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB	9.3459285e-05
2,072	Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance	2010	SIGMOD	9.0864612e-05
2,220	String Similarity Joins: An Experimental Evaluation	2014	VLDB	8.8146984e-05
3,255	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD	7.4890984e-05
3,816	Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints	2010	VLDB	7.0072547e-05
4,439	Incremental Maintenance of Length Normalized Indexes for Approximate String Matching	2009	SIGMOD	6.5998035e-05
6,605	A Pivotal Prefix Based Filtering Algorithm for String Similarity Search	2014	SIGMOD	5.7367357e-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,110	Efficient and Tunable Similar Set Retrieval	2001	SIGMOD
3	3,816	Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints	2010	VLDB
4	6,973	A Scalable Index for Top-k Subtree Similarity Queries	2019	SIGMOD
5	8,408	Fast Approximate Similarity Join in Vector Databases	2025	SIGMOD
6	6,137	Scaling Similarity Joins over Tree-Structured Data	2015	VLDB
7	3,108	Similarity Evaluation on Tree-structured Data	2005	SIGMOD
8	2,921	Leveraging Set Relations in Exact Set Similarity Join	2017	VLDB
9	201	Efficient set joins on similarity predicates	2004	SIGMOD
10	963	Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search	2012	SIGMOD