Efficiently Mining Maximal Diverse Frequent Itemsets

Dingming Wu, Dexin Luo, Christian S. Jensen, Joshua Zhexu Huang

Research output: Contribution to book/anthology/report/conference proceedingArticle in proceedingResearchpeer-review

Abstract

Given a database of transactions, where each transaction is a set of items, maximal frequent itemset mining aims to find all itemsets that are frequent, meaning that they consist of items that co-occur in transactions more often than a given threshold, and that are maximal, meaning that they are not contained in other frequent itemsets. Such itemsets are the most interesting ones in a meaningful sense. We study the problem of efficiently finding such itemsets with the added constraint that only the top-k most diverse ones should be returned. An itemset is diverse if its items belong to many different categories according to a given hierarchy of item categories. We propose a solution that relies on a purposefully designed index structure called the FP*-tree and an accompanying bound-based algorithm. An extensive experimental study offers insight into the performance of the solution, indicating that it is capable of outperforming an existing method by orders of magnitude and of scaling to large databases of transactions.
Original languageEnglish
Title of host publicationDatabase Systems for Advanced Applications - 24th International Conference, DASFAA 2019, Proceedings : DASFAA 2019: Database Systems for Advanced Applications
EditorsYongxin Tong, Juggapong Natwichai, Jun Yang, Guoliang Li, Joao Gama
Number of pages17
PublisherSpringer
Publication date2019
Pages191-207
ISBN (Print)978-3-030-18578-7
ISBN (Electronic)978-3-030-18579-4
DOIs
Publication statusPublished - 2019
EventInternational Conference on Database Systems for Advanced Applications - Chiang Mai, Thailand
Duration: 22 Apr 201925 Apr 2019

Conference

ConferenceInternational Conference on Database Systems for Advanced Applications
CountryThailand
CityChiang Mai
Period22/04/201925/04/2019
SeriesLecture Notes in Computer Science
Volume11447
ISSN0302-9743

Keywords

  • Algorithm
  • Diversification
  • Frequent itemsets

Cite this

Wu, D., Luo, D., Jensen, C. S., & Huang, J. Z. (2019). Efficiently Mining Maximal Diverse Frequent Itemsets. In Y. Tong, J. Natwichai, J. Yang, G. Li, & J. Gama (Eds.), Database Systems for Advanced Applications - 24th International Conference, DASFAA 2019, Proceedings: DASFAA 2019: Database Systems for Advanced Applications (pp. 191-207). Springer. Lecture Notes in Computer Science, Vol.. 11447 https://doi.org/10.1007/978-3-030-18579-4_12