7 citations · 23 across the 12 of their papers we have counts for
17 papers
ZigZag Trie: A Novel Index for Contextual Queries
Ling Li, Daniel Gibney, Sharma V. Thankachan +3
There is increasing interest in queries about the context of a string in a longer text , i.e., the set of all string pairs , with , for a given , such t…
Compressed Inverse Suffix Arrays
Sharma V. Thankachan
The suffix array ($\SA$) and inverse suffix array ($\ISA$) are fundamental data structures in string algorithms. For a text $T[0 \dd n)$ over an alphabet $[0 \dd σ)$, explicitly st…
Contextual Pattern Mining and Counting
Ling Li, Daniel Gibney, Sharma V. Thankachan +2
Given a string of length , a longer string of length , and two integers and , the context of in is the set of all string pairs , w…
Near-Optimal Quantum Algorithms for Bounded Edit Distance and Lempel-Ziv Factorization
Daniel Gibney, Ce Jin, Tomasz Kociumaka +1
Classically, the edit distance of two length- strings can be computed in time, whereas an -time procedure would falsify the Orthogonal Vectors Hypothesis. I…
Compressibility-Aware Quantum Algorithms on Strings
Daniel Gibney, Sharma V. Thankachan
Sublinear time quantum algorithms have been established for many fundamental problems on strings. This work demonstrates that new, faster quantum algorithms can be designed when th…
The Complexity of Approximate Pattern Matching on De Bruijn Graphs
Daniel Gibney, Sharma V. Thankachan, Srinivas Aluru
Aligning a sequence to a walk in a labeled graph is a problem of fundamental importance to Computational Biology. For finding a walk in an arbitrary graph with edges that exa…
Simple Reductions from Formula-SAT to Pattern Matching on Labeled Graphs and Subtree Isomorphism
Daniel Gibney, Gary Hoppenworth, Sharma V. Thankachan
The CNF formula satisfiability problem (CNF-SAT) has been reduced to many fundamental problems in P to prove tight lower bounds under the Strong Exponential Time Hypothesis (SETH).…
On the Complexity of BWT-runs Minimization via Alphabet Reordering
Jason Bentley, Daniel Gibney, Sharma V. Thankachan
The Burrows-Wheeler Transform (BWT) has been an essential tool in text compression and indexing. First introduced in 1994, it went on to provide the backbone for the first encoding…
On the Hardness and Inapproximability of Recognizing Wheeler Graphs
Daniel Gibney, Sharma V. Thankachan
In recent years several compressed indexes based on variants of the Burrows-Wheeler transformation have been introduced. Some of these index structures far more complex than a sing…
On Computing Average Common Substring Over Run Length Encoded Sequences
Sahar Hooshmand, Neda Tavakoli, Paniz Abedin +1
The Average Common Substring (ACS) is a popular alignment-free distance measure for phylogeny reconstruction. The ACS can be computed in O(n) space and time, where n=x+y is the inp…
Parameterized Pattern Matching -- Succinctly
Arnab Ganguly, Rahul Shah, Sharma V. Thankachan
We consider the problem, where a pattern matches some location in a text iff there is a one-to-one correspondence between the…
An In-place Framework for Exact and Approximate Shortest Unique Substring Queries
Wing-Kai Hon, Sharma V. Thankachan, Bojian Xu
We revisit the exact shortest unique substring (SUS) finding problem, and propose its approximate version where mismatches are allowed, due to its applications in subfields such as…
Probabilistic Threshold Indexing for Uncertain Strings
Sharma V. Thankachan, Manish Patil, Rahul Shah +1
Strings form a fundamental data type in computer systems. String searching has been extensively studied since the inception of computer science. Increasingly many applications have…
Optimal Encodings for Range Majority Queries
Gonzalo Navarro, Sharma V. Thankachan
We study the problem of designing a data structure that reports the positions of the distinct -majorities within any range of an array , without storing . A -major…
On Optimal Top-K String Retrieval
Rahul Shah, Cheng Sheng, Sharma V. Thankachan +1
Let = be a given set of (string) documents of total length . The top- document retrieval problem is to index such that…
Towards an Optimal Space-and-Query-Time Index for Top-k Document Retrieval
Wing-Kai Hon, Rahul Shah, Sharma V. Thankachan
Let $\D = $ be a given set of string documents of total length , our task is to index $\D$, such that the most relevant documents for an online quer…
Fully Dynamic Data Structure for Top-k Queries on Uncertain Data
Manish Patil, Rahul Shah, Sharma V. Thankachan
Top- queries allow end-users to focus on the most important (top-) answers amongst those which satisfy the query. In traditional databases, a user defined score function assi…