# Data structure optimized for merging maps on partitions

My question is a request for literature or pointers that address the following abstracted problem. If I have a finite set (ex. {1..10}) over which I'd like to maintain several "partition maps":

• m1 = {1..5}=1, {6..10}=2
• m2 = {1..3,8..10}=3, {4..7}=4.

Afterwards I'd like to merge (generalize the operation, but use addition for demonstration) these maps:

m1 + m2 = m3 = {1..3}=4,{4,5,8..10}=5,{6,7}=6.

If n is the size of universal set, and k << n the size of the range of the maps. How does one get performance (and space) closer to O(k) as opposed to O(n) (store an array)?

Edit (2017-11-14): I'm mainly interested in merge performance, lookup can be slow. To sharpen the question, there are a couple of approaches to this problem that don't quiet address this trade off:

Edit (2017-11-15): The application where I'm using this performs millions of merges. In the most common instance I have 4 of these maps and compute a new map. The keys are different states and the values are actually probabilities. The probabilities are discretized which is why lots of different states have the same values. It is a form of "compressed" computations. I can use an array to store these values, but this compressed form provides 100x performance currently, but I'm looking for a technique to improve upon that (I need to do billion of merges). As @D.W. described below, batched techniques would also be of interest.

• If all you care about is merge performance, you can get $O(1)$-time merges (at the cost of $O(n)$-time lookups) by just using a linked list to store each partition. You can concatenate two linked lists in $O(1)$ time, so the merge becomes very fast. – D.W. Nov 14 '17 at 23:13
• We need to merge two maps by aligning the keys. We merge two elements iff their keys (the elements of the finite set at the beginning, or the integers that I'm using as their stand-in) match. Using a linked-list would work iff the order of the elements is always aligned such that intervals match. One would also, still, need to take steps to make sure that the list has no redundant elements. I have code that does exactly this, but I'm looking for a more principled approach. – LeonidR Nov 15 '17 at 3:00
• No, you don't have to do any of that during the merge operation. You can just concatenate the two lists and handle that during the lookup operation. – D.W. Nov 15 '17 at 4:15
• True, but then the merge wouldn't be performing the work that I want it to perform. At some point I'm going to extract the value (actually I'd like to convert them back into an array ordered by the sets), but after, literally, several million, merges. – LeonidR Nov 15 '17 at 13:39
• It might be possible to find an algorithm that handles an entire batch of merges more efficiently than handling one merge at a time. If that's what you want, it might help to edit the question to state that fact. – D.W. Nov 15 '17 at 22:39

Assuming that partitions are composed of ranges of consecutive integers (as in your example), use an interval tree. If there are $k$ intervals in the partitions, then the data structure takes $O(k)$ space. You can perform a lookup operation in $O(\log k)$ time. Taking the union of two maps of size $k_1,k_2$ can be done in $O(k_1+k_2 \log (k_1+k_2))$ time.
• Thanks for the quick response. My current solution uses intervals arranged in sorted lists. The union algorithm that you have in mind is to simultaneously, in order, fold over the tree's inserting the result into the tree of construction? How would that handle the merging of 2 elements that match in range space? Notice that in my example to effectively constrain the grow of k, the[8..10] interval is appended to [4,5]. As I had just edited, I am not interested in lookup performance at all, just unions. – LeonidR Nov 14 '17 at 20:29