Arrow Research search

Author name cluster

Manish Patil

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers
1 author row

Possible papers

2

TCS Journal 2015 Journal Article

Succinct indexes for reporting discriminating and generic words

  • Sudip Biswas
  • Manish Patil
  • Rahul Shah
  • Sharma V. Thankachan

We consider the problem of indexing a collection D of D strings (documents) of total n characters from an alphabet set of size σ, such that whenever a pattern P (of p characters) and an integer τ ∈ [ 1, D ] come as a query, we can efficiently report all (i) maximal generic words and (ii) minimal discriminating words as defined below: • maximal generic word is a maximal extension of P occurring in at least τ documents. • minimal discriminating word is a minimal extension of P occurring in at most τ documents. These problems were introduced by Kucherov et al. (SPIRE) [8], they proposed indexes occupying O ( n log ⁡ n ) bits with query times O ( p + output ) and O ( p + log ⁡ log ⁡ n + output ) for Problem (i) and Problem (ii) respectively. The query time for Problem (ii) is later improved to optimal O ( p + output ) by Gawrychowski et al. (SPIRE) [6]. In this paper, we describe succinct indexes of n log ⁡ σ + o ( n log ⁡ σ ) + O ( n ) bits space with near-optimal query times i. e. , O ( p + log ⁡ log ⁡ n + output ) for both these problems.

Details DOI

I&C Journal 2013 Journal Article

Compressed property suffix trees

  • Wing-Kai Hon
  • Manish Patil
  • Rahul Shah
  • Sharma V. Thankachan

Property matching is a biologically motivated problem where the task is to find those occurrences of an online pattern P in a string text T (of size n), such that the matched text part satisfies some conceptual property. The property of a string is a set π of (possibly overlapping) intervals { ( s 1, f 1 ), ( s 2, f 2 ), … } corresponding to the part of text and an occurrence of a pattern P = T [ i, …, ( i + | P | − 1 ) ] is a valid output only if T [ i, …, ( i + | P | − 1 ) ] is completely contained in at least one interval ( s j, f j ) ∈ π. The indexing version of this problem was introduced by A. Amir (2008), where the text is preprocessed in O ( n log σ + n log log n ) time and an O ( n log n ) bits index, named Property Suffix Tree (PST) is maintained. PST can perform property matching in O ( | P | log σ + occ π ) time, where occ π is the number of occurrences of P in T satisfying the property. T. Kopelowitz (2010) considered the dynamic version of this problem where intervals can be added or deleted. However, all these indexes take space linear to the size of text ( O ( n log n ) bits), which can be much more than the size of the text ( n log σ bits). In this paper, we propose the first index for property matching occupying space close to the entropy compressed space requirement of the text. Our compressed index takes | CSA | + n ( 2 + ϵ + o ( 1 ) ) bits space and performs query answering in O ( t ( | P | ) + 1 ϵ ( 1 + occ π ) t SA ) time, where | CSA | is the size of compressed suffix array of T, t ( | P | ) be the time for searching a pattern of length | P | in CSA, t SA is the time for computing the suffix array value and ϵ > 0 is a constant. We also introduce a dynamic index, which takes | CSA | + O ( n + | π | log n ) bits space and performs query answering in O ( t ( | P | ) + ( 1 + occ π ) log n ( t SA + log n / log log n ) ) time and can update (insert/delete) an interval ( s, f ) in O ( ( f − s ) ( log n + t SA ) ) time.

Details DOI
v2026.09.13