18247103
InfoMiner+: mining partial periodic patterns with gap penalties
In this paper we focus on mining periodic patterns allowing some degree of imperfection in the form of random replacement from a perfect periodic pattern. Information gain was proposed to identify patterns with events of vastly different occurrence frequencies and adjust for deviation from a pattern. However, it does not involve a penalty if there exists some gap between pattern occurrences. In many applications, e.g., bioinformatics, it is important to identify subsequences that a pattern repeats perfectly (or near perfectly). As a solution, we extend the information gain measure to include a penalty for gaps between pattern occurrences. We call this measure generalized information gain. Furthermore, we need to find a subsequence S' such that for a pattern P, the generalized information gain of P in S' is high. This is particularly useful in locating repeats in DNA sequences. In this paper, we developed an effective mining algorithm, InfoMiner+, to simultaneously mine significant patterns and associated subsequences.
7408751
Quantitative Association Analysis Using Tree Hierarchies
Association analysis arises in many important applications such as bioinformatics and business intelligence. Given a large collection of measurements over a set of samples, association analysis aims to find dependencies of target variables to subsets of measurements. Most previous algorithms adopt a two-stage approach; they first group samples based on the similarity in the subset of measurements, and then they examine the association between these groups and the specified target variables without considering the inter-group similarities or alternative groupings. This can lead to cases where the strength of association depends significantly on arbitrary clustering choices. In this paper, we propose a tree-based method for quantitative association analysis. Tree hierarchies derived from sample similarities represent many possible sample groupings. They also provide a natural way to incorporate domain knowledge such as ontologies and to identify and remove outliers. Given a tree hierarchy, our association analysis evaluates all possible groupings and selects the one with strongest association to the target variable. We introduce an efficient algorithm, TreeQA, to systematically explore the search-space of all possible groupings in a set of input trees, with integrated permutation tests. Experimental results show that TreeQA is able to handlelarge-scale association analysis very efficiently and is more effective and robust in association analysis than previous methods.
5788516
Efficient genome ancestry inference in complex pedigrees with inbreeding
Motivation: High-density SNP data of model animal resources provides opportunities for fine-resolution genetic variation studies. These genetic resources are generated through a variety of breeding schemes that involve multiple generations of matings derived from a set of founder animals. In this article, we investigate the problem of inferring the most probable ancestry of resulting genotypes, given a set of founder genotypes. Due to computational difficulty, existing methods either handle only small pedigree data or disregard the pedigree structure. However, large pedigrees of model animal resources often contain repetitive substructures that can be utilized in accelerating computation. Results: We present an accurate and efficient method that can accept complex pedigrees with inbreeding in inferring genome ancestry. Inbreeding is a commonly used process in generating genetically diverse and reproducible animals. It is often carried out for many generations and can account for most of the computational complexity in real-world model animal pedigrees. Our method builds a hidden Markov model that derives the ancestry probabilities through inbreeding process without explicit modeling in every generation. The ancestry inference is accurate and fast, independent of the number of generations, for model animal resources such as the Collaborative Cross (CC). Experiments on both simulated and real CC data demonstrate that our method offers comparable accuracy to those methods that build an explicit model of the entire pedigree, but much better scalability with respect to the pedigree size. Contact: weiwang@cs.unc.edu
62615149
Mining Asynchronous Periodic Patterns in Time Series Data
Periodicy detection in time series data is a challenging problem of great importance in many applications. Most previous work focused on mining synchronous periodic patterns and did not recognize the misaligned presence of a pattern due to the intervention of random noise. In this paper, we propose a more flexible model of asynchronous periodic pattern that may be present only within a subsequence and whose occurrences may be shifted due to disturbance. Two parameters min/spl I.bar/rep and max/spl I.bar/dis are employed to specify the minimum number of repetitions that is required within each segment of nondisrupted pattern occurrences and the maximum allowed disturbance between any two successive valid segments. Upon satisfying these two requirements, the longest valid subsequence of a pattern is returned. A two-phase algorithm is devised to first generate potential periods by distance-based pruning followed by an iterative procedure to derive and validate candidate patterns and locate the longest valid subsequence. We also show that this algorithm cannot only provide linear time complexity with respect to the length of the sequence but also achieve space efficiency.
14969897
Dynamic adaptive file management in a local area network
In light of advances in processor and networking technology, especially the emergence of network attached disks, the traditional client-server architecture of file systems has become suboptimal for many computation/data intensive applications. We introduce a revised architecture for file management employing network attached storage: the dynamic file server environment (Dynamo). Dynamo introduces two main architectural innovations: to provide high scalability, the file management functions are mainly performed cooperatively by the clients in the system. Furthermore, data is transferred directly to the client's cache from network-attached disks, thus avoiding copies from a disk to the server buffer and then over the network to the client. Secondly, Dynamo uses a cooperative cache management which employs a decentralized lottery-based page replacement strategy. We show via performance benchmarks run on the Dynamo system and simulation results how this architecture increases the system's adaptability, scalability and cost performance.
2548187
Mining asynchronous periodic patterns in time series data
Periodicy detection in time series data is a challenging problem of great importance in many applications. Most previous work focused on mining synchronous periodic patterns and did not recognize the misaligned presence of a pattern due to the intervention of random noise. In this paper, we propose a more flexible model of asynchronous periodic pattern that may be present only within a subsequence and whose occurrences may be shifted due to disturbance. Two parameters min rep and max dis are employed to specify the minimum number of repetitions that is required within each segment of nondisrupted pattern occurrences and the maximum allowed disturbance between any two successive valid segments. Upon satisfying these two requirements, the longest valid subsequence of a pattern is returned. A two-phase algorithm is devised to first generate potential periods by distance-based pruning followed by an iterative procedure to derive and validate candidate patterns and locate the longest valid subsequence. We also show that this algorithm cannot only provide linear time complexity with respect to the length of the sequence but also achieve space
19598296
Type I HARQ performance modeling and evaluation of mobile WiMAX for network simulators
While the development of Mobile WiMAX devices is still an ongoing process, complete and accurate simulations become more important in order to study the performance of Mobile WiMAX based broadband wireless access networks. To further improve network simulation models for Mobile WiMAX, we have theoretically modeled the Hybrid Automatic Retransmission reQuest (HARQ) mechanism and evaluated its performance and accuracy. In this paper, we present the design and implementation methodology of the Mobile WiMAX HARQ simulation model in system-level network simulators in order to gain the benefit of link quality improved by enabling HARQ. Our results show that HARQ achieves higher throughput even at low signal strength which can be considered as non-line-of-sight (NLOS) environments. We believe the implementation of HARQ in the network simulation model and its evaluation studies will provide profound understanding to Mobile WiMAX field test studies.
14352341
Energy-Distortion-Authentication Optimized Resource Allocation for Secure Wireless Image Streaming
Joint consideration of energy efficiency, multimedia quality and media authenticity has largely been overlooked in the studies of secure wireless multimedia streaming. In this paper, we propose an authentication - resource allocation framework for secure transmission of multimedia streaming over energy constrained wireless networks. The contributions of this research can be summarized in three aspects. Firstly, a hash chain based stream level authentication scheme compatible for JPEG2000 compression standard is proposed. Secondly, link layer energy- distortion is modeled, and the energy-distortion convex hull is efficiently identified, which significantly reduces optimization complexity. Finally, an authentication oriented resource allocation scheme is proposed based on the proposed authentication scheme and link layer energy-distortion convex hull, where the authenticated image quality is optimized according to energy budget constraints.
12878597
Pattern Mining for Information Extraction Using Lexical, Syntactic and Semantic Information: Preliminary Results
A method is being developed to mine a text corpus for candidate linguistic patterns for information extraction. The candidate patterns can be used to improve the quality of extraction patterns constructed by a pseudosupervised learning method--an automated method in which the system is provided with a high quality seed pattern or clue, which is used to generate a training set automatically. The study is carried out in the context of developing a system to extract disease-treatment information from medical abstracts retrieved from the Medline database. In an earlier study, the Apriori algorithm had been used to mine a sample of sentences containing a disease concept and a drug concept, to identify frequently occurring word patterns to see if these patterns could be used to identify treatment relations in text. Word patterns and statistical association measures alone were found to be insufficient for generating good extraction patterns, and need to be combined with syntactic and semantic constraints. In this study, we explore the use of syntactic, semantic and lexical constraints to improve the quality of extraction patterns.
18635626
Storing Normalized XML Documents in Normalized Relations
This paper studies the XML storage in relations. Unlike traditional techniques, it considers the semantics expressed by functional dependencies. We propose an algorithm for mapping DTD to relational schema, which preserves not only the content and structure but also the semantics of original XML documents. To tackle the problem of constraints expression, we introduce a way to define functional dependencies and normalization for DTD. In a normalized DTD, every constraints expressed by functional dependencies can be concluded to keys. So we use the key definitions for XML as the foundation for relation generation, and maintain the keys in relations. After investigating the relationship between functional dependencies in XML documents with the corresponding ones in relations, we further prove that, if the original DTD is normalized, the generated relations will be in BCNF. So our method keeps the good properties of normalized DTD, and can fully leverage the relational technology
139968
Efficient Pattern-Growth Methods for Frequent Tree Pattern Mining
Mining frequent tree patterns is an important research problems with broad applications in bioinformatics, digital library, e-commerce, and so on. Previous studies highly suggested that pattern-growth methods are efficient in frequent pattern mining. In this paper, we systematically develop the pattern growth methods for mining frequent tree patterns. Two algorithms, Chopper and XSpanner, are devised. An extensive performance study shows that the two newly developed algorithms outperform TreeMinerV [13], one of the fastest methods proposed before, in mining large databases. Furthermore, algorithm XSpanner is substantially faster than Chopper in many cases.