# Find all items which are subsets of an item

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.

• 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. – Kaveh Jun 18 '13 at 3:18
• 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? $\:$ – user6973 Jun 18 '13 at 5:34
• @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 – wroscoe Jun 18 '13 at 6:18
• 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. – Sasho Nikolov Jun 18 '13 at 17:32
• 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. – Sasho Nikolov Jun 19 '13 at 4:19

• 6 character edit requirement $\:$ gaaah $\;\;\;$ – user6973 Jun 18 '13 at 7:29