A NEW AND VERSATILE METHOD FOR ASSOCIATION GENERATION

Current algorithms for finding associations among the attributes descr ibing data in a database have a number of shortcomings: 1. Their perfo rmance time grows dramatically as the minimum support is reduced. Cons equently, applications that require associations with very small suppo rt have prohibitively large running times. 2. They assume a static dat abase. Some applications require generating associations in real-time from a dynamic database, where transactions are constantly being added and deleted. There are no existing algorithms to accommodate such app lications. 3. They can only find associations of the type where a conj unction of attributes implies a conjunction of different attributes. I t turns out that there are many cases where a conjunction of attribute s implies another conjunction only in case certain other attributes ar e excluded. To our knowledge, there is no current algorithm that can g enerate such excluding associations. We present a novel method for ass ociation generation, that answers all three above desiderata. Our meth od is inherently different from all existing algorithms, and especiall y suitable to textual databases with binary attributes. At the heart o f our algorithm lies the use of subword trees for quick indexing into the required database statistics. We tested our algorithm on the Reute rs-22173 database with satisfactory results. (C) 1997 Published by Els evier Science Ltd. All rights reserved.