Author name cluster

Francisco Claude

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.

3 papers

2 author rows

I&C Journal 2013 Journal Article

Compact binary relation representations with rich functionality

Jérémy Barbay
Francisco Claude
Gonzalo Navarro

Binary relations are an important abstraction arising in many data representation problems. The data structures proposed so far to represent them support just a few basic operations required to fit one particular application. We identify many of those operations arising in applications and generalize them into a wide set of desirable queries for a binary relation representation. We also identify reductions among those operations. We then introduce several novel binary relation representations, some simple and some quite sophisticated, that not only are space-efficient but also efficiently support a large subset of the desired queries.

Details DOI

TCS Journal 2011 Journal Article

Untangled monotonic chains and adaptive range search

Diego Arroyuelo
Francisco Claude
Reza Dorrigiv
Stephane Durocher
Meng He
Alejandro López-Ortiz
J. Ian Munro
Patrick K. Nicholson

We present the first adaptive data structure for two-dimensional orthogonal range search. Our data structure is adaptive in the sense that it gives improved search performance for data that is better than the worst case (Demaine et al. , 2000) [8]; in this case, data with more inherent sortedness. Given n points on the plane, the linear space data structure can answer range queries in O ( log n + k + m ) time, where m is the number of points in the output and k is the minimum number of monotonic chains into which the point set can be decomposed, which is O ( n ) in the worst case. Our result matches the worst-case performance of other optimal-time linear space data structures, or surpasses them when k = o ( n ). Our data structure can be made implicit, requiring no extra space beyond that of the data points themselves (Munro and Suwanda, 1980) [16], in which case the query time becomes O ( k log n + m ). We also present a novel algorithm of independent interest to decompose a point set into a minimum number of untangled, similarly directed monotonic chains in O ( k 2 n + n log n ) time.

Details DOI

MFCS Conference 2009 Conference Paper

Self-indexed Text Compression Using Straight-Line Programs

Francisco Claude
Gonzalo Navarro 0001

Abstract Straight-line programs (SLPs) offer powerful text compression by representing a text T [1, u ] in terms of a restricted context-free grammar of n rules, so that T can be recovered in O ( u ) time. However, the problem of operating the grammar in compressed form has not been studied much. We present a grammar representation whose size is of the same order of that of a plain SLP representation, and can answer other queries apart from expanding nonterminals. This can be of independent interest. We then extend it to achieve the first grammar representation able of extracting text substrings, and of searching the text for patterns, in time o ( n ). We also give byproducts on representing binary relations.

Details