Linked Questions
10 questions linked to/from state of the art of subset, set containment and partial match queries
7
votes
1
answer
377
views
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 ...
1
vote
1
answer
262
views
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, $\...
- 111
1
vote
1
answer
182
views
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, ...
- 111
2
votes
1
answer
161
views
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:
...
- 121
5
votes
1
answer
91
views
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 ...
- 153
3
votes
0
answers
143
views
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 ...
- 131
1
vote
0
answers
100
views
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, ...
- 121
2
votes
0
answers
74
views
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 \}$. ...
- 51
3
votes
0
answers
65
views
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 ...
- 3,800
2
votes
0
answers
36
views
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$ ...
- 145