3184000
Revealing true subspace clusters in high dimensions
Subspace clustering is one of the best approaches for discovering meaningful clusters in high dimensional space. One cluster in high dimensional space may be transcribed into multiple distinct maximal clusters by projecting onto different subspaces. A direct consequence of clustering independently in each subspace is an overwhelmingly large set of overlapping clusters which may be significantly similar. To reveal the true underlying clusters, we propose a similarity measurement of the overlapping clusters. We adopt the model of Gaussian tailed hyper-rectangles to capture the distribution of any subspace cluster. A set of experiments on a synthetic dataset demonstrates the effectiveness of our approach. Application to real gene expression data also reveals impressive meta-clusters expected by biologists.
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.
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.
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.
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.
3170428
Fitting B-spline curves to point clouds by curvature-based squared distance minimization
Computing a curve to approximate data points is a problem encountered frequently in many applications in computer graphics, computer vision, CAD/CAM, and image processing. We present a novel and efficient method, called squared distance minimization (SDM), for computing a planar B-spline curve, closed or open, to approximate a target shape defined by a point cloud, that is, a set of unorganized, possibly noisy data points. We show that SDM significantly outperforms other optimization methods used currently in common practice of curve fitting. In SDM, a B-spline curve starts from some properly specified initial shape and converges towards the target shape through iterative quadratic minimization of the fitting error. Our contribution is the introduction of a new fitting error term, called the squared distance (SD) error term, defined by a curvature-based quadratic approximant of squared distances from data points to a fitting curve. The SD error term faithfully measures the geometric distance between a fitting curve and a target shape, thus leading to faster and more stable convergence than the point distance (PD) error term, which is commonly used in computer graphics and CAGD, and the tangent distance (TD) error term, which is often adopted in the computer vision community. To provide a theoretical explanation of the superior performance of SDM, we formulate the B-spline curve fitting problem as a nonlinear least squares problem and conclude that SDM is a quasi-Newton method which employs a curvature-based positive definite approximant to the true Hessian of the objective function. Furthermore, we show that the method based on the TD error term is a Gauss-Newton iteration, which is unstable for target shapes with high curvature variations, whereas optimization based on the PD error term is the alternating method that is known to have linear convergence.
39024705
The Linear 2-Arboricity of Planar Graphs
Abstract. Let G be a planar graph with maximum degree Δ and girth g. The linear 2-arboricity la2(G) of G is the least integer k such that G can be partitioned into k edge-disjoint forests, whose component trees are paths of length at most 2. We prove that (1) la2(G)≤⌈(Δ+1)/2⌉+12; (2) la2(G)≤⌈(Δ+1)/2⌉+6 if g≥4; (3) la2(G)≤⌈(Δ+1)/2⌉+2 if g≥5; (4) la2(G)≤⌈(Δ+1)/2⌉+1 if g≥7.
18265885
Identifying intrusions in computer networks with principal component analysis
Most current anomaly intrusion detection systems (IDSs) detect computer network behavior as normal or abnormal but cannot identify the type of attacks. Moreover, most current intrusion detection methods cannot process large amounts of audit data for real-time operation. In this paper, we propose a novel method for intrusion identification in computer networks based on principal component analysis (PCA). Each network connection is transformed into an input data vector. PCA is employed to reduce the dimensionality of the data vectors and identification is handled in a low dimensional space with high efficiency and low use of system resources. The normal behavior is profiled based on normal data for anomaly detection and models of each type of attack are built based on attack data for intrusion identification. The distance between a vector and its reconstruction onto those reduced subspaces representing the different types of attacks and normal activities is used for identification. The method is tested with network data from MIT Lincoln labs for the 1998 DARPA intrusion detection evaluation program and testing results show that the model is promising in terms of identification accuracy and computational efficiency for real-time intrusion identification.
8724139
News Content Highlight via Fast Caption Text Detection on Compressed Video
Captions present in video frames play an important role in understanding video content. This paper presents a fast algorithm to automatically detect captions in MPEG compressed video. It is based on statistics features of caption text's chrominance components. The paper also discusses its principle and speed-up mechanism in detail. We have successfully exploited the technique to automatically construct the pictorial catalogue, a new content representation. Experiment results show the proposed caption detection algorithm has not only the ideal accuracy 96.6% and recall 100%, but also a detection speed of faster than real time.
33629250
Robust Visual Tracking Via Incremental Maximum Margin Criterion
Robust visual object tracking is one of the key problems in computer vision. Subspace based tracking method is a promising approach in handling appearance variability. Linear Discriminant Analysis(LDA) has been applied to this problem, but LDA is not a stable algorithm especially for visual tracking. Maximum Margin Criterion(MMC) is a recently proposed discriminant criterion. Its promising specialities make it a better choice for the tracking problem. In this paper, we present a novel subspace tracking algorithm based on MMC. We also proposed an incremental version of the corresponding algorithm so that the tracker can update in realtime. Experiments show our tracking algorithm is able to track objects well under large lighting, pose and expression variation.