8

In other words, can we model many to many relationships in a persistent data structure efficiently?

A pair of unidirectional multimaps was suggested. However, I'm not sure how this would work well for removal in a persistent data structure. Let's take the case where we have keys 1..4 to values "1".."4" and let's say they each refer to all the others, so we have two maps that look very similar for both directions:

{1 => ["2","3","4"], 2 => ["1","3","4"], ...} {"1" => [2,3,4], "2" => [1,3,4], ...}

Now we want to remove item 1 completely from the system. That requires changing one node in the first map, but it requires changing n-1 nodes in the second. For n in the thousands (which is likely in the case I'm considering this for) wouldn't that be rather expensive? Or is a multimap optimized for handling that type of a change? It's a pathological case, but still...

Quadtrees seems like a fascinating idea. I'm going to give that some more thought.

mentics
  • 6,852
  • 5
  • 39
  • 93

2 Answers2

6

The simplest way is to use a pair of unidirectional maps. It has some cost, but you won't get much better (you could get a bit better using dedicated binary trees, but you have a huge complexity cost to pay if you have to implement it yourself). In essence, lookups will be just as fast, but addition and deletion will be twice as slow. Which isn't so bad for a logarithmic operation. Another advantage of this technique is that you can use specialized maps types for the key or value type if you have one available. You won't get as much flexibility with a specific generalist data structure.

A different solution is to use a quadtree (instead of considering a NxN relation as a pair of 1xN and Nx1 relations, you see it as a set of elements in the cartesian product (Key*Value) of your types, that is, a spatial plane), but it's not clear to me that the time and memory costs are better than with two maps. I suppose it needs to be tested.

Finally, I there is a mind-blowing non-regular recursive data structure to do that, but I can't find a reference for it in english.

Edit: I just quickly pasted an adapted version of the original code for this mysterious data structure.

gasche
  • 31,259
  • 3
  • 78
  • 100
  • I'm curious enough, I would like a reference to the mind-blowing data structure even if not in English. – mentics Apr 18 '11 at 06:16
  • Interesting, though I notice there is no remove function which is where I see there being a challenge for this type of thing. Also, it appears keys and values must be different types, or at least they can't have the same values in both. – mentics Apr 18 '11 at 17:24
  • Your data structure seems to be a particular case of a [kd-tree](https://en.wikipedia.org/wiki/Kd-tree). – esope May 22 '12 at 16:50
5

Proof by construction: the bimap package for Haskell.

A Bimap is essentially a bijection between subsets of its two argument types

And how is it implemented?

data Bimap a b = MkBimap !(M.Map a b) !(M.Map b a)

As a pair of unidirectional maps.

Don Stewart
  • 137,316
  • 36
  • 365
  • 468