4
$\begingroup$

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, 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!

$\endgroup$
4
$\begingroup$

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 (this was a class project; beyond that I know almost nothing about that code). The author of that code has a nice writeup 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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – senseiwa Feb 18 '16 at 15:00
  • $\begingroup$ 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. $\endgroup$ – SamM Feb 18 '16 at 16:35
  • $\begingroup$ 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. $\endgroup$ – senseiwa Feb 18 '16 at 17:54
2
$\begingroup$

I believe A sparse table implementation of priority queues

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.

$\endgroup$
  • $\begingroup$ Thanks, I've downloaded some articles, and now I am reading them. However, no source code seems to be in sight... $\endgroup$ – senseiwa Feb 18 '16 at 16:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.