go-v.orgcodex
Menu
Page tools

codex · Philosophy

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.

More Philosophy · Search the codex