I have a problem that I think should have been studied. I am looking for algorithms for it.

Each item is a set of key-value pairs. Let $x$ be an item and $F$ be a set of items.

Each key and each value can appear multiple times. The number of possible keys and possible values can be arbitrary large.

We are given $x$ and $F$. We want to find all those items $y$ in $F$ such that $y.val \subseteq x$.

For example,

$x = \{(a,1), (b,2), (c,3), (d,4)\}$

$F= \{$
$(A, \{(a,1)\}), $
$(B, \{(a,1), (b,2)\}),$
$(C, \{(a,1), (b,3)\}),$
$(D, \{(b,2), (c,3), (d,4)\}),$
$(E, \{(a,1), (b,2), (c,3), (d,4)\}),$
$(F, \{(a,1), (b,2), (c,3), (d,4), (e,5)\}),$
$(G, \{(a,1), (b,2), (c,3), (e,5)\})$

The answer is: $A$ yes, $B$ yes, $C$ no (right keys, wrong values), $D$ yes, $E$ yes (exact match), $F$ no, $G$ no.

Has this problem been studied?

The problem seems similar to finding features from a DNA sequence or detecting plagiarism in a document.

  • 1
    $\begingroup$ Please state the computational problem that you want to solve without code. For example: I am given input [the description of what is given], and I want to compute [the description of what you want to compute]. Check other questions for examples. $\endgroup$ – Kaveh Jun 18 '13 at 3:18
  • $\begingroup$ Will there generally be a total order on the set of values? $\hspace{2.51 in}$ Will there generally be a total order on the set of keys? $\:$ $\endgroup$ – user6973 Jun 18 '13 at 5:34
  • $\begingroup$ @Kaveh I thought code would be helpful because I'm unfamiliar with the vocabulary used in theoretical computer science. Regardless here's a stab... Given an item defined by an unknown number of key value pairs and a feature set of items defined the same way, find the items in the feature set that are a subset of the given item. Even help defining this problem would be a great help. Thanks $\endgroup$ – wroscoe Jun 18 '13 at 6:18
  • 1
    $\begingroup$ there is so much extraneous information it seems. why does it matter these are key-value pairs? you have a set $S$ and a collection of sets $\{T_1, ..., T_n\}$, and you want to output all $T_i$ which satisfy $T_i \subseteq S$. the key word for you is hashing. $\endgroup$ – Sasho Nikolov Jun 18 '13 at 17:32
  • 1
    $\begingroup$ Oh come on..hash each pair in $x$ and store them in the hash table. now for each item in $F$, hash each of its pairs and check if it is equal to a pair in $x$. The expected running time is linear in input size. $\endgroup$ – Sasho Nikolov Jun 19 '13 at 4:19

The most straightforward answer I can think of, but unsure about running times:

def find_matching(d, f):
      matching = []
      dSet = set(d.items())
      for k in f:
        if set(f[k].items()).issubset(dSet):
      return matching
  • $\begingroup$ 6 character edit requirement $\:$ gaaah $\;\;\;$ $\endgroup$ – user6973 Jun 18 '13 at 7:29
  • $\begingroup$ This is not Stack Overflow. For questions about algorithms you should not assume people know any particular programming language. Please explain your algorithm in plain English or pseudo-code. $\endgroup$ – Kaveh Jun 18 '13 at 17:21

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.