patternMinor
state of the art of subset, set containment and partial match queries
Viewed 0 times
containmentthematchartstatepartialandqueriessubsetset
Problem
The subset query problem is defined as:
Given a list
I was wondering what are the best known algorithms to solve this problem. I couldn't find any recent publications, just this work from 2002:
Subset Queries
There it is stated, that the subset query problem is equivalent to the set containment problem as well as the partial match problem.
Any help would be appreciated.
Given a list
D of size N where the entries are subsets of a universe with m elements, create a datastructure that detects for every query-set Q if there exists a set P in D so that Qis a subset of PI was wondering what are the best known algorithms to solve this problem. I couldn't find any recent publications, just this work from 2002:
Subset Queries
There it is stated, that the subset query problem is equivalent to the set containment problem as well as the partial match problem.
Any help would be appreciated.
Solution
I am not sure if this is "state of the art" but take a look at this paper Efficient subset and superset queries.
Context
StackExchange Computer Science Q#75915, answer score: 4
Revisions (0)
No revisions yet.