<p>I've been interested in looking into the area of de-amortization recently (i.e. finding data structures with matching worst-case and amortized running time bounds, or exhibiting lower bounds against matching the amortized complexity of certain operations with a worst-case bound). </p>

<p>The only reference I've been able to find so far is a <a href="http://link.springer.com/chapter/10.1007%2F3-540-68535-9_4">survey</a> from COCOON by S.R. Kosaraju and M. Pop.</p>

<p>Are there any other good surveys or set of papers to read regarding de-amortization?</p>

CC BY-SA 3.0
2014-09-30T09:06:22.007Z
Naor and Yogev [showed a nice de-amortization](http://arxiv.org/pdf/1304.5872v6.pdf) for their sliding bloom filter structure (section 2.4).
R B
CC BY-SA 3.0
2014-09-30T20:36:34.303Z
You can take a look to the recent work of Goodrich, Mitzenmacher et al. on de-amortize oblivious RAM simulations (see also their "previous work" section): [Oblivious RAM simulation with efficient worst-case access overhead](http://dl.acm.org/citation.cfm?id=2046680) and   
[Cache-Oblivious dictionaries and multimaps with negligible failure probability](http://dl.acm.org/citation.cfm?id=2437302)
Marzio De Biasi
<reference-request><ds.data-structures><lower-bounds><amortized-analysis>
References for de-amortization
rahulmehta95
# References for de-amortization

(Asked by: username_0 on 2014-09-30)

I've been interested in looking into the area of de-amortization recently (i.e. finding data structures with matching worst-case and amortized running time bounds, or exhibiting lower bounds against matching the amortized complexity of certain operations with a worst-case bound).

The only reference I've been able to find so far is a [survey](http://link.springer.com/chapter/10.1007%2F3-540-68535-9_4) from COCOON by S.R. Kosaraju and M. Pop.

Are there any other good surveys or set of papers to read regarding de-amortization?

**Tags:** reference-request, ds.data-structures, lower-bounds, amortized-analysis

> **Comments:**
> **username_1**: Naor and Yogev [showed a nice de-amortization](http://arxiv.org/pdf/1304.5872v6.pdf) for their sliding bloom filter structure (section 2.4).  
> **username_2**: You can take a look to the recent work of Goodrich, Mitzenmacher et al. on de-amortize oblivious RAM simulations (see also their "previous work" section): [Oblivious RAM simulation with efficient worst-case access overhead](http://dl.acm.org/citation.cfm?id=2046680) and    [Cache-Oblivious dictionaries and multimaps with negligible failure probability](http://dl.acm.org/citation.cfm?id=2437302)  

---

## 0 answers

