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: hc79a3f31edc57759
Venue: SIGMOD
Year: 2016
Pagerank: 6.7803631e-05
Overall Rank: 4,147 | 72.12%
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,444	Pigeonring: A Principle for Faster Thresholded Similarity Search	2019	VLDB	6.1268526e-05
7,833	Allign: Aligning All-Pair Near-Duplicate Passages in Long Texts	2021	SIGMOD	5.443666e-05
7,906	Near-Duplicate Text Alignment with One Permutation Hashing	2024	SIGMOD	5.428873e-05
8,689	TxtAlign: Efficient Near-Duplicate Text Alignment Search via Bottom-k Sketches for Plagiarism Detection	2022	SIGMOD	5.2905577e-05
10,214	Near-Duplicate Sequence Search at Scale for Large Language Model Memorization Evaluation	2023	SIGMOD	5.0596605e-05
10,736	Near-Duplicate Text Alignment under Weighted Jaccard Similarity	2026	VLDB	4.9793485e-05
11,759	A Two-Level Signature Scheme for Stable Set Similarity Joins	2023	VLDB	4.9793485e-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
20	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00057568153
168	Efficient Exact Set-Similarity Joins	2006	VLDB	0.00027163517
201	Efficient set joins on similarity predicates	2004	SIGMOD	0.00025331535
963	Can We Beat the Prefix Filtering? An Adaptive Framework for Similarity Join and Search	2012	SIGMOD	0.00012816649
992	Bayesian Locality Sensitive Hashing for Fast Similarity Search	2012	VLDB	0.00012646771
1,001	Winnowing: Local Algorithms for Document Fingerprinting	2003	SIGMOD	0.00012599856
1,306	Copy Detection Mechanisms for Digital Documents	1995	SIGMOD	0.00011084152
1,385	Truth Discovery and Copying Detection in a Dynamic World	2009	VLDB	0.00010843714
1,933	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB	9.3459285e-05
2,220	String Similarity Joins: An Experimental Evaluation	2014	VLDB	8.8146984e-05
3,255	Efficient Exact Edit Similarity Query Processing with the Asymmetric Signature Scheme	2011	SIGMOD	7.4890984e-05
3,501	An Efficient Filter for Approximate Membership Checking	2008	SIGMOD	7.2531528e-05
4,696	Global Detection of Complex Copying Relationships Between Sources	2010	VLDB	6.4652683e-05
4,736	Scalable Ad-hoc Entity Extraction from Text Collections	2008	VLDB	6.4451961e-05
5,333	On Indexing Error-Tolerant Set Containment	2010	SIGMOD	6.1750986e-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
10,298	Local Filtering: Improving the Performance of Approximate Queries on String Collections	2015	SIGMOD	5.0418674e-05

Semantically Similar Papers

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