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.4855571e-05
Overall Rank: 3,256 | 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
965	Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search	2012	SIGMOD	0.00012810695
2,223	String Similarity Joins: An Experimental Evaluation	2014	VLDB	8.8105347e-05
4,147	Local Similarity Search for Unstructured Text	2016	SIGMOD	6.7771533e-05
4,496	Approximate String Joins with Abbreviations	2018	VLDB	6.5741786e-05
5,190	Fast Subtrajectory Similarity Search in Road Networks under Weighted Edit Distance Constraints	2020	VLDB	6.2341162e-05
5,210	String Similarity Measures and Joins with Synonyms	2013	SIGMOD	6.2243094e-05
5,449	Pigeonring: A Principle for Faster Thresholded Similarity Search	2019	VLDB	6.123954e-05
6,608	A Pivotal Prefix Based Filtering Algorithm for String Similarity Search	2014	SIGMOD	5.73402e-05
7,032	Efficient Similarity Join and Search on Multi-Attribute Data	2015	SIGMOD	5.6147056e-05
7,175	Efficient Error-tolerant Query Autocompletion	2013	VLDB	5.5915423e-05
7,625	SyncSignature: A Simple, Efficient, Parallelizable Framework for Tree Similarity Joins	2023	VLDB	5.4806154e-05
9,886	META: An Efficient Matching-Based Method for Error-Tolerant Autocompletion	2016	VLDB	5.115241e-05
9,912	DiskJoin: Large-scale Vector Similarity Join with SSD	2026	SIGMOD	5.1079647e-05
10,303	Local Filtering: Improving the Performance of Approximate Queries on String Collections	2015	SIGMOD	5.0394806e-05
10,304	Efficient and Effective KNN Sequence Search with Approximate n-grams	2014	VLDB	5.0394806e-05
11,347	Extensible and Robust Evaluation of Similarity Queries	2025	VLDB	4.9769913e-05
11,819	TokenJoin: Efficient Filtering for Set Similarity Join with Maximum Weighted Bipartite Matching	2023	VLDB	4.9769913e-05
12,234	ZigZag: Supporting Similarity Queries on Vector Space Models	2018	SIGMOD	4.9769913e-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.0019923528
20	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.0005758001
56	M-tree: An Efficient Access Method for Similarity Search in Metric Spaces	1997	VLDB	0.00040363819
108	Approximate String Joins in a Database (Almost) for Free	2001	VLDB	0.00033040246
168	Efficient Exact Set-Similarity Joins	2006	VLDB	0.00027151132
201	Efficient set joins on similarity predicates	2004	SIGMOD	0.00025319937
929	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00013014029
1,062	VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams	2007	VLDB	0.00012208031
1,739	Extending Autocompletion To Tolerate Errors	2009	SIGMOD	9.7448851e-05
2,074	Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance	2010	SIGMOD	9.0821759e-05
2,147	Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently	2008	SIGMOD	8.9566452e-05
3,512	Efficient Approximate Entity Extraction with Edit Distance Constraints	2009	SIGMOD	7.2405277e-05
3,817	Trie-Join: Efficient Trie-based String Similarity Joins with Edit-Distance Constraints	2010	VLDB	7.0039415e-05
4,195	Efficient and Effective Similarity Search over Probabilistic Data based on Earth Mover's Distance	2010	VLDB	6.7391674e-05
4,893	An Efficient Index Structure for String Databases	2001	VLDB	6.3652283e-05
5,797	Efficient Approximate Search on String Collections (Tutorial)	2009	VLDB	5.9898117e-05
7,860	Similarity Search on Bregman Divergence: Towards Non-Metric Indexing	2009	VLDB	5.4373938e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,110	Similarity Evaluation on Tree-structured Data	2005	SIGMOD
2	8,251	Indexing Mixed Types for Approximate Retrieval	2005	VLDB
3	10,304	Efficient and Effective KNN Sequence Search with Approximate n-grams	2014	VLDB
4	2,074	Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance	2010	SIGMOD
5	6,974	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,625	Reference-Based Indexing of Sequence Databases	2006	VLDB
8	10,303	Local Filtering: Improving the Performance of Approximate Queries on String Collections	2015	SIGMOD
9	6,608	A Pivotal Prefix Based Filtering Algorithm for String Similarity Search	2014	SIGMOD
10	7,846	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD