12798864
BASS: approximate search on large string databases
In this paper, we study the problem on how to build an index structure for large string databases to efficiently support various types of string matching without the necessity of mapping the substrings to a numerical space (e.g., string B-tree and MRS-index) nor the restriction of in-memory practice (e.g., suffix tree and suffix array). Towards this goal, we propose a new indexing scheme, BASS-tree, to efficiently support general approximate substring match (in terms of certain symbol substitutions and misalignments) in sublinear time on a large string database. The key idea behind the design is that all positions in each string are grouped recursively into a fully balanced tree according to the similarities of the subsequent segments starting at those positions. Each node is labeled with a regular expression that describes the commonality of the substrings indexed through the subtree. Any search can then be properly directed to the portion in the database with a high potential of matching quickly. With the BASS-tree in place, wild card(s) in the query pattern can also be handled in a seamless way. In addition, search of a long pattern can be decomposed into a series of searches of short segments followed by a process to join the results. It has been demonstrated in our experiments that the potential performance improvement brought by BASS-tree is in an order of magnitude over alternative methods.
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.
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.
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.
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.
8299246
HyLog: A High Performance Approach to Managing Disk Layout
Our objective is to improve disk I/O performance in multi-disk systems supporting multiple concurrent users, such as file servers, database servers, and email servers. In such systems, many disk reads are absorbed by large in-memory buffers, and so disk writes comprise a large portion of the disk I/O traffic. LFS (Log-structured File System) has the potential to achieve superior write performance by accumulating small writes into large blocks and writing them to new places, rather than overwriting on top of their old copies (called Overwrite). Although it is commonly believed that the high segment cleaning overhead of LFS makes it a poor choice for workloads with random updates, in this paper we find that because of the fast improvement of disk technologies, LFS significantly outperforms Overwrite in a wide range of system configurations and workloads (including the random update workload) under modern and future disks. 
 
LFS performs worse than Overwrite, however, when the disk space utilization is very high due to the high cleaning cost. In this paper, we propose a new approach, the Hybrid Log-structured (Hy-Log) disk layout, to overcome this problem. Hy-Log uses a log-structured approach for hot pages to achieve high write performance, and Overwrite for cold pages to reduce the cleaning cost. We compare the performance of HyLog to that of Overwrite, LFS and WOLF (the latest improvement on LFS) under various system configurations and workloads. Our results show that, in most cases, Hylog performs comparably to the best of the other three approaches.
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.
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.
5599627
Choosability and edge choosability of planar graphs without five cycles
Abstract It is proved that a planar graph G without five cycles is three degenerate, hence, four choosable, and it is also edge-( Δ ( G ) + 1)-choosable.
45794206
Rational Quadratic Parameterizations of Quadrics
Every irreducible quadric in E3 has infinitely many different rational quadratic parameterizations. These parameterizations and the relationships between them are investigated. It is shown that every faithful rational quadratic parameterization of a quadric can be generated by a stereographic projection from a point on the quadric, called the center of projection (COP). Two such parameterizations for the same quadric are related by a rational linear reparameterization if they have the same COP; otherwise they are related by a rational quadratic reparameterization. We also consider unfaithful parameterizations for which, in general, a one-to-one correspondence between points on the surface and parameters in the plane does not exist. It is shown that all unfaithful rational quadratic parameterizations of a properly degenerate quadric can be characterized by a simple canonical form, and there exist no unfaithful rational quadratic parameterizations for a nondegenerate quadric. In addition, given a faithful rational quadratic parameterization of a quadric, a new technique is presented to compute its base points and inversion formula. These results are applied to solve the problems of parameterizing the intersection of two quadrics and reparameterizing a given quadric parameterization with respect to a different COP without implicitization.