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: 7028
Venue: SIGMOD
Year: 2024
Pagerank: 5.5534781e-05
Overall Rank: 7,745 | 46.87%
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,265	LSHAlign: All-Pair Near-Duplicate Text Alignment via LSH	2026	SIGMOD	5.093636e-05
10,330	SWIFT: Enabling Large-Scale Temporal Graph Learning on a Single Machine	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 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
21	Similarity Search in High Dimensions via Hashing	1999	VLDB	0.00056760516
287	Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search	2007	VLDB	0.00022323585
332	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00020920444
369	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD	0.00019945234
580	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00016157635
581	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00016153395
911	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00013283031
978	Winnowing: Local Algorithms for Document Fingerprinting	2003	SIGMOD	0.00012859554
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,040	Leveraging Set Relations in Exact Set Similarity Join	2017	VLDB	7.8262287e-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
7,676	Allign: Aligning All-Pair Near-Duplicate Passages in Long Texts	2021	SIGMOD	5.5686107e-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

Semantically Similar Papers

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