12-05-2011, 12:06 PM
[attachment=13635]
[attachment=13637]
Hardware enhanced association rule mining with Hashing and Pipelining
Abstract
• Data mining techniques have been widely used in various applications. One of the most important data mining applications is association rule mining.
• Apriori-based association rule mining in hardware, one has to load candidate itemsets and a database into the hardware.
• Since the capacity of the hardware architecture is fixed, if the number of candidate itemsets or the number of items in the database is larger than the hardware capacity, the items are loaded into the hardware separately.
• The time complexity of those steps that need to load candidate itemsets or database items into the hardware is in proportion to the number of candidate itemsets multiplied by the number of items in the database. Too many candidate itemsets and a large database would create a performance bottleneck.
• In this paper, we propose a Hash-based and Pipelined (abbreviated as HAPPI) architecture for hardware enhanced association rule mining. Therefore, we can effectively reduce the frequency of loading the database into the hardware.
• HAPPI solves the bottleneck problem in a priori-based hardware schemes.
Scope of the project
We can effectively reduce the frequency of loading the database into the hardware
Introduction:
DATA mining technology is now used in a wide variety of fields. Applications include the analysis of customer transaction records, web site logs, credit card purchase information, call records, to name a few. The interesting results of data mining can provide useful information such as customer behavior for business managers and researchers. One of the most important data mining applications is association rule mining
We only need to focus on the methods of finding the frequent itemsets in the database. The Apriori approach was the first to address this issue. Apriori finds frequent itemsets by scanning a database to check the frequencies of candidate itemsets, which are generated by merging frequent subitemsets. However, Apriori-based algorithms have undergone bottlenecks because they have too many candidate itemsets.
Apriori-based hardware schemes require loading the candidate itemsets and the database into the hardware. Since the capacity of the hardware is fixed, if the number of items in the database is larger than the hardware capacity, the data items must be loaded separately. Therefore, the process of comparing candidate itemsets with the database needs to be executed several times. Similarly, if the number of candidate itemsets is larger than the capacity of the hardware, the pattern matching procedure has to be separated into many rounds. Clearly, it is infeasible for any hardware design to load the candidate itemsets and the database into hardware for multiple times. Since the time complexity of those steps that need to load candidate itemsets or database items into the hardware is in proportion to the number of candidate itemsets and the number of items in the database, this procedure is very time consuming. In addition, numerous candidate itemsets and a huge database may cause a bottleneck in the system.
1.1 PROJECT DESCRIPTION
Modules:
1.Transaction Table
2. Support Count
3. Frequent Item set
4. Transaction Trimming
5. HAPPI Result
1. Transaction Table
This table is used during restart recovery to track the state of active transactions. It is initialized during the analysis pass from the most recent checkpoints record and is modified during the analysis of the log records written after the beginning of that checkpoint. It is also used during normal processing
2. Support Count
The support counting procedure finds frequent itemsets by comparing candidate itemsets with transactions in the database.
3. Frequent Item set
A frequent itemset is an itemset whose support is greater than some user-specified minimum support
Transaction Trimming
From this information, infrequent items in the transactions can be eliminated since they are not useful in generating frequent itemsets through the trimming filter
5. HAPPI Result
It will compare the existing system and proposed system with graph manner.
Input:
Transaction table is input of our project
2. SYSTEM STUDY
2.1 FEASIBLITY STUDY
The feasibility of the project is analyzed in this phase and business proposal is put forth with a very general plan for the project and some cost estimates. During system analysis the feasibility study of the proposed system is to be carried out. This is to ensure that the proposed system is not a burden to the company. For feasibility analysis, some understanding of the major requirements for the system is essential.
Three key considerations involved in the feasibility analysis are
ECONOMICAL FEASIBILITY
TECHNICAL FEASIBILITY
SOCIAL FEASIBILITY
ECONOMICAL FEASIBILITY:
This study is carried out to check the economic impact that the system will have on the organization. The amount of fund that the company can pour into the research and development of the system is limited. The expenditures must be justified. Thus the developed system as well within the budget and this was achieved because most of the technologies used are freely available. Only the customized products had to be purchased.
TECHNICAL FEASIBILITY:
This study is carried out to check the technical feasibility, that is, the technical requirements of the system. Any system developed must not have a high demand on the available technical resources. This will lead to high demands on the available technical
esources. This will lead to high demands being placed on the client. The developed system must have a modest requirement, as only minimal or null changes are required for implementing this system.
SOCIAL FEASIBILITY:
The aspect of study is to check the level of acceptance of the system by the user. This includes the process of training the user to use the system efficiently. The user must not feel threatened by the system, instead must accept it as a necessity. The level of acceptance by the users solely depends on the methods that are employed to educate the user about the system and to make him familiar with it. His level of confidence must be raised so that he is also able to make some constructive criticism, which is welcomed, as he is the final user of the system.
Existing System:
• Apriori is a classic algorithm for learning association rules. Apriori is designed to operate on database containing transactions. Apriori finds frequent itemsets by scanning a database to check the frequencies of candidate itemsets, which are generated by merging frequent subitemsets. Apriori uses to count candidate item sets efficiently.
• Apriori-based algorithms have undergone bottlenecks because they have too many candidate itemsets. So we can’t reduce the frequency of loading the database into the hardware.
Proposed System:
• We propose a HAsh-based and PiPelIned (abbreviated as HAPPI) architecture for hardware-enhanced association rule mining.
• There are three hardware modules in our system.
1. First, when the database is fed into the hardware, the candidate itemsets are compared with the items in the database by the systolic array.
2. Second, we collect trimming information. From this information, infrequent items in the transactions can be eliminated since they are not useful in generating frequent itemsets through the trimming filter.
3. Third, we generate itemsets from transactions and hash them into the hash table, which is then used to filter out unnecessary candidate itemsets.
• Our Proposed System solves the bottleneck problem in a priori-based hardware schemes.
3. SYSTEM CONFIGURATION
3.1 HARDWARE CONFIGURATION
The hardware used for the development of the project is:
PROCESSOR : PENTIUM III 766 MHz
RAM : 128 MD SD RAM
MONITOR : 15” COLOR
HARD DISK : 20 GB
FLOPPY DRIVE : 1.44 MB
CDDRIVE : LG 52X
KEYBOARD : STANDARD 102 KEYS
MOUSE : 3 BUTTONS
3.2 SOFTWARE CONFIGURATION
The software used for the development of the project is:
OPERATING SYSTEM : Windows 2000 Professional
ENVIRONMENT : Visual Studio .NET 2005
.NET FRAMEWORK : Version 2.0
LANGUAGE : VB.NET
WEB TECHNOLOGY : Active Server Pages.NET
WEB SERVER : Internet Information Server 5.0
BACK END : SQL SERVER 2000
REPORTS : Web Form Data Grid control
4. LANGUAGE SPECIFICATION
4.1 FEATURES OF VISUAL BASIC .NET
Overview of the .NET Framework:
The .NET Framework is a new computing platform that simplifies application development in the highly distributed environment of the Internet. The .NET Framework is designed to fulfill the following objectives:
• To provide a consistent object-oriented programming environment whether object code is stored and executed locally, executed locally but Internet-distributed, or executed remotely.
• To provide a code-execution environment that minimizes software deployment and versioning conflicts.
• To provide a code-execution environment that guarantees safe execution of code, including code created by an unknown or semi-trusted third party.
• To provide a code-execution environment that eliminates the performance problems of scripted or interpreted environments.
• To make the developer experience consistent across widely varying types of applications, such as Windows-based applications and Web-based applications.
• To build all communication on industry standards to ensure that code based on the .NET Framework can integrate with any other code.
The .NET Framework has two main components: the common language runtime and the .NET Framework class library. The common language runtime is the foundation of the .NET Framework. You can think of the runtime as an agent that manages code at execution time, providing core services such as memory management, thread management, and remoting, while also enforcing strict type safety and other forms of code accuracy that ensure security and robustness. In fact, the concept of code management is a fundamental principle of the runtime. Code that targets the runtime is known as managed code, while code that does not target the runtime is known as unmanaged code. The class library, the other main component of the .NET Framework, is a comprehensive, object-oriented collection of reusable types that you can use to develop applications ranging from traditional command-line or graphical user interface (GUI) applications to applications based on the latest innovations provided by ASP.NET, such as Web Forms and XML Web services.
The .NET Framework can be hosted by unmanaged components that load the common language runtime into their processes and initiate the execution of managed code, thereby creating a software environment that can exploit both managed and unmanaged features. The .NET Framework not only provides several runtime hosts, but also supports the development of third-party runtime hosts.
For example, ASP.NET hosts the runtime to provide a scalable, server-side environment for managed code. ASP.NET works directly with the runtime to enable Web Forms applications and XML Web services, both of which are discussed later in this topic.
The following illustration shows the relationship of the common language runtime and the class library to your applications and to the overall system. The illustration also shows how managed code operates within a larger architecture.
The following sections describe the main components and features of the .NET Framework in greater detail.
Features of the Common Language Runtime:
The common language runtime manages memory, thread execution, code execution, code safety verification, compilation, and other system services. These features are intrinsic to the managed code that runs on the common language runtime.
With regards to security, managed components are awarded varying degrees of trust, depending on a number of factors that include their origin (such as the Internet, enterprise network, or local computer). This means that a managed component might or might not be able to perform file-access operations, registry-access operations, or other sensitive functions, even if it is being used in the same active application.
The runtime enforces code access security. For example, users can trust that an executable embedded in a Web page can play an animation on screen or sing a song, but cannot access their personal data, file system, or network. The security features of the runtime thus enable legitimate Internet-deployed software to be exceptionally feature rich.
The runtime also enforces code robustness by implementing a strict type- and code-verification infrastructure called the common type system (CTS). The CTS ensures that all managed code is self-describing. The various Microsoft and third-party language compilers generate managed code that conforms to the CTS. This means that managed code can consume other managed types and instances, while strictly enforcing type fidelity and type safety.
In addition, the managed environment of the runtime eliminates many common software issues. For example, the runtime automatically handles object layout and manages references to objects, releasing them when they are no longer being used. This automatic memory management resolves the two most common application errors, memory leaks and invalid memory references.
The runtime also accelerates developer productivity. For example, programmers can write applications in their development language of choice, yet take full advantage of the runtime, the class library, and components written in other languages by other developers. Any compiler vendor who chooses to target the runtime can do so. Language compilers that target the .NET Framework make the features of the .NET Framework available to existing code written in that language, greatly easing the migration process for existing applications.
While the runtime is designed for the software of the future, it also supports software of today and yesterday. Interoperability between managed and unmanaged code enables developers to continue to use necessary COM components and DLLs.
The runtime is designed to enhance performance. Although the common language runtime provides many standard runtime services, managed code is never interpreted. A feature called just-in-time (JIT) compiling enables all managed code to run in the native machine language of the system on which it is executing. Meanwhile, the memory manager removes the possibilities of fragmented memory and increases memory locality-of-reference to further increase performance.
Finally, the runtime can be hosted by high-performance, server-side applications, such as Microsoft® SQL Server™ and Internet Information Services (IIS). This infrastructure enables you to use managed code to write your business logic, while still enjoying the superior performance of the industry's best enterprise servers that support runtime hosting.
.NET Framework Class Library:
The .NET Framework class library is a collection of reusable types that tightly integrate with the common language runtime. The class library is object oriented, providing types from which your own managed code can derive functionality. This not only makes the .NET Framework types easy to use, but also reduces the time associated with learning new features of the .NET Framework. In addition, third-party components can integrate seamlessly with classes in the .NET Framework.
For example, the .NET Framework collection classes implement a set of interfaces that you can use to develop your own collection classes. Your collection classes will blend seamlessly with the classes in the .NET Framework.
As you would expect from an object-oriented class library, the .NET Framework types enable you to accomplish a range of common programming tasks, including tasks such as string management, data collection, database connectivity, and file access. In addition to these common tasks, the class library includes types that support a variety of specialized development scenarios. For example, you can use the .NET Framework to develop the following types of applications and services:
• Console applications.
• Scripted or hosted applications.
• Windows GUI applications (Windows Forms).
• ASP.NET applications.
• XML Web services.
• Windows services.
For example, the Windows Forms classes are a comprehensive set of reusable types that vastly simplify Windows GUI development. If you write an ASP.NET Web Form application, you can use the Web Forms classes.
Client Application Development:
Client applications are the closest to a traditional style of application in Windows-based programming. These are the types of applications that display windows or forms on the desktop, enabling a user to perform a task. Client applications include applications such as word processors and spreadsheets, as well as custom business applications such as data-entry tools, reporting tools, and so on. Client applications usually employ windows, menus, buttons, and other GUI elements, and they likely access local resources such as the file system and peripherals such as printers.
Another kind of client application is the traditional ActiveX control (now replaced by the managed Windows Forms control) deployed over the Internet as a Web page. This application is much like other client applications: it is executed natively, has access to local resources, and includes graphical elements.
Server Application Development:
Server-side applications in the managed world are implemented through runtime hosts. Unmanaged applications host the common language runtime, which allows your custom managed code to control the behavior of the server. This model provides you with all the features of the common language runtime and class library while gaining the performance and scalability of the host server.
The following illustration shows a basic network schema with managed code running in different server environments. Servers such as IIS and SQL Server can perform standard operations while your application logic executes through the managed code.
Server-side managed code
ASP.NET is the hosting environment that enables developers to use the .NET Framework to target Web-based applications. However, ASP.NET is more than just a runtime host; it is a complete architecture for developing Web sites and Internet-distributed objects using managed code. Both Web Forms and XML Web services use IIS and ASP.NET as the publishing mechanism for applications, and both have a collection of supporting classes in the .NET Framework.
XML Web services, an important evolution in Web-based technology, are distributed, server-side application components similar to common Web sites. However, unlike Web-based applications, XML Web services components have no UI and are not targeted for browsers such as Internet Explorer and Netscape Navigator. Instead, XML Web services consist of reusable software components designed to be consumed by other applications, such as traditional client applications, Web-based applications, or even other XML Web services. As a result, XML Web services technology is rapidly moving application development and deployment into the highly distributed environment of the Internet.
The .NET Framework also provides a collection of classes and tools to aid in development and consumption of XML Web services applications. XML Web services are built on standards such as SOAP (a remote procedure-call protocol), XML (an extensible data format), and WSDL (the Web Services Description Language). The .NET Framework is built on these standards to promote interoperability with non-Microsoft solutions.
Active Server Pages.NET
ASP.NET is a programming framework built on the common language runtime that can be used on a server to build powerful Web applications. ASP.NET offers several important advantages over previous Web development models:
• Enhanced Performance. ASP.NET is compiled common language runtime code running on the server. Unlike its interpreted predecessors, ASP.NET can take advantage of early binding, just-in-time compilation, native optimization, and caching services right out of the box. This amounts to dramatically better performance before you ever write a line of code.
• World-Class Tool Support. The ASP.NET framework is complemented by a rich toolbox and designer in the Visual Studio integrated development environment. WYSIWYG editing, drag-and-drop server controls, and automatic deployment are just a few of the features this powerful tool provides.
• Power and Flexibility. Because ASP.NET is based on the common language runtime, the power and flexibility of that entire platform is available to Web application developers. The .NET Framework class library, Messaging, and Data Access solutions are all seamlessly accessible from the Web. ASP.NET is also language-independent, so you can choose the language that best applies to your application or partition your application across many languages. Further, common language runtime interoperability guarantees that your existing investment in COM-based development is preserved when migrating to ASP.NET.
• Simplicity. ASP.NET makes it easy to perform common tasks, from simple form submission and client authentication to deployment and site configuration. For example, the ASP.NET page framework allows you to build user interfaces that cleanly separate application logic from presentation code and to handle events in a simple, Visual Basic - like forms processing model. Additionally, the common language runtime simplifies development, with managed code services such as automatic reference counting and garbage collection.
• Manageability. ASP.NET employs a text-based, hierarchical configuration system, which simplifies applying settings to your server environment and Web applications. Because configuration information is stored as plain text, new settings may be applied without the aid of local administration tools. This "zero local administration" philosophy extends to deploying ASP.NET Framework applications as well. An ASP.NET Framework application is deployed to a server simply by copying the necessary files to the server. No server restart is required, even to deploy or replace running compiled code.
• Scalability and Availability. ASP.NET has been designed with scalability in mind, with features specifically tailored to improve performance in clustered and multiprocessor environments. Further, processes are closely monitored and managed by the ASP.NET runtime, so that if one misbehaves (leaks, deadlocks), a new process can be created in its place, which helps keep your application constantly available to handle requests.
• Customizability and Extensibility. ASP.NET delivers a well-factored architecture that allows developers to "plug-in" their code at the appropriate level. In fact, it is possible to extend or replace any subcomponent of the ASP.NET runtime with your own custom-written component. Implementing custom authentication or state services has never been easier.
• Security. With built in Windows authentication and per-application configuration, you can be assured that your applications are secure.
Language Support
The Microsoft .NET Platform currently offers built-in support for three languages: C#, Visual Basic, and JScript.
