1384536
Mining association rules with adjustable accuracy
In this paper, we devise efficient algorithms for mining association rules with adjustable accuracy. It is noted that several applications require mining the transaction data to capture the customer behavior frequently. In those applications, the efficiency of data mining could be a more important faktor t.han the requirement for complete accuracy of the mining results. Allowing imprecise results can significantly improve the data mining efficiency. In this paper, two methods for mining association rules with adjustable accuracy are developed. By dealing with the concept of sampling, both methods obtain some essential knowledge from a sampled subset first, and in light of that knowledge, perform efficient association rule mining on the entire database. A technique of relaxing the support factor based on the sampling size is devised to achieve the desired level of accuracy. These two methods differ from each other in their ways of utilizing the sampled data. Performance of these two methods is comparatively analyzed. As shown by our experimental results, the relaxation factor, as well as the sample size, can be properly adjusted so as to improve the result accuracy while minimizing the corresponding execution time, thereby allowing us to effectively achieve a design trade-off between accuracy and efficiency with two control parameters. It is shown that with the advantage of controlled sampling, the proposed methods are very flexible and efficient, and can in general lead to results of a very high degree of accuracy.
16144421
Fast algorithms for projected clustering
The clustering problem is well known in the database literature for its numerous applications in problems such as customer segmentation, classification and trend analysis. Unfortunately, all known algorithms tend to break down in high dimensional spaces because of the inherent sparsity of the points. In such high dimensional spaces not all dimensions may be relevant to a given cluster. One way of handling this is to pick the closely correlated dimensions and find clusters in the corresponding subspace. Traditional feature selection algorithms attempt to achieve this. The weakness of this approach is that in typical high dimensional data mining applications different sets of points may cluster better for different subsets of dimensions. The number of dimensions in each such cluster-specific subspace may also vary. Hence, it may be impossible to find a single small subset of dimensions for all the clusters. We therefore discuss a generalization of the clustering problem, referred to as the projected clustering problem, in which the subsets of dimensions selected are specific to the clusters themselves. We develop an algorithmic framework for solving the projected clustering problem, and test its performance on synthetic data.
28122333
Using a Hash-Based Method with Transaction Trimming for Mining Association Rules
We examine the issue of mining association rules among items in a large database of sales transactions. Mining association rules means that, given a database of sales transactions, to discover all associations among items such that the presence of some items in a transaction will imply the presence of other items in the same transaction. The mining of association rules can be mapped into the problem of discovering large itemsets where a large itemset is a group of items that appear in a sufficient number of transactions. The problem of discovering large itemsets can be solved by constructing a candidate set of itemsets first, and then, identifying, within this candidate set, these itemsets that meet the large itemset requirement. Generally, this is done iteratively for each large k-itemset in increasing order of k, where a large k-itemset is a large itemset with k items. To determine large itemsets from a huge number of candidate sets in early iterations is usually the dominating factor for the overall data mining performance. To address this issue, we develop an effective algorithm for the candidate set generation. It is a hash-based algorithm and is especially effective for the generation of a candidate set for large 2-itemsets. Explicitly, the number of candidate 2-itemsets generated by the proposed algorithm is, in orders of magnitude, smaller than that by previous methods, thus resolving the performance bottleneck. Note that the generation of smaller candidate sets enables us to effectively trim the transaction database size at a much earlier stage of the iterations, thereby reducing the computational cost for later iterations significantly. The advantage of the proposed algorithm also provides us the opportunity of reducing the amount of disk I/O required. An extensive simulation study is conducted to evaluate performance of the proposed algorithm.
3768369
Efficient Data Mining for Path Traversal Patterns
The authors explore a new data mining capability that involves mining path traversal patterns in a distributed information-providing environment where documents or objects are linked together to facilitate interactive access. The solution procedure consists of two steps. First, they derive an algorithm to convert the original sequence of log data into a set of maximal forward references. By doing so, one can filter out the effect of some backward references, which are mainly made for ease of traveling and concentrate on mining meaningful user access sequences. Second, they derive algorithms to determine the frequent traversal patterns-i.e., large reference sequences-from the maximal forward references obtained. Two algorithms are devised for determining large reference sequences; one is based on some hashing and pruning techniques, and the other is further improved with the option of determining large reference sequences in batch so as to reduce the number of database scans required. Performance of these two methods is comparatively analyzed. It is shown that the option of selective scan is very advantageous and can lead to prominent performance improvement. Sensitivity analysis on various parameters is conducted.
16088118
An effective hash-based algorithm for mining association rules
In this paper, we examine the issue of mining association rules among items in a large database of sales transactions. The mining of association rules can be mapped into the problem of discovering large itemsets where a large itemset is a group of items which appear in a sufficient number of transactions. The problem of discovering large itemsets can be solved by constructing a candidate set of itemsets first and then, identifying, within this candidate set, those itemsets that meet the large itemset requirement. Generally this is done iteratively for each large k-itemset in increasing order of k where a large k-itemset is a large itemset with k items. To determine large itemsets from a huge number of candidate large itemsets in early iterations is usually the dominating factor for the overall data mining performance. To address this issue, we propose an effective hash-based algorithm for the candidate set generation. Explicitly, the number of candidate 2-itemsets generated by the proposed algorithm is, in orders of magnitude, smaller than that by previous methods, thus resolving the performance bottleneck. Note that the generation of smaller candidate sets enables us to effectively trim the transaction database size at a much earlier stage of the iterations, thereby reducing the computational cost for later iterations significantly. Extensive simulation study is conducted to evaluate performance of the proposed algorithm.
9022148
Parallel Searching in Generalized Monge Arrays
Abstract. This paper investigates the parallel time and processor complexities of several searching problems involving Monge, staircase-Monge, and Monge-composite arrays. We present array-searching algorithms for concurrent-read-exclusive-write (CREW) PRAMs, hypercubes, and several hypercubic networks. All these algorithms run in near-optimal time, and their processor-time products are all within an 
 $O (\lg n)$ factor of the worst-case sequential bounds. Several applications of these algorithms are also given. Two applications improve previous results substantially, and the others provide novel parallel algorithms for problems not previously considered.
6379048
Secure Cookies on the Web
Web servers and browsers typically use cookies to capture information for subsequent communications, which provides continuity and state across HTTP connections. At present, Internet e-commerce is somewhat limited in using cookies because sensitive information cannot be securely stored and communicated in typical cookies. Secure cookies offer a potential solution to this problem.
14990532
Weaving Aspects into Real-Time Operating System Design Using Object-Oriented Model Transformation
Despite of the proliferation of object-oriented and component technology, their application to real-time operating systems (RTOS) has been limited since most design concerns in RTOSes crosscut software components and these are critical to deliver required performance and functionality. Aspect-Oriented Programming (AOP) is a very effective means to solve the crosscutting problem. However, we have observed the following limitations of the current AOP framework: (1) the current text-based AOP languages cannot clearly show how aspects are weaved together, (2) their granularity is too coarse to capture all aspects in an RTOS, (3) it is difficult to control the weaving process, since aspect weavers are usually hard-coded. In this paper, we propose a new AOP framework that provides (1) a graphical aspect programming environment that visualizes aspects, crosscutting classes, and method structures, (2) a new aspect model that supports a sub-method level granularity where an aspect is defined as a set of classes, and (3) an aspect weaving process specified by an object-oriented meta-model transformation. Since our aspect-oriented programming framework improves the expressiveness of the crosscutting concerns of RTOSes and automates aspect weaver generation, it can enhance RTOS customization.
3099576
High performance and low power FIR filter design based on sharing multiplication
We present a high performance and low power FIR filter design, which is based on computation sharing multiplier (CSHM). CSHM specifically targets computation re-use in vector-scalar products and is effectively used in our FIR filter design. Efficient circuit level techniques: a new carry select adder and conditional capture flip-flop (CCFF), are also used to further improve power and performance. The proposed FIR filter architecture was implemented in 0.25 μm technology. Experimental results on a 10 tap low pass CSHM FIR filter show speed and power improvement of 19% and 17%, respectively, with respect to an FIR filter based on Wallace tree multiplier.
18041119
Component integrity check and recovery against malicious codes
With the rise in usage of software components in distributed computing applications, the importance of safeguarding these components has assumed great significance. In trying to ensure the survivability of these components, we enable a mission-critical application to detect malicious codes in a component downloaded from a remote location and recover the original functionality of the compromised component. In our work, we use digital signatures to ensure the integrity of software components in a large distributed system. By detecting unauthorized add-ons to the original components we can ensure that only legitimate software components are allowed to execute in a protected software environment. We also explore techniques to recover the original functionality of the component under attack by removing the affected portion from the component. In this paper we introduce the system architecture and the support mechanisms for our proposed approaches