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: hd5645068da78aa7a
Venue: SIGMOD
Year: 2011
Pagerank: 7.4890984e-05
Overall Rank: 3,255 | 78.12%
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
963	Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search	2012	SIGMOD	0.00012816649
2,220	String Similarity Joins: An Experimental Evaluation	2014	VLDB	8.8146984e-05
4,147	Local Similarity Search for Unstructured Text	2016	SIGMOD	6.7803631e-05
4,493	Approximate String Joins with Abbreviations	2018	VLDB	6.5772891e-05
5,188	Fast Subtrajectory Similarity Search in Road Networks under Weighted Edit Distance Constraints	2020	VLDB	6.2370687e-05
5,207	String Similarity Measures and Joins with Synonyms	2013	SIGMOD	6.2272365e-05
5,444	Pigeonring: A Principle for Faster Thresholded Similarity Search	2019	VLDB	6.1268526e-05
6,605	A Pivotal Prefix Based Filtering Algorithm for String Similarity Search	2014	SIGMOD	5.7367357e-05
7,030	Efficient Similarity Join and Search on Multi-Attribute Data	2015	SIGMOD	5.6173605e-05
7,172	Efficient Error-tolerant Query Autocompletion	2013	VLDB	5.5941906e-05
7,619	SyncSignature: A Simple, Efficient, Parallelizable Framework for Tree Similarity Joins	2023	VLDB	5.4832111e-05
9,879	META: An Efficient Matching-Based Method for Error-Tolerant Autocompletion	2016	VLDB	5.1176637e-05
9,905	DiskJoin: Large-scale Vector Similarity Join with SSD	2026	SIGMOD	5.1103839e-05
10,298	Local Filtering: Improving the Performance of Approximate Queries on String Collections	2015	SIGMOD	5.0418674e-05
10,299	Efficient and Effective KNN Sequence Search with Approximate n-grams	2014	VLDB	5.0418674e-05
11,339	Extensible and Robust Evaluation of Similarity Queries	2025	VLDB	4.9793485e-05
11,813	TokenJoin: Efficient Filtering for Set Similarity Join with Maximum Weighted Bipartite Matching	2023	VLDB	4.9793485e-05
12,228	ZigZag: Supporting Similarity Queries on Vector Space Models	2018	SIGMOD	4.9793485e-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.001992968
20	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00057568153
56	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.00040370171
108	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.0003305531
168	Efficient Exact Set-Similarity Joins	2006	VLDB	0.00027163517
201	Efficient set joins on similarity predicates	2004	SIGMOD	0.00025331535
929	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00013020115
1,061	VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams	2007	VLDB	0.00012213729
1,737	Extending Autocompletion To Tolerate Errors	2009	SIGMOD	9.7494976e-05
2,072	Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance	2010	SIGMOD	9.0864612e-05
2,144	Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently	2008	SIGMOD	8.9608583e-05
3,512	Efficient Approximate Entity Extraction with Edit Distance Constraints	2009	SIGMOD	7.2439455e-05
3,816	Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints	2010	VLDB	7.0072547e-05
4,196	Efficient and Effective Similarity Search over Probabilistic Data based on Earth Mover's Distance	2010	VLDB	6.7421052e-05
4,889	An Efficient Index Structure for String Databases	2001	VLDB	6.3682428e-05
5,795	Efficient Approximate Search on String Collections (Tutorial)	2009	VLDB	5.9926463e-05
7,856	Similarity Search on Bregman Divergence: Towards Non-Metric Indexing	2009	VLDB	5.4399688e-05

Semantically Similar Papers

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