Anytime Algorithms for Mining Groups with Maximum Coverage

Vadlamudi, S.G., Chakrabarti, P.P. and Sarkar, S.

Mining maximal groups from spatio-temporal data of mobile users is a well known problem. However, number of such groups mined can be very large, demanding further processing to come up with a readily usable set of groups. In this paper, we introduce the problem of mining a set of K maximal groups which covers maximum number of users. Such a set of groups can be useful for businesses which plan to distribute a set of K offers targeting groups of users such that a large number of users are covered. We propose efficient methods to solve this hard problem, which do not mine the total set of groups apriori (avoiding the large amount of time consumed upfront), instead intelligently decide during their execution as to which area of the search space is to be explored to mine the next group so that a set of K groups covering large number of users is quickly produced, and then improve the K-set as time progresses (anytime nature). Experimental results on several synthetic spatio-temporal datasets as well as real datasets that are publicly available show the efficacy and scalability of the proposed methods across various parametric inputs.

Cite as: Vadlamudi, S.G., Chakrabarti, P.P. and Sarkar, S. (2012). Anytime Algorithms for Mining Groups with Maximum Coverage. In Proc. Data Mining and Analytics 2012 (AusDM 2012) Sydney, Australia. CRPIT, 134. Zhao, Y., Li, J. , Kennedy, P.J. and Christen, P. Eds., ACS. 209 - 220

(from crpit.com) (local if available)