2
$\begingroup$

Multi Key Multi Value Dictionary is a dictionary in which each value is associated with a set of keys and each key is associated with a set of values. Several values can be associated with the same key, and several keys can be associated with the same value.

Let's define a $get$ operation over Multi Key Multi Value Dictionary accepting set of keys as an input and returning set of all values from the dictionary such that every value in the resulting set is associated with all of the input Keys; i.e. for each key in its input $get$ operation takes the set of its associated values and produces intersection of all those recorded sets of values.

Naïve algorithm's time-complexity would be $\mathrm{O} (\min\limits_{i \in 1...N} (n_i) \cdot k \cdot \log (N))$. The naïve algorithm finds out the key from input with the highest selectivity, go through its set of values and add only these values to result that have all other keys as well.

But is there any better algorithm in which there is no $\min\limits_{i \in 1...N} (n_i)$ component in its time complexity, but the number of values in result instead of it? E.g. is time-complexity $\mathrm{O} (n \cdot \log (N) + k \cdot \log (N))$ feasible for $get$? Also I assume that the space-complexity of the algorithm must be strictly less than $\mathrm{O} (N \cdot 2^K)$.

Here:

  • $n$ - number of values returned by $get$ operation,
  • $n_i$ - number of values associated with $i$th key from input,
  • $N$ - number of values in the dictionary,
  • $k$ – number of keys provided as an input to $get$ operation,
  • $K$ – number of keys in the dictionary.

Here is the motivation for such an algorithm. Let's say we are looking for a person in a dictionary using several traits like First Name, Last Name, Zip code and so on. There could be millions of people for each single trait. But there would be only couple of people having all the traits at the same time. So the lookup algorithm shouldn’t iterate over all values of one trait, even if the trait with highest selectivity is chosen. There could be no Key with good enough selectivity by its own.

$\endgroup$
  • $\begingroup$ OK. So it sounds like you have a bipartite graph; a query is a set $S$ of left-vertices, and you want to output the set $T$ of right-vertices $r$ such that there's an edge $(s,r)$ for all $s \in S$, i.e., $T= \{r : (s,r) \in E \forall s \in S\}$. Let me know if I got that wrong. $\endgroup$ – D.W. Feb 11 '17 at 3:36
  • $\begingroup$ @D.W., that's correct. $\endgroup$ – Volodymyr Frolov Feb 11 '17 at 14:27

Your Answer

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

Browse other questions tagged or ask your own question.