4 papers · 1 filter
Tight Bounds for Online Stable Sorting
Travis Gagie, Yakov Nekrich
Although many authors have considered how many ternary comparisons it takes to sort a multiset of size , the best known upper and lower bounds still differ by a term linear…
Data Structures for Approximate Range Counting
Yakov Nekrich
We present new data structures for approximately counting the number of points in orthogonal range. There is a deterministic linear space data structure that supports updates in O(…
Fast and Compact Prefix Codes
Travis Gagie, Gonzalo Navarro, Yakov Nekrich
It is well-known that, given a probability distribution over characters, in the worst case it takes (Θ(n \log n)) bits to store a prefix code with minimum expected codeword len…
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…