Name
Abstract | ||
|---|---|---|
The Sparse Table is a data structure for controlling density in an array which was first proposed in 1981 and has recently reappeared as a component of cache-oblivious data structures. All existing variants of the Sparse Table divide the array into blocks that have a calibrator tree above them. We show that the same amortized complexity can be achieved without this auxiliary structure, obtaining a canonical data structure that can be updated by conceptually simpler algorithms. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1016/j.ipl.2007.07.001 | Inf. Process. Lett. |
Keywords | DocType | Volume |
amortized complexity,canonical data structure,conceptually simpler algorithm,cache-oblivious data structure,calibrator tree,canonical density control,existing variant,sparse table,data structure,auxiliary structure,analysis of algorithms,data structures | Journal | 104 |
Issue | ISSN | Citations |
6 | 0020-0190 | 3 |
PageRank | References | Authors |
0.37 | 8 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alon Itai | 1 | 2971 | 620.32 |
| Irit Katriel | 2 | 176 | 13.72 |