Efficient discovery of optimal word-association patterns in large text databases
We study efficient discovery of proximity word-association patterns, defined by a sequence of strings and a proximity gap, from a collection of texts with the positive and the negative labels. We present an algorithm that finds all d-strings k-proximity word-association patterns that maximize the number of texts whose matching agree with their labels. It runs in expected time complexity O(k(d-1) n log(d) n) and space O(k(d-1)n) with the total length n of texts, if texts are uniformly random strings. We also show that the problem to find one of the best word-association patterns with arbitrarily many strings is MAX SNP-hard.
optimization text databases proximity word-association patterns data mining discovery science