37744397
Stay Current and Relevant in Data Mining Research
In a recent editorial of the Bioinformatics journal, Dr. Pavel Pevzner, a pioneering researcher in the field of bioinformatics, made the following statement [1]: For many years algorithms were taught exclusively to computer scientists, with relatively few students from other disciplines attending algorithms courses. A biology student in an algorithms class would be a surprising and unlikely (though not entirely unwelcome) guest in the 1990s. Things change; some biology students now take some sort of Algorithms 101. At the same time, curious computer science students often take Genetics 101.
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.
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.
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.
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.
206702052
Comparing Customer Trust in Virtual Salespersons With Customer Trust in Human Salespersons
Virtual salespersons (computer agents) act in a similar role in online stores as human salespersons act in physical stores. Customer trust in a salesperson is key in generating transactions and managing customer relationships. In this exploratory study, 44 participants used the services of both virtual and human salespersons in the same commercial store. Written protocols were collected by asking the participants open-ended questions regarding their comparative trust. This paper finds that similar to trust in a human salesperson, trust in a virtual salesperson contains trust in competence, benevolence, and integrity; however, the formation processes of trust in virtual salespersons, trust in human salespersons, distrust in virtual salespersons, and distrust in human salespersons are different. This paper theoretically outlines to what extent research on trust in computer agents can draw from literature on interpersonal trust. It practically contributes to our understanding of how to better design trustworthy virtual salespersons.
3416923
Efficient Computation of the Skyline Cube
Skyline has been proposed as an important operator for multi-criteria decision making, data mining and visualization, and user-preference queries. In this paper. we consider the problem of efficiently computing a SKYCUBE, which consists of skylines of all possible non-empty subsets of a given set of dimensions. While existing skyline computation algorithms can be immediately extended to computing each skyline query independently, such "shared-nothing" algorithms are inefficient. We develop several computation sharing strategies based on effectively identifying the computation dependencies among multiple related skyline queries. Based on these sharing strategies, two novel algorithms, Bottom-Up and Top-Down algorithms, are proposed to compute SKYCUBE efficiently. Finally, our extensive performance evaluations confirm the effectiveness of the sharing strategies. It is shown that new algorithms significantly outperform the naive ones.
1993887
Locating Motifs in Time-Series Data
Finding motifs in time-series is proposed to make clustering of time-series subsequences meaningful, because most existing algorithms of clustering time-series subsequences are reported meaningless in recent studies. The existing motif finding algorithms emphasize the efficiency at the expense of quality, in terms of the number of time-series subsequences in a motif and the total number of motifs found. In this paper, we formalize the problem as a continuous top-k motif balls problem in an m-dimensional space, and propose heuristic approaches that can significantly improve the quality of motifs with reasonable overhead, as shown in our experimental studies.
1103015
Visualization of wormholes in sensor networks
Several protocols have been proposed to defend against wormholes in ad hoc networks by adopting positioning devices, synchronized clocks, or directional antennas. In this paper, we propose a mechanism, MDS-VOW, to detect wormholes in a sensor network. MDS-VOW first reconstructs the layout of the sensors using multi-dimensional scaling. To compensate the distortions caused by distance measurement errors, a surface smoothing scheme is adopted. MDS-VOW then detects the wormhole by visualizing the anomalies introduced by the attack. The anomalies, which are caused by the fake connections through the wormhole, bend the reconstructed surface to pull the sensors that are faraway to each other. Through detecting the bending feature, the wormhole is located and the fake connections are identified. The contributions of MDS-VOW are: (1) it does not require the sensors to be equipped with special hardware, (2) it adopts and combines the techniques from social science, computer graphics, and scientific visualization to attack the problem in network security. We examine the accuracy of the proposed mechanism when the sensors are deployed in a circle area and one wormhole exists in the network. The results show that MDS-VOW has a low false alarm ratio when the distance measurement errors are not large.