Set intersection oracle
A set intersection oracle (SIO) is a data structure which represents a collection of sets and can quickly answer queries about whether the set intersection of two given sets is non-empty. The input to the problem is n finite sets. The sum of the sizes of all sets is N (which also means that there are at most N distinct elements). The SIO should quickly answer any query of the form:
"Does the set Si intersect the set Sk"?
Wikipedia contributors, "Set intersection oracle", Wikipedia, revision 1082271882, retrieved 20 November 2026, source, CC BY-SA 4.0.