16978334
Evaluating a class of distance-mapping algorithms for data mining and clustering
A distance-mapping algorithm takes a set of objects and a distance metric and then maps those objects to a Euclidean or pseudoEuclidean space in such a way that the distances among objects are approximately preserved. Distance mapping algorithms are a useful tool for clustering and visualization in data intensive applications, because they replace expensive distance calculations by sum-of-square calculations. This can make clustering in large databases with expensive distance metrics practical. In this paper we present five distance-mapping algorithms and conduct experiments to compare their performance in data clustering applications. These include two algorithms called FastMap and MetricMap, and three hybrid heuristics that combine the two algorithms in different ways. Experimental results on both synthetic and RNA data show the superiority of the hybrid algorithms. The results imply that FastMap and MetricMap capture complementary information about distance metrics and therefore can be used together to great benefit. The net effect is that multi-day computations may be done in minutes.
46019766
A Study on Textual Entailment
In this paper we study a graph-based approach to the task of textual entailment between a text and hypothesis. The approach takes into account the full lexico-syntactic context of both the text and hypothesis and relies heavily on the concept of subsumption. It starts with mapping the text and hypothesis into graph structures where nodes represent concepts and edges represent lexico-syntactic relations among concepts. Based on a subsumption score between the text-graph and hypothesis-graph an entailment decision is then made. The impact of synonymy on entailment is quantified and discussed. An important advantage of our solution is the ability to customize it so that high-confidence results are obtained
18266651
A similarity-based soft clustering algorithm for documents
Document clustering is an important tool for applications such as Web search engines. Clustering documents enables the user to have a good overall view of the information contained in the documents that he has. However, existing algorithms suffer from various aspects, hard clustering algorithms (where each document belongs to exactly one cluster) cannot detect the multiple themes of a document, while soft clustering algorithms (where each document can belong to multiple clusters) are usually inefficient. We propose SISC (similarity-based soft clustering), an efficient soft clustering algorithm based on a given similarity measure. SISC requires only a similarity measure for clustering and uses randomization to help make the clustering efficient. Comparison with existing hard clustering algorithms like K-means and its variants shows that SISC is both effective and efficient.
15536346
An Index Structure for Data Mining and Clustering
Abstract. In this paper we present an index structure, called MetricMap, that takes a set of objects and a distance metric and then maps those objects to a k-dimensional space in such a way that the distances among objects are approximately preserved. The index structure is a useful tool for clustering and visualization in data-intensive applications, because it replaces expensive distance calculations by sum-of-square calculations. This can make clustering in large databases with expensive distance metrics practical. We compare the index structure with another data mining index structure, FastMap, recently proposed by Faloutsos and Lin, according to two criteria: relative error and clustering accuracy. For relative error, we show that (i) FastMap gives a lower relative error than MetricMap for Euclidean distances, (ii) MetricMap gives a lower relative error than FastMap for non-Euclidean distances (i.e., general distance metrics), and (iii) combining the two reduces the error yet further. A similar result is obtained when comparing the accuracy of clustering. These results hold for different data sizes. The main qualitative conclusion is that these two index structures capture complementary information about distance metrics and therefore can be used together to great benefit. The net effect is that multi-day computations can be done in minutes.
11135944
Fuzzy Clustering of Web Logs for User Classification
1161117
Fast Similarity Search in the Presence of Noise, Scaling, and Translation in Time-Series Databases
We introduce a new model of similarity of time sequences that captures the intuitive notion that two sequences should be considered similar if they have enough non-overlapping time-ordered pairs of subsequences thar are similar. The model allows the amplitude of one of the two sequences to be scaled by any suitable amount and its offset adjusted appropriately. Two subsequences are considered similar if one can be enclosed within an envelope of a specified width drawn around the other. The model also allows non-matching gaps in the matching subsequences. The matching subsequences need not be aligned along the time axis. Given this model of similarity, we present fast search techniques for discovering all similar sequences in a set of sequences. These techniques can also be used to find all (sub)sequences similar to a given sequence. We applied this matching system to the U.S. mutual funds data and discovered interesting matches.
14056151
Distributed pinwheel scheduling with end-to-end timing constraints
Algorithms for allocating resources and scheduling tasks are important to the success of many real-time systems with end-to-end performance requirements. In this paper, an end-to-end scheduling model based on the pinwheel scheduling algorithms is presented for distributed real-time systems. We discuss how tasks on different nodes may be transformed to have harmonic periods. We also present algorithms to adjust the phases between schedules on neighboring nodes so that the overall end-to-end delay is reduced. Using the pinwheel approach, schedules on different nodes are closely synchronized and more static. However, for many real-time systems, this practical approach may provide a more predictable performance and a shorter end-to-end delay.
41885018
A theory of lexicographic multi-criteria optimization
The field of multi-criteria optimization is reviewed as it pertains to lexicographic optimization over real-valued vector spaces. How lexicographic optimization differs from multi-criteria optimization that is restricted to proper Pareto optima is explained. Through a survey of previous work, it is revealed that there are currently no generally applicable methods for solving lexicographic optimization problems, and it is explained that this is due to the lack of an adequate mathematical theory for such problems. A more adequate mathematical theory is then presented for lexicographic optimization in this paper.
45567604
Hierarchical budget management in the RED-Linux scheduling framework
A hierarchical scheduling mechanism has been implemented in RED-Linux to integrate different scheduling paradigms together. We extend the concept of group so that the execution budget for jobs in RED-Linux can be managed in a hierarchical way. A budget group contains a set of jobs that share the available budget for the group. The jobs in a budget group could be a normal job or another budget group job, which contains its own group of jobs. Every job has its system budget. But if it belongs to a budget group, the job's budget is also constrained by its group's budget. We discuss how the budget group mechanism is implemented in RED-Linux. We also show how to use the mechanism to implement several schedulers.
5848136
Protein metal binding residue prediction based on neural networks
Over one-third of protein structures contain metal ions, which are the necessary elements in life systems. Traditionally, structural biologists were used to investigate properties of metalloproteins (proteins which bind with metal ions) by physical means and interpreting the function formation and reaction mechanism of enzyme by their structures and observations from experiments in vitro. Most of proteins have primary structures (amino acid sequence information) only; however, the 3-dimension structures are not always available. In this paper, a direct analysis method is proposed to predict the protein metal-binding amino acid residues from its sequence information only by neural networks with sliding window-based feature extraction and biological feature encoding techniques. In four major bulk elements (Calcium, Potassium, Magnesium, and Sodium), the metal-binding residues are identified by the proposed method with higher than 90% sensitivity and very good accuracy under 5-fold cross validation. With such promising results, it can be extended and used as a powerful methodology for metal-binding characterization from rapidly increasing protein sequences in the future.
36582531
A semantic-based concurrency control protocol for real-time transactions
Real-time database systems must maintain both logical and temporal data integrity so that transactions can respond to real-world events timely and predictably. For real-time applications, such as avionics and process control, that are connected to sensor devices, the consistency between the device readings and the current values used by transactions could be more important than the serializability of transactions. In this paper, we propose a semantic-based concurrency control protocol that increases the responsiveness of transactions. A method compatibility matrix is created for each object in the database. Transactions request different types of methods according to their consistency requirements. We show the performance of the semantic-based concurrency control protocol by simulation.