2
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Commented Nov 14, 2017 at 23:13
  • $\begingroup$ 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. $\endgroup$
    – LeonidR
    Commented Nov 15, 2017 at 3:00
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Commented Nov 15, 2017 at 4:15
  • $\begingroup$ 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. $\endgroup$
    – LeonidR
    Commented Nov 15, 2017 at 13:39
  • $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Commented Nov 15, 2017 at 22:39

2 Answers 2

Reset to default
1
$\begingroup$

I can't say that I have a fully satisfactory answer to my question. But I spent a bit of time implementing and writing about a data-structure to solve my needs here. I call the data structure a partition map. It is really just an association lists of list of integer intervals and values. The former have nicer properties, resting on top of fairly straight-forward interval comparison logic.

Improve this answer
$\endgroup$
0
0
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – LeonidR
    Commented Nov 14, 2017 at 20:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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