2012 EstimatingEntityImportanceviaCo

(Gionis et al., 2012) ⇒ Aristides Gionis, Theodoros Lappas, and Evimaria Terzi. (2012). “Estimating Entity Importance via Counting Set Covers.” In: Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD-2012). ISBN:978-1-4503-1462-6 doi:10.1145/2339530.2339640

Subject Headings:

Notes

Cited By

Quotes

Author Keywords

Combinatorial algorithms; counting; counting problems; importance sampling; miscellaneous; set cover

Abstract

The data-mining literature is rich in problems asking to assess the importance of entities in a given dataset. At a high level, existing work identifies important entities either by ranking or by selection. Ranking methods assign a score to every entity in the population, and then use the assigned scores to create a ranked list. The major shortcoming of such approaches is that they ignore the redundancy between high-ranked entities, which may in fact be very similar or even identical. Therefore, in scenarios where diversity is desirable, such methods perform poorly. Selection methods overcome this drawback by evaluating the importance of a group of entities collectively. To achieve this, they typically adopt a set-cover formulation, which identifies the entities in the minimum set cover as the important ones. However, this dichotomy of entities conceals the fact that, even though an entity may not be in the reported cover, it may still participate in many other optimal or near-optimal solutions. In this paper, we propose a framework that overcomes the above drawbacks by integrating the ranking and selection paradigms. Our approach assigns importance scores to entities based on both the number and the quality of set-cover solutions that they participate. Our algorithmic contribution lies with the design of an efficient algorithm for approximating the number of high-quality set covers that each entity participates. Our methodology applies to a wide range of applications. In a user study and an experimental evaluation on real data, we demonstrate that our framework is efficient and provides useful and intuitive results.

References

;

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2012 EstimatingEntityImportanceviaCo	Theodoros Lappas Evimaria Terzi Aristides Gionis			Estimating Entity Importance via Counting Set Covers				10.1145/2339530.2339640		2012