Sudatta Bhattacharya

activity

20232025

collaborators

Showing cs.DSShow all

3 papers · 1 filter

cs.DS2024

Many Flavors of Edit Distance

Sudatta Bhattacharya, Sanjana Dey, Elazar Goldenberg +1

Several measures exist for string similarity, including notable ones like the edit distance and the indel distance. The former measures the count of insertions, deletions, and subs…

cs.DS2023

Streaming $k$ -edit approximate pattern matching via string decomposition

Sudatta Bhattacharya, Michal Koucký

In this paper we give an algorithm for streaming $k$ -edit approximate pattern matching which uses space $O (k^{2})$ and time $O (k^{2})$ per arriving symbol. This…

cs.DS2023

Locally consistent decomposition of strings with applications to edit distance sketching

Sudatta Bhattacharya, Michal Koucký

In this paper we provide a new locally consistent decomposition of strings. Each string $x$ is decomposed into blocks that can be described by grammars of size $O (k)$ (…

Many Flavors of Edit Distance

Streaming k-edit approximate pattern matching via string decomposition

Locally consistent decomposition of strings with applications to edit distance sketching

Streaming $k$ -edit approximate pattern matching via string decomposition