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.428873e-05
Overall Rank: 7,906 | 46.85%
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,478	LSHAlign: All-Pair Near-Duplicate Text Alignment via LSH	2026	SIGMOD	4.9793485e-05
10,535	SWIFT: Enabling Large-Scale Temporal Graph Learning on a Single Machine	2026	SIGMOD	4.9793485e-05
10,717	SeDA: Bridging the Gap between Efficient Syntactic and Precise Semantic Search of Similar Passages in Large Text Corpora	2026	VLDB	4.9793485e-05
10,736	Near-Duplicate Text Alignment under Weighted Jaccard Similarity	2026	VLDB	4.9793485e-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.00057568153
280	Multi-Probe LSH: Efficient Indexing for High-Dimensional Similarity Search	2007	VLDB	0.0002230467
298	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00021833987
338	Locality-Sensitive Hashing Scheme Based on Dynamic Collision Counting	2012	SIGMOD	0.00020585187
562	SRS: Solving c-Approximate Nearest Neighbor Queries in High Dimensional Euclidean Space with a Tiny Index	2015	VLDB	0.00016335405
576	Quality and Efficiency in High Dimensional Nearest Neighbor Search	2009	SIGMOD	0.00016121388
929	Ed-Join: An Efficient Algorithm for Similarity Joins With Edit Distance Constraints	2008	VLDB	0.00013020115
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,933	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB	9.3459285e-05
2,921	Leveraging Set Relations in Exact Set Similarity Join	2017	VLDB	7.8519256e-05
4,147	Local Similarity Search for Unstructured Text	2016	SIGMOD	6.7803631e-05
5,549	Faerie: Efficient Filtering Algorithms for Approximate Dictionary-based Entity Extraction	2011	SIGMOD	6.088104e-05
7,833	Allign: Aligning All-Pair Near-Duplicate Passages in Long Texts	2021	SIGMOD	5.443666e-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

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,299	Efficient and Effective KNN Sequence Search with Approximate n-grams	2014	VLDB
2	8,186	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,952	Space-efficient Substring Occurrence Estimation	2011	PODS
5	2,362	Streaming Similarity Search over one Billion Tweets using Parallel Locality-Sensitive Hashing	2013	VLDB
6	8,689	TxtAlign: Efficient Near-Duplicate Text Alignment Search via Bottom-k Sketches for Plagiarism Detection	2022	SIGMOD
7	7,842	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD
8	7,833	Allign: Aligning All-Pair Near-Duplicate Passages in Long Texts	2021	SIGMOD
9	10,736	Near-Duplicate Text Alignment under Weighted Jaccard Similarity	2026	VLDB
10	10,478	LSHAlign: All-Pair Near-Duplicate Text Alignment via LSH	2026	SIGMOD