SCALABLE NEAR-DUPLICATE SEQUENCE ALIGNMENT FOR LEXICAL AND SEMANTIC SIMILARITY SEARCH

Near-duplicate sequence alignment aims to identify subsequences in large data collections that are sufficiently similar to a query, with applications including plagiarism detection, data deduplication, and multimedia copy detection. Unlike document-level similarity search, sequence alignment must locate the precise boundaries of reused content while tolerating variations in length and structure. A fundamental challenge is scalability, as a sequence of length n contains O(n^2) possible subsequences, making exhaustive representation and comparison prohibitively expensive. This dissertation develops scalable techniques for near-duplicate sequence alignment by progressively reducing the cost of representing, indexing, and searching large numbers of overlapping subsequences. We first introduce TxtAlign, which uses bottom-k sketches to estimate Jaccard similarity between text passages. By exploiting the observation that many overlapping passages share the same sketch, TxtAlign reduces O(n^2) possible passages to O(nk) compact representations, enabling efficient corpus-level retrieval and text alignment. Building on this framework, RangeAlign further addresses the storage overhead of sketch-based alignment. While indexing O(nk) compact windows together with their sketch elements can require O(nk^2) space, RangeAlign groups the endpoint ranges associated with the same distinct word and stores only a constant-size representation for each distinct word, reducing the index space to O(n) and making it independent of the sketch size k. Finally, we move beyond lexical similarity with VecAlign, which performs near-duplicate detection at the semantic level. It represents text and video as sequences of high-dimensional embedding vectors, allowing semantically equivalent content to be identified even when its surface form has been substantially rewritten or transformed. VecAlign defines an embedding-aware edit distance and combines threshold-based approximate nearest-neighbor search with four filtering strategies to efficiently identify candidate subsequences for verification. Together, these works provide scalable alignment techniques that progress from compact lexical representations and space-efficient indexing to semantic sequence matching in the embedding space.