5447146
Mining long sequential patterns in a noisy environment
Pattern discovery in long sequences is of great importance in many applications including computational biology study, consumer behavior analysis, system performance analysis, etc. In a noisy environment, an observed sequence may not accurately reflect the underlying behavior. For example, in a protein sequence, the amino acid N is likely to mutate to D with little impact to the biological function of the protein. It would be desirable if the occurrence of D in the observation can be related to a possible mutation from N in an appropriate manner. Unfortunately, the support measure (i.e., the number of occurrences) of a pattern does not serve this purpose. In this paper, we introduce the concept of compatibility matrix as the means to provide a probabilistic connection from the observation to the underlying true value. A new metric match is also proposed to capture the "real support" of a pattern which would be expected if a noise-free environment is assumed. In addition, in the context we address, a pattern could be very long. The standard pruning technique developed for the market basket problem may not work efficiently. As a result, a novel algorithm that combines statistical sampling and a new technique (namely border collapsing) is devised to discover long patterns in a minimal number of scans of the sequence database with sufficiently high confidence. Empirical results demonstrate the robustness of the match model (with respect to the noise) and the efficiency of the probabilistic algorithm.
19868872
Management Assistance for Work First via a Dynamic Website
The purpose of the Work First project is to assist the state Dept. of Health and Human Services (DHHS) staff and each county Dept. of Social Services (DSS) across the state in the management of welfare reform initiatives. Work First is the cash assistance program in NC. One important objective is to encourage and support program managers to use data on outcomes to assess their performance. This is accomplished by providing them with easy to use and easy to understand comprehensive information on the experiences of families and individuals that have received assistance through their agency over time.
11841640
Accelerating Profile Queries in Elevation Maps
Elevation maps are a widely used spatial data representation in geographical information systems (GIS). Paths on elevation maps can be characterized by profiles, which describe relative elevation as a function of distance. In this research, we address the inverse of this mapping - given a profile, how to efficiently find paths that could have generated it. This is called the profile query problem. Profiles have a wide variety of uses that include registering tracking information, or even other maps, to a given map. We describe a probabilistic model to characterize the maximal likelihood that a point lying on a path matches the query profile. Propagation of such probabilities to neighboring points can effectively prune the search space. This model enables us to efficiently answer queries of arbitrary profiles with user-specified error tolerances. When compared to existing spatial index methods, our approach supports more flexible queries with orders of magnitude speedup.
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.
28890
Extension of Lower Probabilities and Coherence of Belief Measures
Coherence is an important concept which is introduced and discussed in a new mathematics branch, Imprecise Probability Theory. By using the Choquet integral, belief measures can be extended to be coherent lower previsions on the linear space consisting of all bounded functions. As a special case, we establish that all belief measures are coherent imprecise probabilities.
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.
1003852
Upper Bounds of Entire Chromatic Number of Plane Graphs
The entire chromatic number χvef (G) of a plane graph G is the least number of colors assigned to the vertices, edges and faces so that every two adjacent or incident pair of them receive different colors. Kronk and Mitchem (1973) conjectured that χvef (G) ≤ 1 + 4 for every plane graph G. In this paper we prove the conjecture for a plane graph G having χ ′(G) = 1 and give a upper bound χvef (G) ≤ 1+ 5 for all plane graphs, where χ ′(G) and 1 are the chromatic index and the maximum degree of G, respectively.
5467929
Some sufficient conditions for a planar graph of maximum degree six to be Class 1
Let G be a planar graph of maximum degree 6. In this paper we prove that if G does not contain either a 6-cycle, or a 4-cycle with a chord, or a 5- and 6-cycle with a chord, then @g^'(G)=6, where @g^'(G) denotes the chromatic index of G.
15242556
AFOPT: An Efficient Implementation of Pattern Growth Approach
In this paper, we revisit the frequent itemset mining (FIM) problem and focus on studying the pattern growth approach. Existing pattern growth algorithms differ in several dimensions: (1) item search order; (2) conditional database representation; (3) conditional database construction strategy; and (4) tree traversal strategy. They adopted different strategies on these dimensions. Several adaptive algorithms were proposed to try to find good strategies for general situations. In this paper, we described the implementation techniques of an adaptive pattern growth algorithm, called AFOPT, which demonstrated good performance on all tested datasets. We also extended the algorithm to mine closed and maximal frequent itemsets. Comprehensive experiments were conducted to demonstrate the efficiency of the proposed algorithms.
14663639
An Effective Method to Improve Convergence for Sequential Blind Source Separation
Based on conventional natural gradient algorithm (NGA) and equivariant adaptive separation via independence algorithm (EASI), a novel sign algorithm for on-line blind separation of independent sources is presented. A sign operator for the adaptation of the separation model is obtained from the derivation of a generalized dynamic separation model. A variable step-size sign algorithm rooted in NGA is also derived to better match the dynamics of the input signals and unmixing matrix. The proposed algorithms are appealing in practice due to their computational simplicity. Experimental results verify the superior convergence performance over conventional NGA and EASI algorithm in both stationary and non-stationary environments.
2992545
Constrained 3D shape reconstruction using a combination of surface fitting and registration
We investigate 3D shape reconstruction from measurement data in the presence of constraints. The constraints may fix the surface type or set geometric relations between parts of an object's surface, such as orthogonality, parallelity and others. It is proposed to use a combination of surface fitting and registration within the geometric optimization framework of squared distance minimization (SDM). In this way, we obtain a quasi-Newton like optimization algorithm, which in each iteration simultaneously registers the data set with a rigid motion to the fitting surface and adapts the shape of the fitting surface. We present examples to show the applicability of our method to constrained 3D shape fitting for reverse engineering of CAD models and to high accuracy fitting with kinematic surfaces, which include surfaces of revolution (reconstructed from fragments of archeological pottery) and spiral surfaces, which are fitted to 3D measurement data of shells. Our optimization algorithm can combine registration of multiple scans of an object and model fitting into a single optimization process which is shown to be superior to the traditional procedure, which first registers the data and then fits a model to it.