Fast Algorithms for Mining Association Rules - Review

Authors - Rakesh Agrawal, Ramakrishnan Srikant
Summary - The paper presents two association rules mining algorithm for large datasets. Association rule mining is an interesting area of data mining which discovers the relations among the items in transactions. The new algorithms execute at least three times faster than existing algorithms. The first algorithm is called Apriori which incrementally build the large itemsets (an itemset is a set of items, the support of an itemset is calculated by the count the set appear in the database and a large itemset has support greater than minimum support) until no new bigger large itemset can be added, but this algorithm requires many passes over the database to discover all large itemsets. To tackle this problem this paper also presents another algorithm called AprioriTid, which does not require many passes over the database. AprioriTid stores the list of transactions that requires passing again to compute bigger large itemsets in the subsequent steps. However, the list of transactions that requires passing again may grow larger than the original size of the database which deteriorates the performance instead of improving it. This problem is severe for greater number of large itemsets but drastically disappear for smaller number of large itemset. Hence this paper proposes the use of a hybrid algorithm composed of Apriori and AprioriTid called AprioriHybrid. AprioriHybrid uses Apriori at the beginning when the number of large itemsets is high and switched to AprioriTid when the number of large itemsets became small. An empirical study confirms their claim at the end of the paper.
Further thoughts - (1) In order to obtain meaningful rules how does a user choose minimum support and minimum confidence? (2) Attribute data are fundamentally different from transactional data, how does the association rule mining work for attribute data?

DBOD-DS: Distance Based Outlier Detection for Data Streams

Data stream is a newly emerging data model for applications like environment monitoring, Web click stream, network traffic monitoring, etc. It consists of an infinite sequence of data points accompanied with timestamp coming from external data source. Typically data sources are located onsite and very vulnerable to external attacks and natural calamities, thus outliers are very common in the datasets. Existing techniques for outlier detection are inadequate for data streams because of its metamorphic data distribution and uncertainty. In this paper we propose an outlier detection technique, called Distance-Based Outline Detection for Data Streams (DBOD-DS) based on a novel continuously adaptive probability density function that addresses all the new issues of data streams. Extensive experiments on a real dataset for meteorology applications show the supremacy of DBOD-DS over existing techniques in terms of accuracy.

In DEXA' 2010.

Using Data Mining to Handle Missing Data in Multi-Hop Sensor Network Applications

A sensor’s data loss or corruption, aka sensor data missing, is a common phenomenon in modern wireless sensor networks. It is more severe for multi-hop sensor network (MSN) applications where sensor data reach the base station via other sensors; hence a sensor’s failure can cause multiple missing data. In this paper we present MASTER-M, a data estimation framework based on data clustering and association rule mining to estimate the values of missing sensor data for MSN. Estimating, instead of resending, the missing sensor data is becoming popular as it may reduce query response time and sensor energy consumption; however the current works cater to only single-hop sensor networks. To fill this gap, our novel technique addresses the issues related to MSN, such as simultaneous missing sensors and missing spatially correlated sensors. It consists of three steps: 1) clustering sensors online; 2) capturing association rules between sensors inside each cluster, and 3) estimating the values of the missing data using the obtained association rules. Experimental results on both real-life sensor data and synthetic sensor data demonstrate the efficacy of MASTER-M in terms of estimation accuracy compared to the existing techniques. Moreover, we also present experiments showing the supremacy of data estimation by MASTER-M in terms of energy savings over re-transmission of missing data.

In MobiDE' 2010.

Security for Data Stream Management System

There emerge new applications, such as environment monitoring, Web click streams, and network traffic monitoring, where data are in a form of streams that continuously arrive, usually in high speed and with changing data distribution. Due to the unbounded data volume and the real-time continuous high rate data collection and processing characteristics of those applications, traditional database management systems are not suitable to manage them. To fill in the gap, researchers have proposed a new type of systems, called Data Stream Management Systems (DSMS). Like traditional database management systems, DSMS need to provide security mechanisms to protect streams of data along with the system against malicious attacks in sensitive applications. The special characteristics of data stream applications raise new issues that must be considered when developing security mechanisms for DSMS. This paper discusses those issues, reviews how they have been addressed in the literature, and identifies future research directions.

In Security in computing and networking systems: the state-of-the-art, Eds. William McQuay and Walled W. Smari.

Accelerated Search for Gaussian Generator Based on Triple Prime Integers

Problem statement: Modern cryptographic algorithms are based on complexity of two problems: Integer factorization of real integers and a Discrete Logarithm Problem (DLP). Approach: The latter problem is even more complicated in the domain of complex integers, where Public Key Cryptosystems (PKC) had an advantage over analogous encryption-decryption protocols in arithmetic of real integers modulo p: The former PKC have quadratic cycles of order O (p2) while the latter PKC had linear cycles of order O(p). Results: An accelerated non-deterministic search algorithm for a primitive root (generator) in a domain of complex integers modulo triple prime p was provided in this study. It showed the properties of triple primes, the frequencies of their occurrence on a specified interval and analyzed the efficiency of the proposed algorithm. Conclusion: Numerous computer experiments and their analysis indicated that three trials were sufficient on average to find a Gaussian generator.

Appeared In Journal of Computer Science, 2009.

Research papers!

Only thing I learn in my US life is how to find research papers and how to read them. It is really difficult to say how many papers I have read so far. Dr. Gruenwald has a style of reading papers. After reading a paper she expects you will be able to find the downfall of the strategy. Actually, not only Dr. Gruenwald, all the professors expect same way. Dr. Hougen is one step ahead of it. He expects you will be able to criticize the paper both positively and negatively. On an average, I read two papers per day. Then, I have to report Dr. Gruenwald about those papers. Guess! What worse thing could happen in life?

Actually, we didn’t read much research paper in our style of education in Bangladesh but they do here from the very beginning. So, we have to learn it when we get here. This is an important thing we should add in our academia. I think it is very important part of scientific study. If you can’t criticize other’s work you will not be able to produce your own. Reading a research paper is a good fun once you get on it. One of my tips for reading research paper is: forget about the authors when you are reading; even the giants write craps.

3-Tier Architecture of Data Server on Grid: Implemented using Globus Toolkit

Grid System is one of the newest versions of distributed System. In a distributed System, we often hope to distribute the overheads of the entire system to different PCs. Parallel execution is one of the major features of Grid System as well as we can share RAM or any other resources. But it is quite challenging to design a data server on Grid. To get the full performance of a Grid System the traditional Database Management System (DBMS) fails and so here we propose a modified version of Data Server architecture using existing Database System. Also this implementation base paper includes some comparisons, figures and tables indicating the performance of the Data Server on Grid with the traditional DBMS. We have used Globus Toolkit in our implementation and all the terms in this paper are similar to the terms used on Globus Toolkit.

"published at GCA'07- The 2007 International Conference on Grid Computing and Applications"

ALCHEMI VS GLOBUS: A PERFORMANCE COMPARISON

Alchemi and the Globus Toolkit are open source software toolkits for implementing a Grid. Although both toolkits are designed for the same purpose, their architecture and underlying technology are completely different. Thus, a performance comparison of a Grid implementation in Alchemi with a similar Grid implementation in the Globus Toolkit will be interesting. We built a test bed to compare the performance of the two toolkits. This paper includes tables and graphs to illustrate the comparison.
published at 4^th International Conference on Electrical and Computer Engineering, BUET, Dhaka, Bangladesh, Dec, 2006.

Implementation of Server on Grid System: A Super Computer Approach

The Internet technology has already changed the Information Society in profound ways, and will continue to do so. Nowadays many people foresee that there is a similar trajectory for the next generation of Internet - Grid Technology. As an emerging computational and networking infrastructure, Grid Computing is designed to provide pervasive, uniform and reliable access to data, computational and human resources distributed in a dynamic, heterogeneous environment. Also the development of Grid Security provides a secured field for work. That’s why; we have used the Grid Technology for implementing a server that response to many Clients for any database queries or any other database applications. Our design provides single level distribution of Grid Applications that make the faster response time and faster throughput than the normal server application and even that of distributed application. Here we have used the open source software “Alchemi” in all through our work. This document summarizes the design and implementation of a server using Grid Technology and compares its performance.

published at 15th International Conference of Information System and Development, Budapest, Hungary, Aug, 2006.