[IJCISIM] Horizontal Format Data Mining with Extended Bitmaps

We published our data mining algorithm to the International Journal of Computer Information Systems and Industrial Management Applications ISSN 2150-7988. It is available online with the Volume 4 - 2012.

Feel free to download it.

Horizontal Format Data Mining with Extended Bitmaps
Buddhika De Alwis, Supun Malinga, Kathiravelu Pradeeban, Denis Weerasiri, Shehan Perera
pp. 514-521 Full Text PDF

Abstract: Analysing the data warehouses to foresee the patterns of the transactions often needs high computational power and memory space due to the huge set of past history of the data transactions. With the fragmented data along with the current trend of distributed systems, most of the fundamental algorithms that are initially proposed to find the association among the itemsets in the data warehouses are inefficient either in throughput or the utilization of the resources.

Apriori algorithm is a mostly learned and implemented algorithm that mines the data warehouses to find the associations. However, Apriori is generally not an optimized algorithm. More variations, improvements, and alternatives have been suggested to overcome the inefficiency of Apriori algorithm, either as a whole or to specific sets of data. In any case, a fraction of improvement in the algorithm often improves the mining considerably. Frequent item set mining with vertical data format has been proposed as an improvement over the basic Apriori algorithm, which mines the data sets of vertical form, opposed to the typical horizontal format data as in case of Apriori.

In this paper we are proposing an algorithm as an alternative to Apriori algorithm, which will use bitmap indices in conjunction with a horizontal format data set converted to a vertical format data structure to mine frequent itemsets leveraging efficiencies of bitmap based operations and vertical format data orientation.

Keywords: Data mining, Association Rule, Apriori, Vertical format mining, Bitmap Indices, Data Analysis, Data Warehousing.

SoCPaR2010

SoCPaR (International Conference on Soft Computing and Pattern Recognition) is an annual conference that focuses on bringing the Soft Computing and Pattern Recognition together ~ "Innovating and Inspiring Soft Computing and Intelligent Pattern Recognition". For the second consecutive year, SoCPaR has been successfully conducted. SoCPaR 2009 was held in Malacca, Malaysia on December 4th - 7th, 2009, which was followed by SoCPaR2010 in Cergy Pontoise / Paris, France at Universite' de Cergy Pontoise on December 7th - 10th, 2010. Following the two successful years, SoCPaR2011 has been scheduled to be held on Dalian, China on October 14th - 16th, 2011.

Presenting the paper on Association Rule Mining
It was really a pleasant experience for me presenting our paper on our research "Horizontal Format Data Mining with Extended Bitmaps [1]" on SoCPaR2010. Our paper has been listed as Paper 113 in the proceedings. I presented the paper on Dec 8th, 2.30 - 3.00 p.m at E1 auditorium of the University, where the conference had 3 parallel sessions at E1, E2, and Colloque. It should be noted that the paper was from the same team of undergraduates from the University of Moratuwa who published a paper on their product, "Mooshabaya - A Mashup Generator for XBaya [2]". Our paper got positive and constructive feedbacks, which essentially gives us more idea towards taking the algorithm forward. We have our algorithm implementation benchmarked with the FIMI datasets, and also have the door opened to the competition of algorithm implementations on Frequent Itemset Mining Implementations, as suggested by the chair.

Paris (6th - 11th, December 2010)
Apart from the paper presentations and tech talks, we also had social events and extra social activities such as 'Paris by Night', 'Wine Tasting', 'Visit to Chateau de Chantilly', and Banquet at Abbey of Royaumont [3][4], organized by the committee. It was a nice learning experience along with the days filled with fun. It should also be noted that we had the opportunity to face the strongest snowfall that Paris experienced after the year 1986. After the conference, we were also able to enjoy two more days at Paris, and were lucky enough to visit Louvre (the museum where Mona Lisa and many other master pieces live), Notre Dame Cathedral, Montmartre Hill along with a big white church Basilica of Sacre-Coeur on its crust, Eiffel Tower, and a few other places of interest.

[1] Buddhika De Alwis, Supun Malinga, Kathiravelu Pradeeban, Denis Weerasiri, Shehan Perera. "Horizontal Format Data Mining with Extended Bitmaps," in  Proceedings of the 2010 International Conference on Soft Computing and Pattern Recognition (SoCPaR2010), Cergy-Pontoise, Paris, France. pp 220-223, Dec. 2010.

[2] Buddhika De Alwis, Supun Malinga, Kathiravelu Pradeeban, Denis Weerasiri, Srinath Perera, Vishaka Nanayakkara. "Mooshabaya: mashup generator for XBaya," in Proceedings of the 8th International Workshop on Middleware for Grids, Clouds and e-Science (MGC '10), Bangalore, India. ISBN: 978-1-4503-0453-5 doi>10.1145/1890799.1890807 

[3] The abbey
[4] Photos of the Abbey

Horizontal Format Data Mining with Extended Bitmaps

Abstract
Analysing the data warehouses to foresee the patterns of the transactions often needs high computational power and memory space due to the huge set of past history of the data transactions. Apriori algorithm is a mostly learned and implemented algorithm that mines the data warehouses to find the associations. Frequent item set mining with vertical data format has been proposed as an improvement over the basic Apriori algorithm.
In this paper we are proposing an algorithm as an alternative to Apriori algorithm, which will use bitmap indices in conjunction with a horizontal format data set converted to a vertical format data structure to mine frequent itemsets leveraging efficiencies of bitmap based operations and vertical format data orientation.

Categories and Subject Descriptors
[Data Mining] Association Rule, Apriori, Bitmap Indices.
[Data Analysis] Data warehousing, Data Analysis.
General Terms - Data Analysis and Mining
Keywords - Data mining, Association Rule, Apriori, Vertical format mining, Bitmap Indices



Here we are proposing an algorithm "Horizontal Format Data Mining with Extended Bitmaps," for the Association Rule Mining. First we will have a look into the association rule mining and the roots of our algorithm. What is association rule mining? Finding interesting relationships between the variables is defined as Association Rule Mining. Association rule mining is often explained by market basket analysis, where the customers' purchase details are analyzed to find interesting relationships between the items. Here we find the variable sets which appear together. This is defined as Frequent Itemsets, and it is an interest of research due to its expensiveness.

Apriori Algorithm is a fundamental algorithm for the association rule mining. This mines the frequent patterns that are presented in a horizontal format, where the items are listed against their respective transaction. Apriori algorithm abides to the apriori property - any subset of the frequent itemsets is frequent. Each pass should go through the whole data set in Apriori algorithm. Hence it is not an optimized algorithm. Many improvements are suggested to the Apriori Algorithm.

Transaction data mostly occur in horizontal format, where vertical format is an alternative way of looking into it. Here the transactions are listed against the respective items. Since data may not appear in this format, we may need to re-organize the data into the vertical format, before mining them for the associations. Many effective algorithms are built on top of the vertical format data mining.

Now let's look at the next interesting terminology of our algorithm - Bitmaps. Bitmaps are used to store individual bits compactly. It's 0's and 1's where 1's depict the existence. Major advantage of using bitmaps is the possibility of effectively exploiting the bit-level parallelism. We have seen the vertical data formats and the bitmaps. Now we have a question. Is it possible to grab the benefits from both the vertical format representation and the bitmap operations to find frequent itemsets in a distributed environment?

Here we propose the algorithm 'Horizontal Format Data Mining with Extended Bitmaps'. The algorithm takes the data set organized in horizontal format. With one pass of the data set, we construct a bit map based data structure. The bit map structure will be in the vertical format. This structure facilitates an efficient mining.

First we take the transaction id of T100. (T100, {I1, I2, I5}). We will mark the items that appear in T100 in the ordered array. At the same time we link the associated items to the ordered array. Hence I2 will be linked to I1 in the master array, while I5 will be linked to I2. I5 will also be linked to I2 in the ordered array. Linking I1 to I2 or I2 to I5 in the ordered array is avoided to prevent redundancy. I1, I2, and I5 are marked 1 to represent their existence, hence constructing their bitmaps.

Refer to the Slides for a simple explanation on the algorithm "Horizontal Format Data Mining with Extended Bitmaps" itself.

T - Average size of transaction (Transactions).
I - Average size of maximal potentially-large itemsets (Itemsets).
D - Number of Transactions (Datasets).


Image: http://en.wikipedia.org/wiki/File:Storeisle.png

Over the road of flowers..

The last two weeks were really interesting and most remarkable. Our Advanced Database (CS4420) Module research paper "Horizontal Format Data Mining with Extended Bitmaps," got accepted for International Conference of Soft Computing and Pattern Recognition - SoCPaR-2010 (Paris, France. December 7th - 10th, 2010), under the category "Pattern Recognition," as a short paper. We got to know this exciting news on 11th of September. After a few days, on 16th, we were announced that our Mooshabaya paper too has been accepted to the 8th International Workshop on Middleware for Grids, Clouds and e-Science - MGC-2010 (Bangalore, India . November 29th - December 3rd, 2010), as a full paper, to double our joy. It should also be noted that both the projects were from us - the same 4 member team Mooshabaya, who are currently Software Engineers at WSO2.

Our job at WSO2 started with a remarkable week. The new building at #50 was opened the very same day (September) we joined. The next two days we had the WSO2Conf marking the 5 years of excellence of WSO2. The first week ended with the 5 years party at the Waters Edge. Walks between the forts of 50 and 59 over the road of flowers⚘. Loving these days... ♥ ♥ Cloud/Could Duality ;) And I am into WSO2 Stratos! I got into the Stratos (WSO2 Carbon Middleware Platform as a Service) team - Stratos Manager Component and Stratos Security as the first tasks. Finally completing one of the most remarkable fortnights with this post.

Association Rule Mining with Extended Vertical Format Data Mining

We, the team of Mooshabaya (De Alwis.K.D.B.C, Malinga.A.S, Pradeeban.K, Weerasiri.W.A.D.D.) chose "Association Rule Mining with Extended Vertical Format Data Mining" as our Advanced Database CS4420 module research project. The project proposal can be found here. The research paper we submitted is given below.

Abstract

Analyzing the data warehouses to foresee the patterns of the transactions of the businesses and scientific infrastructures often needs high computational power and a high memory space due to the huge set of past history of data transactions. With the fragmented data along with the current trend of distributed systems, most of the fundamental algorithms that are initially proposed to find the association among the itemsets in the data warehouses are inefficient either in throughput or the utilization of the resources.

Apriori algorithm is such an algorithm which was proposed to mine the data warehouses to find the associations. Apriori, though being the mostly learned and implemented algorithm for data mining, it is generally not an optimized algorithm. More variations, improvements, and alternatives have been suggested to overcome the inefficiency of Apriori algorithm, either as a whole or to a particular specific set of data. In either case a fraction of improvement in the algorithm often improves the mining considerably. Vertical Format Data mining is one of the efficient alternatives to Apriori algorithm. In this paper we are proposing an algorithm as an alternative to Apriori algorithm, which will use bitmap indices in conjunction with vertical format data mining. The implementation of the proposed algorithm is benchmarked with an implementation of Apriori Algorithm against a chosen set of benchmarks, which is supposed to be more efficient than its predecessors.

Initial Paper: PDF.


Update as on 18th Dec: We further worked on the algorithm and published a paper ("Horizontal Format Mining with Extended Bitmaps") on this. Slides with explanation on the algorithm can be downloaded here.