EFIM: A highly efficient algorithm for high-utility itemset mining

Souleymane Zida, Philippe Fournier-Viger*, Jerry Chun Wei Lin, Cheng Wei Wu, Vincent Shin-Mu Tseng

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

79 Scopus citations

Abstract

High-utility itemset mining (HUIM) is an important data mining task with wide applications. In this paper, we propose a novel algorithm named EFIM (EFficient high-utility Itemset Mining), which introduces several new ideas to more efficiently discovers high-utility itemsets both in terms of execution time and memory. EFIM relies on two upper-bounds named sub-tree utility and local utility to more effectively prune the search space. It also introduces a novel array-based utility counting technique named Fast Utility Counting to calculate these upper-bounds in linear time and space. Moreover, to reduce the cost of database scans, EFIM proposes efficient database projection and transaction merging techniques. An extensive experimental study on various datasets shows that EFIM is in general two to three orders of magnitude faster and consumes up to eight times less memory than the state-of-art algorithms d2HUP, HUI-Miner, HUP-Miner, FHM and UP-Growth+.

Original languageEnglish
Title of host publicationAdvances in Artificial Intelligence and Soft Computing - 14th Mexican International Conference on Artificial Intelligence, MICAI 2015, Proceedings
EditorsGrigori Sidorov, SofÍa N. Galicia-Haro
PublisherSpringer Verlag
Pages530-546
Number of pages17
ISBN (Print)9783319270593
DOIs
StatePublished - 1 Jan 2015
Event14th Mexican International Conference on Artificial Intelligence, MICAI 2015 - Cuernavaca, Morelos, Mexico
Duration: 25 Oct 201531 Oct 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9413
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference14th Mexican International Conference on Artificial Intelligence, MICAI 2015
CountryMexico
CityCuernavaca, Morelos
Period25/10/1531/10/15

Keywords

  • High-utility mining
  • Itemset mining
  • Pattern mining

Fingerprint Dive into the research topics of 'EFIM: A highly efficient algorithm for high-utility itemset mining'. Together they form a unique fingerprint.

Cite this