Data Structures for Maintaining Set Partitions (Extended Abstract)
Michael A. Bender, Saurabh Sethia, Steven Skiena · 2000
) Michael A. Bender, Saurabh Sethia, and Steven Skiena Department of Computer Science, State University of New York at Stony Brook, Stony Brook, NY 11794-4400 USA, bender|saurabh|[email protected] 1 Introduction Each test or feature in a classication system denes a set partition on a class of objects. Adding new features renes the classication, whereas deleting features may result in merging previously distinguished classes. As an illustration, consider the set of automobile types f VW Beetle, Toyota, Lexus, Cadillac g. The feature size partitions the cars into sets of small and large cars, ff VW Beetle, Toyotag, f Lexus, Cadillac gg. The feature domestic-origin partitions the cars into ff VW Beetle, Toyota, Lexus g, f Cadillac gg. The feature ugly-shape distinguishes f VW Beetle, Cadillac g from f Toyota, Lexus g. Incorporating both size and origin induces the rened partition ff VW Beetle, Toyotag, f Lexus g, f Cadillac gg, whereas the union of all three features complet...