Srinivasa Rao Satti

Dr. Srinivasa Rao Satti

Department of Computer Science, Norwegian University of Science and Technology, Trondheim 7491, Norway

Research Focus & Metrics

Academic Career Length

29Years (1998-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
1 November 2007 in ACM Transactions on Algorithms
Verified
Journal Article
Open access
RRRajeev Raman
Rajeev Raman
VRVenkatesh Raman
Venkatesh Raman
SSSrinivasa Rao Satti
Srinivasa Rao Satti
We consider the indexable dictionary problem, which consists of storing a set S ⊆ {0,…, m − 1} for some integer m while supporting the operations of rank( x ), which returns the number of elements in S that are less than x if x ∈ S , and −1 otherwise; and select( i ), which returns the i th smallest element in S . We give a data structure that supports both operations in O (1) time on the RAM model and requires B( n, m ) + o ( n ) + O (lg lg m ) bits to store a set of size n , where B( n, m ) = ⌊lg ( m / n )⌋ is the minimum number of bits required to store any n -element subset from a universe of size m . Previous dictionaries taking this space only supported (yes/no) membership queries in O (1) time. In the cell probe model we can remove the O (lg lg m ) additive term in the space bound, answering a question raised by Fich and Miltersen [1995] and Pagh [2001]. We present extensions and applications of our indexable dictionary data structure, including: —an information-theoretically optimal representation of a k -ary cardinal tree that supports standard operations in constant time; —a representation of a multiset of size n from {0,…, m − 1} in B( n, m + n ) + o ( n ) bits that supports (appropriate generalizations of) rank and select operations in constant time; and + O (lg lg m ) —a representation of a sequence of n nonnegative integers summing up to m in B( n, m + n ) + o ( n ) bits that supports prefix sum queries in constant time.

21 February 2005 in Algorithmica
Verified
Journal Article
Closed access
PDF file
DBDavid Benoit
David Benoit
EDErik D. Demaine
Erik D. Demaine
JMJ. Ian Munro
J. Ian Munro
RRRajeev Raman
Rajeev Raman
VRVenkatesh Raman
Venkatesh Raman
SSSrinivasa Rao Satti
Srinivasa Rao Satti

1 January 2015 in SIAM Journal on Computing
Verified
Journal Article
Closed access
Philip BillePhilip Bille
Philip Bille
GLGad M. Landau
Gad M. Landau
RRRajeev Raman
Rajeev Raman
KSKunihiko Sadakane
Kunihiko Sadakane
SSSrinivasa Rao Satti
Srinivasa Rao Satti
OWOren Weimann
Oren Weimann
Grammar-based compression, where one replaces a long string by a small context-free grammar that generates the string, is a simple and powerful paradigm that captures (sometimes with slight reduction in efficiency) many of the popular compression schemes, including the Lempel--Ziv family, run-length encoding, byte-pair encoding, Sequitur, and Re-Pair. In this paper, we present a novel grammar representation that allows efficient random access to any character or substring without decompressing the string. Let $S$ be a string of length $N$ compressed into a context-free grammar $\mathcal{S}$ of size $n$. We present two representations of $\mathcal{S}$ achieving $O(\log N)$ random access time, and either $O(n\cdot\alpha_k(n))$ construction time and space on the pointer machine model, or $O(n)$ construction time and space on the RAM. Here, $\alpha_k(n)$ is the inverse of the $k$th row of Ackermann's function. Our representations also efficiently support decompression of any substring in $S$: we can decompress any substring of length $m$ in the same complexity as a single random access query and additional $O(m)$ time. Combining these results with fast algorithms for uncompressed approximate string matching leads to several efficient algorithms for approximate string matching on grammar-compressed strings without decompression. For instance, we can find all approximate occurrences of a pattern $P$ with at most $k$ errors in time $O(n(\min\{|P|k,k^4+|P|\}+\log N)+\mathrm{occ})$, where $\mathrm{occ}$ is the number of occurrences of $P$ in $S$. Finally, we generalize our results to navigation and other operations on grammar-compressed ordered trees. All of the above bounds significantly improve the currently best known results. To achieve these bounds, we introduce several new techniques and data structures of independent interest, including a predecessor data structure, two “biased” weighted ancestor data structures, and a compact representation of heavy paths in grammars.

1 May 2001 in Journal of Algorithms
Verified
Journal Article
Closed access
JMJ.Ian Munro
J.Ian Munro
VRVenkatesh Raman
Venkatesh Raman
SSSrinivasa Rao Satti
Srinivasa Rao Satti

1 June 2012 in Theoretical Computer Science
Verified
Journal Article
Closed access
JMJ. Ian Munro
J. Ian Munro
RRRajeev Raman
Rajeev Raman
VRVenkatesh Raman
Venkatesh Raman
SSSrinivasa Rao Satti
Srinivasa Rao Satti

1 January 2006
Verified
Conference Paper
Open access
PDF file
AGAlexander Golynski
Alexander Golynski
JMJ. Ian Munro
J. Ian Munro
SSSrinivasa Rao Satti
Srinivasa Rao Satti