Quick Connected Components: A Data Clustering Algorithm

Several projects in the Advanced Systems Processing Laboratory (4622) make extensive use of 1- Connected Component algorithms. In these algorithms, data clusters must be extracted from large volumes of input data on the basis of single threaded links between the data items. In addition, the nature of the domain studied in our laboratory is such that these clusters tend to persist over time as new input data is gathered. To address the need for rapid clustering in such a domain, two complementary algorithms have been developed. These algorithms, the history-based Cluster Allocator and the Quick Connected Components algorithm, provide an average case performance of O (n) time complexity.