algorithm - Contains superset -

algorithm - Contains superset -

i'm on hunt construction ("set of sets") allow me efficiently check whether contains superset of set.

example: = { 1, 2 } b = { 2, 3 } c = { 1, 3 } d = { 1, 2, 3 }

set of sets s1 = { a, b } , s2 = { d }

s1 contains => true s1 contains c => false s2 contains => true

the solution should have low complexity (not asymptotic) possible.

use dictionary convert between possible distinct elements , positions in bitmap. store each set bitmap.

taking union of set of sets question of oring bit maps.

checking whether 1 set subset of set of sets checking anding bit maps results in smaller set's bitmap.

these operations should fast. , if really ambitious, start http://en.wikipedia.org/wiki/general-purpose_computing_on_graphics_processing_units , figure out how move computation gpu.

if had larger sets , ok getting wrong answer, should bloom filters. lets right answers shorter bitmaps.

algorithm set