ABSTRACT

Using computer, people can collect data in many types. Thus, many applications

to revealing valuable information have been considered. One of the most

important matters is “to shorten run time” when database become bigger and

bigger. Furthermore, we look for algorithms only using minimum required

resources but are doing well when database become very large.

My thesis, with the subject “hash-based approach to data mining” focuses on the

hash-based method to improve performance of finding association rules in the

transaction databases and use the PHS (perfect hashing and data shrinking)

algorithm to build a system, which helps directors of shops/stores to have a

detailed view about his business. The soft gains an acceptable result when runs

over a quite large database.

TABLE OF CONTENTS

Abstract i

List of tables ii

List of figures iii

List of abbreviate words iv

FOREWORD 1

CHAPTER 1: Introduction 3

1.1 Overview of finding association rules . 3

1.1.1 Problem description . . 4

1.1.2 Problem solution . 5

1.2 Some algorithms in the early state . 5

1.2.1 AIS algorithm . 6

1.2.2 SETM algorithm . 6

1.2.3 Apriori algorithm . . 6

1.3 Shortcoming problems . 10

CHAPTER 2: Algorithms using hash-based approach to find association

rules 11

2.1 DHP algorithm (direct hashing and pruning) 12

2.1.1 Algorithm description . 13

2.1.2 Pseudo-code 14

2.1.3 Example 16

2.2 PHP algorithm (perfect hashing and pruning) . 18

2.2.1 Brief description of algorithm 19

2.2.2 Pseudo-code 20

2.2.3 Example 21

2.3 PHS algorithm (Perfect hashing and database shrinking) . 22

vi

2.3.1 Algorithm description . 23

2.3.2 Pseudo-code 25

2.3.3 Example 25

2.4 Summarize of chapter 28

CHAPTER 3: Experiments . . 31

3.1 Choosing algorithm . 31

3.2 Implement . 32

CONCLUSION . 35

REFERENCES 3