30 citations · 82 across the 38 of their papers we have counts for
4 papers · 2 filters
Optimal Top-k Document Retrieval
Gonzalo Navarro, Yakov Nekrich
Let be a collection of documents, which are strings over an alphabet of size , of total length . We describe a data structure that uses linear space and and…
Optimal Color Range Reporting in One Dimension
Yakov Nekrich, Jeffrey Scott Vitter
Color (or categorical) range reporting is a variant of the orthogonal range reporting problem in which every point in the input is assigned a \emph{color}. While the answer to an o…
Heaviest Induced Ancestors and Longest Common Substrings
Travis Gagie, Paweł Gawrychowski, Yakov Nekrich
Suppose we have two trees on the same set of leaves, in which nodes are weighted such that children are heavier than their parents. We say a node from the first tree and a node fro…
Full-fledged Real-Time Indexing for Constant Size Alphabets
Gregory Kucherov, Yakov Nekrich
In this paper we describe a data structure that supports pattern matching queries on a dynamically arriving text over an alphabet ofconstant size. Each new symbol can be prepended…