The problem at hand is that I have a large number of large collections whose intersections are ordinarily quite small relatively. I'd like to find an auxiliary data structure that allows for efficient computation of those intersections. For the sake of argument everything fits in RAM somehow, everything is an integer, etc.... I.e., filling in the blanks for:
class MySet:
def __init__(self, collection: List[int]):
pass
def intersection(self, other: MySet) -> List[int]: # or -> MySet if we also support iteration
pass
a = MySet(range(0, 10**10, 2)) # might be slow
b = MySet(range(1, 10**10, 2)) # might be slow
res = a.intersect(b) # ought to be nearly instantaneous since the intersection is empty
The problem I'm facing is that implementations I'm aware of have a runtime proportional to at least the size of the smallest set being intersected. E.g., for sets A and B runtimes of O(min(|A|, |B|)) and O(|A| + |B|) (often with polylogarithmic factors) are what you might expect from hashsets, sorted trees, or other common solutions.
If |A.intersect(B)| << min(|A|, |B|) though it would be nice to have a solution with runtime proportional to the result size rather than the size of the intermediate data structures, especially if min(|A|, |B|) is still prohibitively large for a given application.
I'm not certain whether the problem is solvable or not, and I'm curious in results to the contrary as well. At least probabilisticly we have algorithms like the hyperloglog which efficiently support approximately counting the intersection, and if the data has certain properties like being sparsely interleaved then there are also good solutions, but I haven't been able to find a suitable general-purpose algorithm.
tldr;
Are there set-like data structures supporting intersection in O(|A.intersect(B)|) time rather than O(min(|A|, |B|)) time?