2673667
ApproxMAP: Approximate Mining of Consensus Sequential Patterns
Conventional sequential pattern mining methods may meet inherent difficulties in mining databases with long sequences and noise. They may generate a huge number of short and trivial patterns but fail to find interesting patterns approximately shared by many sequences. In this paper, we propose the theme of approximate sequential pattern mining roughly defined as identifying patterns approximately shared by many sequences. We present an efficient and effective algorithm, ApproxMAP, to mine consensus patterns from large sequence databases in two steps. First, sequences are clustered by similarity. Then, consensus patterns are mined directly from each cluster through multiple alignment. We use a real case study to illustrate the effectiveness of ApproxMAP.
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.
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.
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.
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.
14797393
A system for analyzing and indexing human-motion databases
We demonstrate a data-driven approach for representing, compressing, and indexing human-motion databases. Our modeling approach is based on piecewise-linear components that are determined via a divisive clustering method. Selection of the appropriate linear model is determined automatically via a classifier using a subspace of the most significant, or principle features (markers). We show that, after offline training, our model can accurately estimate and classify human motions. We can also construct indexing structures for motion sequences according to their transition trajectories through these linear components. Our method not only provides indices for whole and/or partial motion sequences, but also serves as a compressed representation for the entire motion database. Our method also tends to be immune to temporal variations, and thus avoids the expense of time-warping.
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.
7654975
Using low-discrepancy sequences and the Crofton formula to compute surface areas of geometric models
The surface area of a geometric model, like its volume, is an important integral property that needs to be evaluated frequently and accurately in practice. In this paper, we present a new quasi-Monte Carlo method using low-discrepancy sequences for computing the surface area of a 3D object. We show that the new method is more efficient than a Monte Carlo method using pseudo-random numbers. This method is based on the Cauchy ‐ Crofton formula from integral geometry, and it computes the surface area of a 3D body B by counting the number of intersection points between the boundary surface of B and a set of straight lines in E 3 . Low discrepancy sequences are used to generate the set of lines in E 3 to reduce the estimation errors that would be caused by using statistically uniformly distributed lines. We study and compare two different methods for generating 3D random lines, and demonstrate their validity theoretically and experimentally. Experiments suggest that the new quasi-Monte Carlo method is also more efficient than the conventional approach based on surface tessellation. q 2002 Elsevier Science Ltd. All rights reserved.
16675497
Revisiting the [mu]-basis of a rational ruled surface
The µ-basis of a rational ruled surface P(s,t) = P0(s) + tP1(s) is defined in Chen et al. (Comput. Aided Geom. Design 18 (2001) 61) to consist of two polynomials p(x, y, z, s) and q(x, y, z, s) that are linear in x, y, z. It is shown there that the resultant of p and q with respect to s gives the implicit equation of the rational ruled surface; however, the parametric equation P(s, t) of the rational ruled surface cannot be recovered from p and q. Furthermore, the µ-basis thus defined for a rational ruled surface does not possess many nice properties that hold for the µ-basis of a rational planar curve (Comput. Aided Geom. Design 18 (1998) 803). In this paper, we introduce another polynomial r(x, y, z, s, t) that is linear in x, y, z and t such that p, q, r can be used to recover the parametric equation P(s, t) of the rational ruled surface; hence, we redefine the µ-basis to consist of the three polynomials p, q, r. We present an efficient algorithm for computing the newly-defined µ-basis, and derive some of its properties. In particular, we show that the new µ-basis serves as a basis for both the moving plane module and the moving plane ideal corresponding to the rational ruled surface.
9332288
Choosability, Edge Choosability, and Total Choosability of Outerplane Graphs
Let ?l(G),?l? (G),?l?? (G), and ?(G) denote, respectively, the list chromatic number, the list chromatic index, the list total chromatic number, and the maximum degree of a non-trivial connected outerplane graph G. We prove the following results. (1) 2 ??l(G) ? 3 and?l (G) = 2 if and only if G is bipartite with at most one cycle. (2)?(G) ??l?(G) ??(G) + 1 and?l? (G) =?(G) + 1 if and only if G is an odd cycle. This proves the well-known list edge coloring conjecture for outerplane graphs. (3)?l??(G) =?(G) + 1 if ?(G) ? 4 and ?l??(G) ? 5 if ?(G) ? 3. This proves a conjecture of O. V. Borodin, A. V. Kostochka and D. R. Woodall, List edge and list total coloring of multigraphs, J. Comb. Theory B, 71 (1997), 184?204 for outerplane graphs.
8256320
Fast computation with neural oscillators
This paper studies new spike-based models for winner-take-all computation and coincidence detection. In both cases, fast convergence is achieved independent of initial conditions, and network complexity is linear in the number of inputs. Fully distributed versions can be modelled based on groups of interneurons connected through electrical synapses.