17
$\begingroup$

Is there any data structure that maintain a collection of set (of finite ground set) supporting the following operations? Any sublinear running time will be appreciated?

  1. Init an empty set.
  2. Add an element to a set.
  3. Given two set, report whether they intersect.
$\endgroup$

migrated from cstheory.stackexchange.com Apr 26 '13 at 10:18

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 1
    $\begingroup$ This is a very general question, because any data structure can support those operations with finite domain. Could you be a little more specific ? Eg. What complexity you need, what are you willing to sacrifice to get set operations etc. $\endgroup$ – Bartosz Przybylski Apr 26 '13 at 10:40
11
$\begingroup$

If each set maintains a record of what other sets exist, and you have a total of $s > 0$ sets, you can easily turn any data structure for a collection (e.g. binary search trees, etc.) into one where you can have retrieval of an element of the intersection of two sets in time $O(\log s)$.

  • Each set should have a unique identifier from some totally ordered set. If you explicitly name your sets $S_1, S_2, \ldots$ then the identifier could just be the index.

  • You should implement a "registry" of the sets; a data structure which maintains a collection of all of the sets which you have defined. The registry should be implemented as a search-tree data structure, to allow easy retrieval (e.g. if you wish to delete the set) and linear-time traversal of the sets.

  • Each set $S_j$ also maintains an "index" of each of the other sets — not a copy of them, but rather a data structure which is indexed by the labels of the other sets. This index will be used to maintain, for each set $S_k$, a binary search tree of all of the elements of $S_j \cap S_k$. (The two sets $S_j$ and $S_k$ share one copy of that search tree.)

Initialization

Initialization of a set $T = \varnothing$ consists of $O(1)$ operations to initialize the tree of its elements, $O(s)$ operations as you initialize (copying from the registry) the index for the set $T$, and $O(s \log s)$ operations as you traverse the registry to add $T$ into the indices of each of the other sets $S_j$. In the index of $T$, we create search trees representing $T \cap S_j = \varnothing$ for the other sets $S_j$; we copy the same pointer for the index of $S_j$.

Adding an element to a set $T$

Adding some $x \in V$ to the set $T$ takes time $O(\log n_T)$ as usual, where $n_T = |T|$. We also test for membership of $x$ in each of the other sets $S_1, S_2, \ldots$, which takes time $$O(\log n_{S_1} + \log n_{S_2} + \cdots) \subseteq O(s \log n) ,$$ where $n = |V|$ is the size of the universe (or of the largest set $S_j$) and $s$ is the number of sets in the registry. For each set $S_j$ such that $x \in S_j$, also insert $x$ into the index for the set $S_j \cap T$. For each such set $S_j$, this takes $O(\log s + \log n_T)$ time, to look up $S_j$ in the index of $T$ and to insert $x$ in $S_j \cap T$; across all sets $S_1, S_2, \ldots$ this takes time $O(s \log s + s \log n_T)$. If we suppose that the number of sets $S_j$ is much less than the size of the universe $V$ (that is, if we suppose $s \ll n$), the total time for element insertion is then $O(s \log n)$.

If you do not allow duplicates in sets, we can save time in the case that $x \in S$ already by forgoing the membership test and insertions for the other sets $T$. "Insertion" in the case that $x$ is already present then takes time only $O(\log n_T)$.

Intersection testing

The index of each set is maintained precisely in order to allow quick evaluation of whether or not two sets $S_j$ and $S_k$ intersect. For a set $S_j$, simply by checking its index for the set $S_k$, we can not only determine in time $O(\log s)$ whether or not $S_j$ intersects $S_k$, but we can also retrieve a binary tree containing the entire set $S_j \cap S_k$.

Element Removal

To delete an element $x$ from a set $T$, we remove it not only from the search tree for $T$ itself, but from each of the intersections $S_j \cap T$ for the sets $S_j$ in its index. This takes time $O(s \log n_T)$, where $n_T = |T|$.

Set Deletion

Because of the overhead of searching the registry, if you have many sets, it may be desirable to delete sets once they are no longer needed. By traversing the entire registry, we may delete $S$ from the index of all other sets $S_j$ in time $O(sn_T)$, dominated by the cost of deleting the search tree representing $S_j \cap T$ for each of the other sets $S_j$, where $n_T = |T|$.

Remarks

If you expect only to implement a constant number of sets, then the above run-times reduce to:

  • initialization: $O(1)$

  • element insertion: $O(\log n)$

  • intersection testing (and retrieval of the intersection): $O(1)$

  • element removal: $O(\log n_T)$

  • set deletion: $O(n_S)$

where $n$ is the size of the largest set in the registry, and $n_T = |T|$ for the set $T$ which you are operating on.

If you expect to have $O(|V|)$ sets, where $V$ is your universe, you may need a different data structure if you want these operations to operate in sub-linear time. However, if you have pairs of sets whose intersection you know you will never test, you might be able to reduce the size of the index for the sets (by not including any sets whose intersection you will test) or use more than one registry (one for each collection of sets whose intersection you might test). In fact, a registry is only useful if you want centralized control of ensuring that each pair of sets has a record of each other in the index: it may be practical in some cases, at the initialization of a set $S$, simply to record ad hoc each new set into the indices of the other sets $T$ whose intersection with $S$ you are interested in.

$\endgroup$
5
$\begingroup$

There are data structures that allow you to do this in less than linear time, even for worst-case inputs. See http://research.microsoft.com/pubs/173795/vldb11intersection.pdf (and the papers references in there).

If your two sets S and T have a large intersection and you have a dictionary for S, looking up elements of T in random order should quickly give you a common element. The most difficult case is when the intersection size is 0 or 1.

$\endgroup$
3
$\begingroup$

Usually your programming language of choice will support a data structure with unique elements. In general there are three popular approaches: Trees, Hashes and Bitmasks. Tree elements must be comparable, Hash elements must be hashable and Bitmask elements must have some way of conversion to integers.

A tree-set will support insertion in O(log n) and intersection testing in Worst Case O(n log n).

A hash-set will support insertion in Amortized O(1*h) where 'h' is the running time of the hashing algorithm, and intersection test in Worst Case O(n).

Bitmask sets are not generally used like tree- and hash-sets.

$\endgroup$
  • 2
    $\begingroup$ This would be a decent Stack Overflow answer, but here we'd like some detail on how and why it works. $\endgroup$ – Raphael Apr 26 '13 at 13:17
2
$\begingroup$

If your case allows false positive answers, I'd use Bloom Filter with a single hash function.

You can implement it as follows :

Init an empty set

  • $B$ = bit array of $n$ bits, all set to 0.($n$ should be chosen according to the number of possible elements)

Add an element to a set.

  • $B[hash(element)]=1$

Given two sets(B1,B2), report whether they intersect.

  • check if $B1$ $AND$ $B2$ $=$ $0$

Complexity

  • If $n$ is not too big, all operations are $O(1)$.
$\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.