DCI-Closed vs LCM?

This is for discussing anything related to pattern mining (e.g. itemsets, sequential patterns, subgraph mining)
Post Reply
User avatar
admin
Site Admin
Posts: 121
Joined: Tue Apr 05, 2022 12:47 am
Location: China
Contact:

DCI-Closed vs LCM?

Post by admin »

I recently received a question in my e-mail about whether LCM or DCI-Closed is faster and if they have been compared in research papers.

Here is my answer:

Good evening,

That is an interesting question. The LCM algorithm was compared with many algorithms in the FIMI competition. It was a competition to program the fastest itemset mining algorithm held in 2003 and 2004. LCM was the winner.

But indeed, DCI-Closed was proposed after LCM and in the DCI_Closed paper, they did not compare with LCM. I did not see any paper that did the comparison (maybe i missed something), so it is unclear to me which one is the best. I think they probably have different advantages.

LCM is probably better for dense databases because it applies a merging operation that is very effective for dense datasets (it combines identical transactions into a single one). DCI_closed might be better in other situations.

In my SPMF software, I have implemented both DCI_Closed and LCM. However, it has to be noted that the LCM that I have implemented is based on LCM version 2 of Prof. Uno (if I correctly remember the name of the author of LCM), and I did not implement the merging operation. Besides, if you check the website of Uno, you will see that he has done many versions of LCM like LCM v1 v2 v3 v4 and v5. The version 5 if I remember is very complicated and combine FP-Tree, vertical database and horizontal database and can switch between these three structures depending on the type of database or something like that... I did not implement this in Java either.

By the way, a better algorithm does not always mean the fastest. It can be also the most memory efficient, the easier to implement or the algorithm that is more easily to extend with constraints for some specific applications.

LCM is very memory efficient. Probably better than DCI. But maybe DCI has other advantages like easier to implement and extend. Just my opinion.

Hope this helps.

Best regards
Alva
Posts: 44
Joined: Sun Apr 10, 2022 12:17 am

Re: DCI-Closed vs LCM?

Post by Alva »

But it is not required to compare with the latest and state-of-the-art to publish papers?
User avatar
admin
Site Admin
Posts: 121
Joined: Tue Apr 05, 2022 12:47 am
Location: China
Contact:

Re: DCI-Closed vs LCM?

Post by admin »

Hi Alva,

It is indeed better to compare with the state-of-the-art algorithms but sometimes authors do not do it and the reviewers still let the paper to be published even if it was not compared with the latest algorithms. Sometimes, it is also because the original implementation was not available for comparison, or other reasons!

Best regards
Post Reply