Premium
Data structures for maintaining set partitions
Author(s) -
Bender Michael A.,
Sethia Saurabh,
Skiena Steven S.
Publication year - 2004
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Book series
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
ISBN - 3-540-67690-2
DOI - 10.1002/rsa.20025
Subject(s) - set (abstract data type) , computer science , programming language
Efficiently maintaining the partition induced by a set of features is an important problem in building decision‐tree classifiers. In order to identify a small set of discriminating features, we need the capability of efficiently adding and removing specific features and determining the effect of these changes on the induced classification or partition. In this paper we introduce a variety of randomized and deterministic data structures to support these operations on both general and geometrically induced set partitions. We give both Monte Carlo and Las Vegas data structures that realize near‐optimal time bounds and are practical to implement. We then provide a faster solution to this problem in the geometric setting. Finally, we present a data structure that efficiently estimates the number of partitions separating elements. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2004