3
$\begingroup$

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.

I asked this problem in theoretical CS stack exchange and did not get very helpful answers. https://cstheory.stackexchange.com/questions/18052/find-all-items-which-are-subsets-of-an-item

$\endgroup$
  • 1
    $\begingroup$ Does it matter that they're key-value pairs? It looks like you're only concerned with whether $A$ through $G$ contain the same ordered pairs as $x$. In other words, why not just say $x = \{x_1, x_2, x_3, x_4,\}$ and $G = \{x_1, x_2, x_3, z\}$ where $z \neq x_i$? $\endgroup$ – Patrick87 Jun 20 '13 at 15:40
  • $\begingroup$ As @Patrick87 points out, there is nothing specific in your question that relies on the form of the values of elements of $F$. $\endgroup$ – András Salamon Jun 21 '13 at 8:35
  • $\begingroup$ @Patrick87 This is the nature of my problem so I included it. I thought that having keys could help with the solution. This seems not to be the answer. $\endgroup$ – wroscoe Jun 21 '13 at 20:33
3
$\begingroup$

Your problem is the same one faced by SAT solvers who want to eliminate subsumed clauses from a CNF formula. Any clause $B$ that contains a superset of the literals of another clause $A$ in the formula is redundant and can be removed without changing the satisfiability of the formula. We say $A$ subsumes $B$, so $B$ can be discarded. Instead of single valued literals, you have these item tuples but it is the same problem as finding $A$.

The algorithms used are refinements of the naive algorithm, where you iterate through each element of a potential subset, checking to see if it occurs in $x$. If you sort $x$'s items you can reduce the linear time search to log $\vert{x}\vert$. If you use a hashtable to store $x$'s items you can have amortized constant time for each search. Because of the hashing overhead, save this optimization for large sets. Bitmask signatures for each set allow you to do a cheap initial check, only doing the expensive iteration and searching of $x$ if the bitmaps can't rule out a subset match.

$\endgroup$

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.