CCE Faculty Articles

Minimum Spanning Tree Partitioning Algorithm for Microaggregation

Document Type

Article

Publication Title

IEEE Transactions on Knowledge and Data Engineering

ISSN

1041-4347

Publication Date

7-1-2005

Abstract

This paper presents a clustering algorithm for partitioning a minimum spanning tree with a constraint on minimum group size. The problem is motivated by microaggregation, a disclosure limitation technique in which similar records are aggregated into groups containing a minimum of k records. Heuristic clustering methods are needed since the minimum information loss microaggregation problem is NP-hard. Our MST partitioning algorithm for microaggregation is sufficiently efficient to be practical for large data sets and yields results that are comparable to the best available heuristic methods for microaggregation. For data that contain pronounced clustering effects, our method results in significantly lower information loss. Our algorithm is general enough to accommodate different measures of information loss and can be used for other clustering applications that have a constraint on minimum group size.

DOI

10.1109/TKDE.2005.112

Volume

17

Issue

7

First Page

902

Last Page

911

Link to Full Text

Find in your library

Share

COinS