Increasing the efficiency of data mining algorithms with Breadth-first marker propagation
John M. Aronis, Poster J. Provost · 1997
This paper describes how to increase the efficiency of inductive data mining algorithms by replacing the central matching operation with a marker propagation technique. Breadth-first marker propagation is most beneficial when the data are linked to hierarchical background knowledge (e.g., tree-structured attributes), or when the attributes describing the data have many values. We support our claims analytically with complexity arguments and empirically on several large data sets. We also point out other efficiency gains, including reduced memory management overhead, which facilitate mining massive tape archives. Introduction Inductive algorithms have proven to be valuable, practical tools for automated discovery in science and business, but users run into difficulties applying the algorithms to large, complex problems. For example, a large data set may have thousands of values for a location field (e.g., zip). Unfortunately, most existing algorithms are prohibitively ine...