Speed-Up Algorithms for Happiness-Maximizing Representative Databases

摘要

Helping user identify the ideal results of a manageable size k from a database, such that each user's ideal results will take a big picture of the whole database. This problem has been studied extensively in recent years under various models, resulting in a large number of interesting consequences. In this paper, we introduce the concept of minimum happiness ratio maximization and show that our objective function exhibits the property of monotonictity. Based on this property, two efficient polynomial-time approximation algorithms called Lazy NWF-Greedy and Lazy Stochastic-Greedy are developed. Both of them are extended to exploit lazy evaluations, yielding significant speedups as to basic RDP-Greedy algorithm. Extensive experiments on both synthetic and real datasets show that our Lazy NWF-Greedy achieves the same minimum happiness ratio as the best-known RDP-Greedy algorithm but can greatly reduce the number of function evaluations and our Lazy Stochastic-Greedy sacrifices a little happiness ratio but significantly decreases the number of function evaluations.