143 citations · 504 across the 80 of their papers we have counts for
6 papers · 1 filter
Faster Compact Top-k Document Retrieval
Roberto Konow, Gonzalo Navarro
An optimal index solving top-k document retrieval [Navarro and Nekrich, SODA12] takes O(m + k) time for a pattern of length m, but its space is at least 80n bytes for a collection…
Ranked Document Retrieval in (Almost) No Space
Nieves R. Brisaboa, Ana Cerdeira-Pena, Gonzalo Navarro +1
Ranked document retrieval is a fundamental task in search engines. Such queries are solved with inverted indexes that require additional 45%-80% of the compressed text space, and t…
Optimal Dynamic Sequence Representations
Gonzalo Navarro, Yakov Nekrich
We describe a data structure that supports access, rank and select queries, as well as symbol insertions and deletions, on a string over alphabet in time $O(\lg n…
Sorted Range Reporting
Yakov Nekrich, Gonzalo Navarro
In this paper we consider a variant of the orthogonal range reporting problem when all points should be reported in the sorted order of their -coordinates. We show that reportin…
Adaptive Techniques to find Optimal Planar Boxes
J. Barbay, G. Navarro, P. Pérez-Lantero
Given a set of planar points, two axes and a real-valued score function on subsets of , the Optimal Planar Box problem consists in finding a box (i.e. axis-aligned…
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 operation…