I'm looking for articles on the cache complexity of folds of non-constant space. My use case is Borwein's factorial algorithm. String concatenation would be a more extreme case. I'm aware of dynamic ...
I'd like to know more about real performances of data structures, in particular two families attract my interests: hash tables cache oblivious My researches didn't find any "comprehensive" (let me ...
I am studying the Advanced Data Structures material and I'd like to implement the Ordered-file maintenance data structure. I have few questions in order to start. The papers rely on a static view, ...
I've been reading the following paper: David Karger, Eric Lehman, Tom Leighton, Rina Panigrahy, Mathew Levine, Daniel Lewin, "Consistent Hashing and Random Trees: Distributed Caching Protocols for ...
Background The external memory, or DAM model, defines the cost of an algorithm by the number of I/Os it performs (essentially, the number of cache misses). These running times are generally given in ...
I'm interesting in learning more about cache-oblivious algorithms and data structures, but there are so many papers out there that I honestly don't know where to start. I've found Prokup's original ...
Is there a simple and cache-oblivious data structure that solves the dynamic predecessor problem for strings of length exactly $k$ over an alphabet $A$ in worst-case $O((k\log A)/B + \log n)$ memory ...