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: 5015
Venue: SIGMOD
Year: 2015
Pagerank: 5.7418509e-05
Overall Rank: 6,906 | 52.62%
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,643	Falcon: Scaling Up Hands-Off Crowdsourced Entity Matching to Build Cloud Services	2017	SIGMOD	0.00010134956
4,023	Smurf: Self-Service String Matching Using Random Forests	2019	VLDB	6.949387e-05
4,052	Local Similarity Search for Unstructured Text	2016	SIGMOD	6.935988e-05
4,617	Learned Cardinality Estimation for Similarity Queries	2021	SIGMOD	6.604437e-05
5,479	MATE: Multi-Attribute Table Extraction	2022	VLDB	6.204351e-05
7,493	Human-in-the-loop Data Integration	2017	VLDB	5.6046905e-05
9,979	Balance-Aware Distributed String Similarity-Based Query Processing System	2019	VLDB	5.1845938e-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
107	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.00033511706
132	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD	0.00030378624
254	Record Linkage: Similarity Measures and Algorithms	2006	SIGMOD	0.00023199211
911	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00013283031
975	Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search	2012	SIGMOD	0.00012870645
1,040	VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams	2007	VLDB	0.00012466499
1,293	Entity Resolution with Iterative Blocking	2009	SIGMOD	0.00011292804
1,886	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB	9.5358137e-05
2,036	Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance	2010	SIGMOD	9.2782094e-05
2,186	String Similarity Joins: An Experimental Evaluation	2014	VLDB	9.0001436e-05
3,193	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD	7.649474e-05
3,731	Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints	2010	VLDB	7.1663952e-05
4,359	Incremental Maintenance of Length Normalized Indexes for Approximate String Matching	2009	SIGMOD	6.7451753e-05
6,484	A Pivotal Prefix Based Filtering Algorithm for String Similarity Search	2014	SIGMOD	5.8665833e-05

Semantically Similar Papers

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