Local Similarity Search for Unstructured Text

Summary: Local similarity search for partially replicated text: finds pairs of sliding windows differing by at most tau tokens, not whole documents. Introduces signature-based token combinations on a partitioned token universe, with cost-aware partitioning and overlap-aware reuse to scale to large tau. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 5300
Venue: SIGMOD
Year: 2016
Pagerank: 6.935988e-05
Overall Rank: 4,052 | 72.21%
DOI: 10.1145/2882903.2915211

Incoming Non-self Citations Over Time

Authors

1. Pei Wang (Nagoya University)
2. Chuan Xiao (Nagoya University)
3. Jianbin Qin (University of New South Wales)
4. Wei Wang (University of New South Wales)
5. Xiaoyang Zhang (University of New South Wales)
6. Yoshiharu Ishikawa (Nagoya University)

BibTeX Citation

@inproceedings{wang_sigmod16,
        title = {{Local Similarity Search for Unstructured Text}},
        author = {Wang, Pei and Xiao, Chuan and Qin, Jianbin and Wang, Wei and Zhang, Xiaoyang and Ishikawa, Yoshiharu},
        series = {{SIGMOD} '16},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/2882903.2915211},
        url = {https://dl.acm.org/doi/10.1145/2882903.2915211},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,726	Pigeonring: A Principle for Faster Thresholded Similarity Search	2019	VLDB	6.1079184e-05
7,676	Allign: Aligning All-Pair Near-Duplicate Passages in Long Texts	2021	SIGMOD	5.5686107e-05
7,745	Near-Duplicate Text Alignment with One Permutation Hashing	2024	SIGMOD	5.5534781e-05
8,522	TxtAlign: Efficient Near-Duplicate Text Alignment Search via Bottom-k Sketches for Plagiarism Detection	2022	SIGMOD	5.4119882e-05
10,024	Near-Duplicate Sequence Search at Scale for Large Language Model Memorization Evaluation	2023	SIGMOD	5.1757914e-05
10,554	Near-Duplicate Text Alignment under Weighted Jaccard Similarity	2026	VLDB	5.093636e-05
11,447	A Two-Level Signature Scheme for Stable Set Similarity Joins	2023	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 18 of 18 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
21	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00056760516
169	Efficient Exact Set-Similarity Joins	2006	VLDB	0.0002743469
200	Efficient set joins on similarity predicates	2004	SIGMOD	0.00025597287
975	Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search	2012	SIGMOD	0.00012870645
978	Winnowing: Local Algorithms for Document Fingerprinting	2003	SIGMOD	0.00012859554
991	Bayesian Locality Sensitive Hashing for Fast Similarity Search	2012	VLDB	0.00012793339
1,284	Copy Detection Mechanisms for Digital Documents	1995	SIGMOD	0.00011332822
1,393	Truth Discovery and Copying Detection in a Dynamic World	2009	VLDB	0.00010934682
1,886	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB	9.5358137e-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,442	An Efficient Filter for Approximate Membership Checking	2008	SIGMOD	7.4122197e-05
4,605	Global Detection of Complex Copying Relationships Between Sources	2010	VLDB	6.6103623e-05
4,992	Scalable Ad-hoc Entity Extraction from Text Collections	2008	VLDB	6.4100657e-05
5,306	On Indexing Error-Tolerant Set Containment	2010	SIGMOD	6.2731936e-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
10,085	Local Filtering: Improving the Performance of Approximate Queries on String Collections	2015	SIGMOD	5.1559617e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,554	Near-Duplicate Text Alignment under Weighted Jaccard Similarity	2026	VLDB
2	10,265	LSHAlign: All-Pair Near-Duplicate Text Alignment via LSH	2026	SIGMOD
3	1,625	Determining Text Databases to Search in the Internet	1998	VLDB
4	3,041	Spatio-Textual Similarity Joins	2013	VLDB
5	11,702	LES3: Learning-based Exact Set Similarity Search	2021	VLDB
6	7,745	Near-Duplicate Text Alignment with One Permutation Hashing	2024	SIGMOD
7	2,519	Similarity search in the blink of an eye with compressed indices	2023	VLDB
8	3,193	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD
9	8,522	TxtAlign: Efficient Near-Duplicate Text Alignment Search via Bottom-k Sketches for Plagiarism Detection	2022	SIGMOD
10	14,501	Unstructured Data Bases or Very Efficient Text Searching	1983	PODS