<p>I assume you're talking about maintaining keys, in order, in an $O(N)$-sized array, with $O(\log^2 N)$ amortized worst-case update time.</p>

<blockquote>
  <p>At the beginning how many chunks do I have? I suppose one.</p>
</blockquote>

<p>At the beginning, you will have one chunk.  Ordered file maintenance doesn't make sense for very small arrays.  Pick a smallish number (like 64 or 1024), and only start this whole chunking method once you grow above this small number.  In the small array do something naive, pushing elements around as necessary.</p>

<blockquote>
  <p>When the array is full according to the target density, do I need to grow the array and how? I suppose yes, always by a power of two (number of chunks).</p>
</blockquote>

<p>Yes, you can use standard dynamic array methods, like doubling in size when it gets too large.  </p>

<p>Some data structures like to avoid this, as a full rebuild is a really large cost.  But this isn't a big deal for us, as this data structure is highly amortized anyway.  In other words, you have to do about $\Theta(\log N)$ rebuilds of the entire data structure every $N$ insertions anyway, just to maintain balance.  This just adds an extra one.</p>

<blockquote>
  <p>Is there a possibility that a tree is impossible to rearrange according to the density? I hope not.</p>
</blockquote>

<p>No, so long as there aren't too many elements.  This is fairly easy to see---so long as you don't have too many elements, you can distribute the elements in the whole array evenly, meeting the density bound of the top array.  But the arrays have <em>looser</em> requirements as they go down.  So if the top array fits in density (and the elements are distributed evenly), the entire data structure is correctly balanced.</p>

<blockquote>
  <p>Is there any source code that I can take a loot at?</p>
</blockquote>

<p>Yes, <a href="https://github.com/dhruvbird/packed-memory-array" rel="nofollow">here</a> (this was a class project; beyond that I know almost nothing about that code).  The author of that code has a nice <a href="http://dhruvbird.blogspot.fr/2013/03/pma-packed-memory-array.html" rel="nofollow">writeup</a> of the data structure as well.  Some more recent academic work on that data structure has experimental results.  You may try looking through those as well (though of course, many are variations on the original concept).</p>

<blockquote>
  <p>When $N$ changes do I need to change the chunk size accordingly? I think so.</p>
</blockquote>

<p>It depends on what you mean.  Do you mean "when I insert a single element, so $N\gets N+1$, should I update the chunks?" then the answer is no.  On the other hand, if you mean "when I run out of room in the data structure, and double its size, rebuilding the entire data structure, should I update the chunks?" then the answer is yes.</p>

CC BY-SA 3.0
2016-02-18T15:00:06.533Z
Is there any possible comparison with hash maps? I suspect that in the long run the creation of new elements with the same hash hampers performances. This DS could perform better, *hopefully*.
senseiwa
CC BY-SA 3.0
2016-02-18T16:35:04.070Z
True, but $log^2 N$ is pretty bad performance compared to most hash functions.  There's a further issue that hash tables generally rely on elements being in a particular position, so you'd have to account for that somehow.
SamM
CC BY-SA 3.0
2016-02-18T17:54:46.300Z
I don't know if I can improve memory footprint and possibly time by employing an OFM. Rehashing is quite bad, cache unfriendly, that's why I started looking for OFM.
senseiwa
CC BY-SA 3.0
2016-02-17T21:10:44.717Z
2016-02-19T10:27:30.397Z
2016-02-19T10:27:30.397Z
SamM
<p>I believe <a href="http://link.springer.com/chapter/10.1007%2F3-540-10843-2_34" rel="nofollow">A sparse table implementation of priority queues</a></p>

<p>by Alon Itai, Alan G. Konheim, and Michael Rodeh is the source of this method.  I haven't read the whole paper, but I believe the reason these details are vaguely described is that more than one method for, eg, expanding the table is given (see pg. 424):  </p>

<blockquote>
  <p>One way to increase the size of the table is by expanding to a table of size nmk+ 1 where n
  is the number of genuine keys currently in the table. Note that n may be different that n k
  so that the sequence {nk 0 k ~} no longer plays its former role. Another possibility is to
  reconfigure when n = n k even if there is no need to do so according to the local densities
  criterion. </p>
</blockquote>

<p>You can find this paper cited in some of Demaine's work which is related, so look through the citation graph.  </p>

CC BY-SA 3.0
2016-02-18T16:40:00.400Z
Thanks, I've downloaded some articles, and now I am reading them. However, no source code seems to be in sight...
senseiwa
CC BY-SA 3.0
2016-02-17T17:06:05.417Z
2016-02-17T17:06:05.417Z
KWillets
<p>I am studying the <a href="http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-851-advanced-data-structures-spring-2012/calendar-and-notes/" rel="nofollow">Advanced Data Structures</a> material and I'd like to implement the <strong>Ordered-file maintenance</strong> data structure. I have few questions in order to start.</p>

<p>The papers rely on a static view, where the data structure already contains elements, but I need to start from scratch. The data structure partitions an array of $N$ (circa) elements into chunks of $\log N$ elements, and each chunk is ordered. When inserting, I need to choose a chunk and insert into a blank spot, if I fill the chunk, I need to move and possibly reorder elements based on density in a binary tree fashion.</p>

<ul>
<li><p>At the beginning how many chunks do I have? I suppose <em>one</em>. </p></li>
<li><p>When the array is full according to the target density, do I need to <em>grow</em> the array and how? I suppose yes, always by a power of two (number of chunks).</p></li>
<li><p>Is there a possibility that a tree is <em>impossible</em> to rearrange according to the density? I <em>hope not</em>.</p></li>
<li><p>Is there any source code that I can take a loot at? </p></li>
<li><p>When $N$ changes do I need to change the chunk size accordingly? I think so.</p></li>
</ul>

<p>Thanks!</p>

<reference-request><ds.data-structures><total-ordering><cache-oblivious>
Ordered-file maintenance
senseiwa
# Ordered-file maintenance

(Asked by: username_0 on 2016-02-16)

I am studying the [Advanced Data Structures](http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-851-advanced-data-structures-spring-2012/calendar-and-notes/) 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, where the data structure already contains elements, but I need to start from scratch. The data structure partitions an array of $N$ (circa) elements into chunks of $\log N$ elements, and each chunk is ordered. When inserting, I need to choose a chunk and insert into a blank spot, if I fill the chunk, I need to move and possibly reorder elements based on density in a binary tree fashion.

* At the beginning how many chunks do I have? I suppose *one*.
* When the array is full according to the target density, do I need to *grow* the array and how? I suppose yes, always by a power of two (number of chunks).
* Is there a possibility that a tree is *impossible* to rearrange according to the density? I *hope not*.
* Is there any source code that I can take a loot at?
* When $N$ changes do I need to change the chunk size accordingly? I think so.

Thanks!

**Tags:** reference-request, ds.data-structures, total-ordering, cache-oblivious

---

## 2 answers

### Answer by username_1 on 2016-02-17. Score: 4 | Accepted answer

I assume you're talking about maintaining keys, in order, in an $O(N)$-sized array, with $O(\log^2 N)$ amortized worst-case update time.

> At the beginning how many chunks do I have? I suppose one.

At the beginning, you will have one chunk. Ordered file maintenance doesn't make sense for very small arrays. Pick a smallish number (like 64 or 1024), and only start this whole chunking method once you grow above this small number. In the small array do something naive, pushing elements around as necessary.

> When the array is full according to the target density, do I need to grow the array and how? I suppose yes, always by a power of two (number of chunks).

Yes, you can use standard dynamic array methods, like doubling in size when it gets too large.

Some data structures like to avoid this, as a full rebuild is a really large cost. But this isn't a big deal for us, as this data structure is highly amortized anyway. In other words, you have to do about $\Theta(\log N)$ rebuilds of the entire data structure every $N$ insertions anyway, just to maintain balance. This just adds an extra one.

> Is there a possibility that a tree is impossible to rearrange according to the density? I hope not.

No, so long as there aren't too many elements. This is fairly easy to see---so long as you don't have too many elements, you can distribute the elements in the whole array evenly, meeting the density bound of the top array. But the arrays have *looser* requirements as they go down. So if the top array fits in density (and the elements are distributed evenly), the entire data structure is correctly balanced.

> Is there any source code that I can take a loot at?

Yes, [here](https://github.com/dhruvbird/packed-memory-array) (this was a class project; beyond that I know almost nothing about that code). The author of that code has a nice [writeup](http://dhruvbird.blogspot.fr/2013/03/pma-packed-memory-array.html) of the data structure as well. Some more recent academic work on that data structure has experimental results. You may try looking through those as well (though of course, many are variations on the original concept).

> When $N$ changes do I need to change the chunk size accordingly? I think so.

It depends on what you mean. Do you mean "when I insert a single element, so $N\gets N+1$, should I update the chunks?" then the answer is no. On the other hand, if you mean "when I run out of room in the data structure, and double its size, rebuilding the entire data structure, should I update the chunks?" then the answer is yes.

> **Comments:**
> **username_0**: Is there any possible comparison with hash maps? I suspect that in the long run the creation of new elements with the same hash hampers performances. This DS could perform better, *hopefully*.  
> **username_1**: True, but $log^2 N$ is pretty bad performance compared to most hash functions.  There's a further issue that hash tables generally rely on elements being in a particular position, so you'd have to account for that somehow.  
> **username_0**: I don't know if I can improve memory footprint and possibly time by employing an OFM. Rehashing is quite bad, cache unfriendly, that's why I started looking for OFM.  

---

### Answer by username_2 on 2016-02-17. Score: 2

I believe [A sparse table implementation of priority queues](http://link.springer.com/chapter/10.1007%2F3-540-10843-2_34)

by Alon Itai, Alan G. Konheim, and Michael Rodeh is the source of this method. I haven't read the whole paper, but I believe the reason these details are vaguely described is that more than one method for, eg, expanding the table is given (see pg. 424):

> One way to increase the size of the table is by expanding to a table of size nmk+ 1 where n
> is the number of genuine keys currently in the table. Note that n may be different that n k
> so that the sequence {nk 0 k ~} no longer plays its former role. Another possibility is to
> reconfigure when n = n k even if there is no need to do so according to the local densities
> criterion.

You can find this paper cited in some of Demaine's work which is related, so look through the citation graph.

> **Comments:**
> **username_0**: Thanks, I've downloaded some articles, and now I am reading them. However, no source code seems to be in sight...  

---

