Efficient Parallel Algorithms for Mining Associations

Abstract

The problem of mining hidden associations present in the largeamounts of data has seen widespread applications in manypractical domains such as customer-oriented planning and marketing,telecommunication network monitoring, and analyzing data from scientificexperiments. The combinatorial complexity of the problem hasfascinated many researchers. Many elegant techniques, such as Apriori,have been developed to solve the problem on single-processor machines.However, most available datasets are becoming enormous in size.Also, their high dimensionality results in possibly large number ofmined associations.This strongly motivates the need for efficient and scalable parallelalgorithms. The design of such algorithms is challenging.In the chapter, we give a evolutionary and comparativereview of many existing representative serial and parallel algorithmsfor discovering two kinds of associations. The first part of the chapteris devoted to the non-sequential associations, which utilize the relationshipsbetween events that happen together. The second part is devoted to themore general and potentially more useful sequential associations,which utilize the temporal or sequential relationships between events.It is shown that many existing algorithms actually belong to a few categorieswhich are decided by the broader design strategies.Overall the focus of the chapter is to serve as a comprehensive accountof the challenges and issues involved in effective parallelformulations of algorithms for discovering associations, andhow various existing algorithms try to handle them.