I have a very large amount of objects that look like this:
DataDict = {
id1: {"a": true, "b": true, "bc": true, "hgf": true},
id2: {"bcwe": true, "nKNNn": true, "mjj": true, "AAt": true},
id3: {"h": true, "a": true, "mjj": true, "ABwAU": true},
id4: {"wvzy": true, "zzba": true, "abc": true, "a": true},
...
}
or just (as a set of sets, note that id
s may be excluded)
DataSet = {
{"a", "b", "bc", "hgf"},
{"bcwe", "nKNNn", "mjj", "AAt"},
{"h", "a", "mjj", "ABwAU"},
{"wvzy", "zzba", "abc", "a"},
...
}
Let M
denote the total number of objects in DataDict
(or subsets in DataSet
), and let N
denote the total number of unique names of properties found in DataDict
(or the total number of unique strings found in DataSet
).
The question is: given the set of strings {string1, string2, string3, ...}
, how to get the Yes/No answer (assuming that there is a way to prepare the “index” for DataSet
) to the “Does DataSet
contain at least one subset that contains string1
AND string2
AND string3
AND ...?” question as fast as possible?
In another form, the question is: given the array A = [string1, string2, string3, ...]
, how to build the index (data structure) for DataDict
that allows to quickly determine if it contains at least one object obj
(I don’t care which object to choose, moreover, I don't want to return this object, all I want is that the function should return true
if such an object exists, and false
if not) such that DataDict.obj.string1 is true AND DataDict.obj.string2 is true AND DataDict.obj.string3 is true AND ...
?
The only way that I see is to build the index like this:
{
"a": [1, 3, 4],
"abc": [4],
...
}
and, for example, if A = ["a", "abc"]
, then I need to find the intersection of two arrays ([1, 3, 4]
and [4]
), but stop as soon as one common element is found and return true
(if there are no common elements, return false
). But these operations are very costly and time-consuming, which often leads to the unacceptable waiting time. Is there a way that guarantees a significantly better performance for all cases?
It would be extraordinarily nice if there exists a solution that (assuming that the index already exists) finds the answers depending on A.length
time. The good solutions may depend on log M
or log N
or even close to log M
multipled by log N
, but I cannot imagine how to find such a solution...