Allign: Aligning All-Pair Near-Duplicate Passages in Long Texts

Summary: Allign uses a min-hash based method to align all-pair near-duplicate passages in two texts, avoiding O(n^2 m^2) enumeration via compact windows. It matches windows by shared min-hash, reports the longest and sentence-level near-duplicates, and outperforms prior alignment methods on real data. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6299
Venue: SIGMOD
Year: 2021
Pagerank: 5.5686107e-05
Overall Rank: 7,676 | 47.34%
DOI: 10.1145/3448016.3457548

Incoming Non-self Citations Over Time

Authors

1. Weiqi Feng (Shanghai Jiao Tong University)
2. Dong Deng (Rutgers University)

BibTeX Citation

@inproceedings{feng_sigmod21,
        title = {{Allign: Aligning All-Pair Near-Duplicate Passages in Long Texts}},
        author = {Feng, Weiqi and Deng, Dong},
        series = {{SIGMOD} '21},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3448016.3457548},
        url = {https://dl.acm.org/doi/10.1145/3448016.3457548},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 7 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
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
9,065	R2D2: Reducing Redundancy and Duplication in Data Lakes	2023	SIGMOD	5.3251649e-05
10,024	Near-Duplicate Sequence Search at Scale for Large Language Model Memorization Evaluation	2023	SIGMOD	5.1757914e-05
10,265	LSHAlign: All-Pair Near-Duplicate Text Alignment via LSH	2026	SIGMOD	5.093636e-05
10,533	SeDA: Bridging the Gap between Efficient Syntactic and Precise Semantic Search of Similar Passages in Large Text Corpora	2026	VLDB	5.093636e-05
10,554	Near-Duplicate Text Alignment under Weighted Jaccard Similarity	2026	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 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
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,886	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB	9.5358137e-05
3,446	Efficient Approximate Entity Extraction with Edit Distance Constraints	2009	SIGMOD	7.4087786e-05
3,474	An Efficient Partition Based Method for Exact Set Similarity Joins	2016	VLDB	7.3859271e-05
3,724	Overlap Set Similarity Joins with Theoretical Guarantees	2018	SIGMOD	7.1715735e-05
3,806	On the Complexity of Inner Product Similarity Join	2016	PODS	7.108802e-05
4,052	Local Similarity Search for Unstructured Text	2016	SIGMOD	6.935988e-05
5,412	Faerie: Efficient Filtering Algorithms for Approximate Dictionary-based Entity Extraction	2011	SIGMOD	6.2272563e-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

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	911	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB
2	10,024	Near-Duplicate Sequence Search at Scale for Large Language Model Memorization Evaluation	2023	SIGMOD
3	10,086	Efficient and Effective KNN Sequence Search with Approximate n-grams	2014	VLDB
4	1,886	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB
5	7,692	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD
6	4,052	Local Similarity Search for Unstructured Text	2016	SIGMOD
7	10,554	Near-Duplicate Text Alignment under Weighted Jaccard Similarity	2026	VLDB
8	7,745	Near-Duplicate Text Alignment with One Permutation Hashing	2024	SIGMOD
9	8,522	TxtAlign: Efficient Near-Duplicate Text Alignment Search via Bottom-k Sketches for Plagiarism Detection	2022	SIGMOD
10	10,265	LSHAlign: All-Pair Near-Duplicate Text Alignment via LSH	2026	SIGMOD