Events

Qualifying Exam Near-Duplicate Text Alignment at Scale
Export Event Save iCal Send to Google Calendar Send to Yahoo Calendar Send to Outlook Live Send to Microsoft Outlook Save iCal Preserve formatting in description (only supported in some calendar applications) Close Tuesday, April 01, 2025, 11:00am - 12:00pm

Speaker: Zhencan Peng

Bio

Location : CoRE 305

Committee: 

Assistant Professor Dong Deng

Associate Professor Yongfeng Zhang

Associate Professor Desheng Zhang

Professor Matthew Stone

Event Type: Qualifying Exam

Abstract: The proliferation of near-duplicate content—text segments differing by minor variations—poses significant challenges in large-scale text corpora, particularly in applications involving large language model (LLM) training and web-scale information retrieval. Studies indicate that 30–45% of web content consists of near-duplicates, leading to inefficiencies such as redundant data storage, increased computational costs, and reduced generalization in LLMs. While exact deduplication techniques, such as suffix arrays, effectively remove identical sequences, the problem of fuzzy subsequence-level deduplication remains largely unsolved due to computational constraints.Existing approaches face two fundamental challenges: (1) combinatorial explosion, where a corpus with n tokens contains O(n^2) subsequences, making exhaustive similarity comparisons computationally prohibitive; and (2) memory-throughput tradeoff, where traditional min-hash-based methods require O(nk) space for k hash functions, rendering them infeasible for trillion-token corpora. Addressing these limitations, we introduce a novel near-duplicate text alignment framework that enables efficient and scalable subsequence-level search.Our contributions are threefold: • One Permutation Hashing (OPH) Compact Windows, a novel compression technique that reduces index size from O(nk) to O(n+k), achieving a 90% reduction in space while maintaining full recall. • Interval-Scan Alignment, an O((n+k)log(n+k)) algorithm leveraging dynamic segment trees to accelerate near-duplicate subsequence detection by 100× over prior methods. • Theoretical Guarantees, providing formal proof that OPH maintains the collision probabilities of traditional min-hash techniques, ensuring no loss in accuracy.Building on this foundation, our ongoing work aims to develop corpus-scale subsequence clustering methods that efficiently group redundant text spans, reducing pairwise comparisons from O(n^2) to O(nk) per document while seamlessly integrating into LLM training pipelines. Our research represents a crucial step toward efficient and scalable fuzzy deduplication, with implications for dataset curation, generative model safety, and large-scale text processing.Publications: • Near-Duplicate Sequence Search at Scale for Large Language Model Memorization Evaluation(SIGMOD 2023) • Near-Duplicate Text Alignment with One Permutation Hashing (SIGMOD 2025)

Organization: 

Contact  Assistant Professor Dong Deng

Zoom link: https://rutgers.zoom.us/my/zp128?pwd=b3RCT3A4dThabUczNWZqbFpWWjZwQT09&omn=97200664891