On the Complexity of Mining Itemsets from the Crowd Using Taxonomies

Abstract :

We study the problem of frequent itemset mining in domains where data is not recorded in a conventional database but only exists in human knowledge. We provide examples of such scenarios, and present a crowdsourcing model for them. The model uses the crowd as an oracle to find out whether an itemset is frequent or not, and relies on a known taxonomy of the item domain to guide the search for frequent itemsets. In the spirit of data mining with oracles, we analyze the com- plexity of this problem in terms of (i) crowd complexity, that measures the number of crowd questions required to iden- tify the frequent itemsets; and (ii) computational complexity, that measures the computational effort required to choose the questions. We provide lower and upper complexity bounds in terms of the size and structure of the input taxonomy, as well as the size of a concise description of the output item- sets. We also provide constructive algorithms that achieve the upper bounds, and consider more efficient variants for practical situations.

Type de document :
Communication dans un congrès
ICDT (International Conference on Database Theory), Mar 2014, Athens, Greece. pp.15-25, 2014
Liste complète des métadonnées

https://hal-imt.archives-ouvertes.fr/hal-00986184
Contributeur : Admin Télécom Paristech <>
Soumis le : jeudi 1 mai 2014 - 16:54:18
Dernière modification le : jeudi 11 janvier 2018 - 06:23:39

Identifiants

  • HAL Id : hal-00986184, version 1

Citation

Antoine Amarilli, Yael Amsterdamer, Tova Milo. On the Complexity of Mining Itemsets from the Crowd Using Taxonomies. ICDT (International Conference on Database Theory), Mar 2014, Athens, Greece. pp.15-25, 2014. 〈hal-00986184〉

Partager

Métriques

Consultations de la notice

64