Jérémy Barbay

Prof. Jérémy Barbay

Department of Computer Science, University of Chile, Santiago, Chile
orcid

Research Focus & Metrics

Academic Career Length

24Years (2003-Present)

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

Representative Publications

View All Publications
16 September 2010 in Algorithmica
Verified
Journal Article
Closed access
PDF file
JBJérémy Barbay
Jérémy Barbay
LALuca Castelli Aleardi
Luca Castelli Aleardi
MHMeng He
Meng He
JMJ. Ian Munro
J. Ian Munro

28 September 2011 in ACM Transactions on Algorithms
Verified
Journal Article
Open access
PDF file
JBJérémy Barbay
Jérémy Barbay
MHMeng He
Meng He
JMJ. Ian Munro
J. Ian Munro
SSSrinivasa Rao Satti
Srinivasa Rao Satti
We define and design succinct indexes for several abstract data types (ADTs). The concept is to design auxiliary data structures that ideally occupy asymptotically less space than the information-theoretic lower bound on the space required to encode the given data, and support an extended set of operations using the basic operators defined in the ADT. The main advantage of succinct indexes as opposed to succinct (integrated data/index) encodings is that we make assumptions only on the ADT through which the main data is accessed, rather than the way in which the data is encoded. This allows more freedom in the encoding of the main data. In this article, we present succinct indexes for various data types, namely strings, binary relations and multilabeled trees. Given the support for the interface of the ADTs of these data types, we can support various useful operations efficiently by constructing succinct indexes for them. When the operators in the ADTs are supported in constant time, our results are comparable to previous results, while allowing more flexibility in the encoding of the given data. Using our techniques, we design a succinct encoding that represents a string of length n over an alphabet of size σ using n H k ( S ) + lg σ · o ( n ) + O ( n lg σ/lg lg lg σ) bits to support access/rank/select operations in o ((lg lg σ) 1+ϵ ) time, for any fixed constant ϵ > 0. We also design a succinct text index using n H 0 ( S ) + O ( n lg σ/lg lg σ) bits that supports finding all the occ occurrences of a given pattern of length m in O ( m lg lg σ + occ lg n /lg ϵ σ) time, for any fixed constant 0 < ϵ < 1. Previous results on these two problems either have a lg σ factor instead of lg lg σ in the running time, or are not compressed. Finally, we present succinct encodings of binary relations and multi-labeled trees that are more compact than previous structures.

22 November 2007 in Theoretical Computer Science
Verified
Journal Article
Closed access
JBJérémy Barbay
Jérémy Barbay
AGAlexander Golynski
Alexander Golynski
JMJ. Ian Munro
J. Ian Munro
SRS. Srinivasa Rao
S. Srinivasa Rao

1 January 2006
Verified
Book Chapter
Closed access
PDF file
JBJérémy Barbay
Jérémy Barbay
ALAlejandro López-Ortiz
Alejandro López-Ortiz
TLTyler Lu
Tyler Lu

28 March 2008 in ACM Transactions on Algorithms
Verified
Journal Article
Open access
JBJérémy Barbay
Jérémy Barbay
CKClaire Kenyon
Claire Kenyon
The intersection of sorted arrays problem has applications in search engines such as Google. Previous work has proposed and compared deterministic algorithms for this problem, in an adaptive analysis based on the encoding size of a certificate of the result (cost analysis). We define the alternation analysis , based on the nondeterministic complexity of an instance. In this analysis we prove that there is a deterministic algorithm asymptotically performing as well as any randomized algorithm in the comparison model. We define the redundancy analysis , based on a measure of the internal redundancy of the instance. In this analysis we prove that any algorithm optimal in the redundancy analysis is optimal in the alternation analysis, but that there is a randomized algorithm which performs strictly better than any deterministic algorithm in the comparison model. Finally, we describe how these results can be extended beyond the comparison model.

1 January 2006 in Lecture Notes in Computer Science
Verified
Book Chapter
Closed access
PDF file
JBJérémy Barbay
Jérémy Barbay
AGAlexander Golynski
Alexander Golynski
JMJ. Ian Munro
J. Ian Munro
SSSrinivasa Rao Satti
Srinivasa Rao Satti