39 citations · 87 across the 16 of their papers we have counts for
Showing 2011Show all
3 papers · 1 filter
cs.DS2011
Using Hashing to Solve the Dictionary Problem (In External Memory)
John Iacono, Mihai Pǎtraşcu
We consider the dictionary problem in external memory and improve the update time of the well-known buffer tree by roughly a logarithmic factor. For any λ>= max {lg lg n, log_{M/B}…
cs.CG2011
Orthogonal Range Searching on the RAM, Revisited
Timothy M. Chan, Kasper Green Larsen, Mihai Patrascu
We present several new results on one of the most extensively studied topics in computational geometry, orthogonal range searching. All our results are in the standard word RAM mod…
cs.DS2011★ 8 cited
Don't Rush into a Union: Take Time to Find Your Roots
Mihai Patrascu, Mikkel Thorup
We present a new threshold phenomenon in data structure lower bounds where slightly reduced update times lead to exploding query times. Consider incremental connectivity, letting t…