30 citations · 82 across the 38 of their papers we have counts for
4 papers · 1 filter
Worst-Case Optimal Adaptive Prefix Coding
Travis Gagie, Yakov Nekrich
A common complaint about adaptive prefix coding is that it is much slower than static prefix coding. Karpinski and Nekrich recently took an important step towards resolving this: t…
Low-Memory Adaptive Prefix Coding
Travis Gagie, Marek Karpinski, Yakov Nekrich
In this paper we study the adaptive prefix coding problem in cases where the size of the input alphabet is large. We present an online prefix coding algorithm that uses $O(σ^{1 / λ…
Space Efficient Multi-Dimensional Range Reporting
Marek Karpinski, Yakov Nekrich
We present a data structure that supports three-dimensional range reporting queries in time and uses $O(n\log^{1+\eps} n)$ space, where is…
Searching for Frequent Colors in Rectangles
Marek Karpinski, Yakov Nekrich
We study a new variant of colored orthogonal range searching problem: given a query rectangle all colors , such that at least a fraction of all points in are of colo…