Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme

Summary: Establishes tau+1 as the minimum signature size for exact edit-distance query processing and introduces asymmetric signature schemes that achieve this bound. Proposes fast query processing algorithms and DP-based pruning; empirically beats state-of-the-art across nine baselines. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 4514
Venue: SIGMOD
Year: 2011
Pagerank: 7.649474e-05
Overall Rank: 3,193 | 78.10%
DOI: 10.1145/1989323.1989431

Incoming Non-self Citations Over Time

Authors

1. Jianbin Qin (University of New South Wales)
2. Wei Wang (University of New South Wales)
3. Yifei Lu (University of New South Wales)
4. Chuan Xiao (University of New South Wales)
5. Xuemin Lin (East China Normal University; University of New South Wales)

BibTeX Citation

@inproceedings{qin_sigmod11,
        title = {{Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme}},
        author = {Qin, Jianbin and Wang, Wei and Lu, Yifei and Xiao, Chuan and Lin, Xuemin},
        series = {{SIGMOD} '11},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1989323.1989431},
        url = {https://dl.acm.org/doi/10.1145/1989323.1989431},
        year = {2011}
}

Incoming Citations (Sorted by Pagerank)

Showing 18 of 18 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
975	Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search	2012	SIGMOD	0.00012870645
2,186	String Similarity Joins: An Experimental Evaluation	2014	VLDB	9.0001436e-05
4,052	Local Similarity Search for Unstructured Text	2016	SIGMOD	6.935988e-05
4,396	Approximate String Joins with Abbreviations	2018	VLDB	6.7268636e-05
5,071	Fast Subtrajectory Similarity Search in Road Networks under Weighted Edit Distance Constraints	2020	VLDB	6.3761034e-05
5,088	String Similarity Measures and Joins with Synonyms	2013	SIGMOD	6.3673276e-05
5,726	Pigeonring: A Principle for Faster Thresholded Similarity Search	2019	VLDB	6.1079184e-05
6,484	A Pivotal Prefix Based Filtering Algorithm for String Similarity Search	2014	SIGMOD	5.8665833e-05
6,906	Efficient Similarity Join and Search on Multi-Attribute Data	2015	SIGMOD	5.7418509e-05
7,031	Efficient Error-tolerant Query Autocompletion	2013	VLDB	5.72252e-05
7,476	SyncSignature: A Simple, Efficient, Parallelizable Framework for Tree Similarity Joins	2023	VLDB	5.6090634e-05
9,705	META: An Efficient Matching-Based Method for Error-Tolerant Autocompletion	2016	VLDB	5.2351259e-05
10,085	Local Filtering: Improving the Performance of Approximate Queries on String Collections	2015	SIGMOD	5.1559617e-05
10,086	Efficient and Effective KNN Sequence Search with Approximate n-grams	2014	VLDB	5.1559617e-05
10,359	DiskJoin: Large-scale Vector Similarity Join with SSD	2026	SIGMOD	5.093636e-05
10,951	Extensible and Robust Evaluation of Similarity Queries	2025	VLDB	5.093636e-05
11,504	TokenJoin: Efficient Filtering for Set Similarity Join with Maximum Weighted Bipartite Matching	2023	VLDB	5.093636e-05
11,929	ZigZag: Supporting Similarity Queries on Vector Space Models	2018	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
2	R-Trees: A Dynamic Index Structure For Spatial Searching	1984	SIGMOD	0.0020210012
21	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00056760516
56	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.00040719947
107	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.00033511706
169	Efficient Exact Set-Similarity Joins	2006	VLDB	0.0002743469
200	Efficient set joins on similarity predicates	2004	SIGMOD	0.00025597287
911	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00013283031
1,040	VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams	2007	VLDB	0.00012466499
1,701	Extending Autocompletion To Tolerate Errors	2009	SIGMOD	9.9707165e-05
2,036	Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance	2010	SIGMOD	9.2782094e-05
2,103	Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently	2008	SIGMOD	9.1621686e-05
3,446	Efficient Approximate Entity Extraction with Edit Distance Constraints	2009	SIGMOD	7.4087786e-05
3,731	Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints	2010	VLDB	7.1663952e-05
4,112	Efficient and Effective Similarity Search over Probabilistic Data based on Earth Mover's Distance	2010	VLDB	6.8944534e-05
4,776	An Efficient Index Structure for String Databases	2001	VLDB	6.513844e-05
5,667	Efficient Approximate Search on String Collections (Tutorial)	2009	VLDB	6.1279762e-05
7,708	Similarity Search on Bregman Divergence: Towards Non-Metric Indexing	2009	VLDB	5.5628618e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,047	Similarity Evaluation on Tree-structured Data	2005	SIGMOD
2	8,078	Indexing Mixed Types for Approximate Retrieval	2005	VLDB
3	10,086	Efficient and Effective KNN Sequence Search with Approximate n-grams	2014	VLDB
4	6,832	A Scalable Index for Top-k Subtree Similarity Queries	2019	SIGMOD
5	2,036	Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance	2010	SIGMOD
6	911	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB
7	6,496	Reference-Based Indexing of Sequence Databases	2006	VLDB
8	10,085	Local Filtering: Improving the Performance of Approximate Queries on String Collections	2015	SIGMOD
9	6,484	A Pivotal Prefix Based Filtering Algorithm for String Similarity Search	2014	SIGMOD
10	7,692	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD