9747098
A Selection Algorithm with a Practical Upper Bound on Expected Number
A selection algorithm to find the Irth smallest element of a elements is presented. The algorithm mainly consists of the partition procedure and an improved method to choose a partitioning element. The algorithm estimates the partitioning element from a small sample so that the icth element is contained in the smaller partition between two partitions resulting from partitioning. The partitioning element is determined by using estimation of the cumulative frequency distribution in the theory of non-parametric statistics. The expected number of comparisons is found to be n + min(k, n-k) + O(n2/3) through experimental tests where the sample size is approximately n2/3. The experimental results show that the performance of the algorithm is improved, compared to the two known selection algorithms, particularly when the selection index is near to the median.
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.
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.
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.
31766769
Improved selection in totally monotone arrays
This paper's main result is an -time algorithm for computing the kth smallest entry in each row of an m×n totally monotone array. (A two-dimensional array A={a[i, j]} is totally monotone if for all i1<i2 and j1<j2, a[i1, j1]<a[i1, j2] implies a[i2, j1]<a[i2, j2].) For large values of k (in particular, for k=⌈n/2⌉), this algorithm is significantly faster than the O(k(m + n))-time algorithm for the same problem due to Kravets and Park. An immediate consequence of this result is an O(n3/2lg1/2 n)-time algorithm for computing the kth nearest neighbor of each vertex of a convex n-gon. In addition to the main result, we also give an O(n lg m)-time algorithm for computing an approximate median in each row of an m×n totally monotone array; this approximate median is an entry whose rank in its row lies between ⌊n/4⌋ and ⌈3n/4⌉ − 1.
5711141
Selection and sorting in totally monotone arrays
A two-dimensional arrayA={a[i, j]} is calledtotally monotone if, for alli1<i2 andj1<j2,a[i1,j1]<a[i1,j2] impliesa[i2,j1]<a[i2,j2]. Totally monotone arrays were introduced in 1987 by Aggarwal, Klawe, Moran, Shor, and Wilber, who showed that several problems in computational geometry and VLSI river routing could be reduced to the problem of finding a maximum entry in each row of a totally monotone array. In this paper we consider several selection and sorting problems involving totally monotone arrays and give a number of applications of solutions for these problems. In particular, we obtain the following results for anm × n totally monotone arrayA:1.Thek largest (ork smallest) entries in each row ofA can be computed inO(k(m + n)) time. This result allows us to determine thek farthest (ork nearest) neighbors of each vertex of a convexn-gon inO(kn) time.2.Provided the transpose ofA is also totally monotone, thek largest (ork smallest) entries overall inA can be computed inO(m + n + k lg(mn/k)) time. This result allows us to find thek farthest (ork nearest) pairs of vertices from a convexn-gon inO(n + k lg(n2/k)) time.3.The rows ofA can be sorted inO(mn) time whenm ≥n and inO(mn(1 + lg(n/m))) time whenm < n. This result allows us to solve the of Ω(S) on the number of combinations of row permutations possible for a totally monotone array would imply an Ω(lgS) lower bound on the time necessary to sort the array's rows in a linear decision tree model.)4.In Subsection 4.2 we applied our algorithm for sorting the rows of a totally monotone array to the neighbor-ranking problem for the vertices of a convex polygonP. We then extended this technique to arbitrary point sets. It remains open whether our two selection algorithms for totally monotone arrays, which we also applied to the vertices of a convex polygon, can likewise be applied to arbitrary point sets.
17375890
Binding identities and attributes using digitally signed certificates
A certificate is digitally signed by a certificate authority (CA) to confirm that the information in the certificate is valid and belongs to the subject. Certificate users can verify the integrity and validity of a certificate by checking the issuing CA's digital signature in the certificate and, if necessary, chasing certificate chain and revocation lists. Usually, we use certificates to provide the integrity of identity or attribute information of the subject. Attributes must be coupled with the corresponding identities. We introduce comprehensive approaches to bind identity and attribute certificates, identifying three different techniques: monolithic, autonomic, and chained signatures. We describe each technique and analyze the relative advantages and disadvantages of each.
16813459
Scenario-based multitasking for real-time object-oriented models
Abstract Contemporary embedded systems quite often employ extremely complicated software consisting of a number of interrelated components, and this has made object-oriented design methodologies widely used in practice. To implement an object-oriented model in given target hardware, it is imperative to derive a set of tasks from the designed objects. This process of determining tasks and the events they handle greatly influences the real-time performance of the resultant system including response times and real-time guarantees. However, the innate discrepancies between objects and tasks make this exceedingly difficult, and many developers are forced to find their task sets through trial and error. In this paper, we propose Scenario-based Implementation Synthesis Architecture (SISA), an architecture consisting of a method for deriving a task set from a given object-oriented model and the development tools and run-time system architecture to support the method. A system developed with SISA guarantees the optimal response time for each event while deriving the smallest possible number of tasks. We have fully implemented SISA by extending the RoseRT development tool and applied it to an existing industrial PBX (private branch exchange) system. The experimental results show that SISA outperforms the best known conventional techniques by reducing maximum response times an average of 30.3%.
17481727
Strain analysis and visualization: left ventricle of a heart
Abstract Clinical utility of computational models is crucial in the applications of medical data visualization. Previously we have developed a new class of volumetric models whose parameters are functions in conjunction with physically based deformable modeling framework, and have applied the technique to estimate the left ventricular (LV) wall motion. We have successfully showed that the model parameter functions characterize the LV motion of normal and abnormal states and that no further non-trivial post-processing is required for anatomically meaningful interpretation. In an effort to evaluate the LV model, this paper presents a method and results from a strain analysis based on the nodal displacements of the deformable LV model. Furthermore, in order to visualize the local quantities on the volumetric model for an effective analysis, we also developed a methodology to assist in assessing the cardiac function utilizing principal strains, Von-Mises’ yield criteria, and a smoothing filter. Each strain tensor component was in the range of values observed in other reported studies. The application of a smoothing filter on the model improved in visualizing the overall trend of each strain variation. With our platform for a comprehensive strain analysis, we have augmented a clinical utility to the deformable models with parameter functions.