Near-Duplicate Text Alignment with One Permutation Hashing

Summary: OPH-based compact windows compress all O(n^2 k) min-hashes to O(n+k) space for near-duplicate text alignment under Jaccard, avoiding enumeration. An efficient algorithm derives all query-similar sketches directly from OPH compact windows with three optimizations, reducing index cost and query latency on real datasets. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h6c9ad3b76bf752e0
Venue: SIGMOD
Year: 2024
Pagerank: 5.426303e-05
Overall Rank: 7,910 | 46.84%
DOI: 10.1145/3677136

Incoming Non-self Citations Over Time

Authors

1. Zhencan Peng (Rutgers University)
2. Yuheng Zhang (Rutgers University)
3. Dong Deng (Rutgers University)

BibTeX Citation

@inproceedings{peng_sigmod24,
        title = {{Near-Duplicate Text Alignment with One Permutation Hashing}},
        author = {Peng, Zhencan and Zhang, Yuheng and Deng, Dong},
        series = {{SIGMOD} '24},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3677136},
        url = {https://dl.acm.org/doi/10.1145/3677136},
        year = {2024}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,489	LSHAlign: All-Pair Near-Duplicate Text Alignment via LSH	2026	SIGMOD	4.9769913e-05
10,546	SWIFT: Enabling Large-Scale Temporal Graph Learning on a Single Machine	2026	SIGMOD	4.9769913e-05
10,727	SeDA: Bridging the Gap between Efficient Syntactic and Precise Semantic Search of Similar Passages in Large Text Corpora	2026	VLDB	4.9769913e-05
10,746	Near-Duplicate Text Alignment under Weighted Jaccard Similarity	2026	VLDB	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 16 of 16 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.0005758001
278	Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search	2007	VLDB	0.00022310642
297	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00021849337
338	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD	0.00020600264
562	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00016350316
576	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00016118297
929	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00013014029
1,001	Winnowing: Local Algorithms for Document Fingerprinting	2003	SIGMOD	0.00012593904
1,306	Copy Detection Mechanisms for Digital Documents	1995	SIGMOD	0.00011078917
1,934	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB	9.341845e-05
2,923	Leveraging Set Relations in Exact Set Similarity Join	2017	VLDB	7.8482459e-05
4,147	Local Similarity Search for Unstructured Text	2016	SIGMOD	6.7771533e-05
5,551	Faerie: Efficient Filtering Algorithms for Approximate Dictionary-based Entity Extraction	2011	SIGMOD	6.0852227e-05
7,837	Allign: Aligning All-Pair Near-Duplicate Passages in Long Texts	2021	SIGMOD	5.4410891e-05
8,697	TxtAlign: Efficient Near-Duplicate Text Alignment Search via Bottom-k Sketches for Plagiarism Detection	2022	SIGMOD	5.2880532e-05
10,220	Near-Duplicate Sequence Search at Scale for Large Language Model Memorization Evaluation	2023	SIGMOD	5.0572653e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,304	Efficient and Effective KNN Sequence Search with Approximate n-grams	2014	VLDB
2	8,194	A New Approach for Processing Ranked Subsequence Matching Based on Ranked Union	2011	SIGMOD
3	4,147	Local Similarity Search for Unstructured Text	2016	SIGMOD
4	6,955	Space-efficient Substring Occurrence Estimation	2011	PODS
5	2,363	Streaming Similarity Search over one Billion Tweets using Parallel Locality-Sensitive Hashing	2013	VLDB
6	8,697	TxtAlign: Efficient Near-Duplicate Text Alignment Search via Bottom-k Sketches for Plagiarism Detection	2022	SIGMOD
7	7,846	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD
8	7,837	Allign: Aligning All-Pair Near-Duplicate Passages in Long Texts	2021	SIGMOD
9	10,746	Near-Duplicate Text Alignment under Weighted Jaccard Similarity	2026	VLDB
10	10,489	LSHAlign: All-Pair Near-Duplicate Text Alignment via LSH	2026	SIGMOD