Linked Questions

7 votes
1 answer

Data structure for testing all subsets of a query for membership

Is there a data structure that efficiently supports the following operations? Add set Query whether any subset of a set has been added. This could be implemented with linear overhead by testing ...
Elliot Gorokhovsky's user avatar
1 vote
1 answer

Efficient search of a large set of documents to find documents that only contain a particular set of words

Say I have a set of documents $D = \{d_1, d_2, \dots, d_n\}$ in some natural language. Each document $d_i$ consists of a subset of words from a word pool $W = \{w_1, w_2, \dots, w_k\}$. For example, $\...
Xavier Taylor's user avatar
1 vote
1 answer

What data structure/s can I use for fastest lookup of a permutation between two arrays of pairs (preserving order)?

I'm trying to figure out a more efficient solution to the following problem. Dataset: A set of arrays of key-value pairs (K, V). The arrays have varying lengths, ...
Klaycon's user avatar
  • 111
2 votes
1 answer

How to speed up finding a subset of a given set?

Is there a data indexing technique that speeds up finding subsets of a given set in a collection, or do I always have to scan all of the data? For example, let's say that I have a collection of sets: ...
Bartosz Mikulski's user avatar
5 votes
1 answer

Among a number of sets, how to find the one that includes the highest number of other sets?

I have a large number of sets, A, B, C, ... where each set includes a few integers. I would like to find the set that includes the highest number of other sets. A ...
Matt's user avatar
  • 153
3 votes
0 answers

Map-like data structure with subsets as keys

I am looking for a map-like data structure with the following properties: it uses subsets of some set S as keys. The size of S is potentially unbounded, but does not change during the runtime the ...
Minop's user avatar
  • 131
1 vote
0 answers

Find sets which are subsets of the given search set?

The problem is the following: You are given a collection( set, list, whatever ) C of sets, and you are given a search set S. We want to find among all sets in C the ones which are subsets of S. Hence, ...
Vladimir's user avatar
  • 121
2 votes
0 answers

Efficiently finding all pairs of disjoint sets

Say we have the letters $\Omega = \{1,2,\dots n\}$, and two sets of subsets of $\Omega$, $S_1, S_2$. I want to find $S_1 \cdot S_2 := \{(s_1,s_2) \in S_1 \times S_2: s_1 \cap s_2 = \emptyset \}$. ...
Zach Hunter's user avatar
3 votes
0 answers

Data structure for finding greatest lower bound with respect to a partial order

I have some partial order $\preceq \,\,\subset A \times A$, I'd like a data structure with the following operations: $Insert(a, x, T)$: add $(a, x)$ to the collection $T$ $Find(x, T)$: find the ...
Jake's user avatar
  • 3,800
2 votes
0 answers

Poset data structure to find least element, greater or equal to given

Let $A$ be a finite set, and $S \subset \mathcal{P}(A)$. Is there a data structure for $S$ that would allow to quickly retrieve an element $q \in S $, given a key $p \in \mathcal{P}(A)$, such that $q$ ...
Zyx's user avatar
  • 145