14048105
GString: A Novel Approach for Efficient Search in Graph Databases
Graphs are widely used for modeling complicated data, including chemical compounds, protein interactions, XML documents, and multimedia. Information retrieval against such data can be formulated as a graph search problem, and finding an efficient solution to the problem is essential for many applications. A popular approach is to represent both graphs and queries on graphs by sequences, thus converting graph search to subsequence matching. State-of-the-art sequencing methods work at the finest granularity - each node (or edge) in the graph will appear as an element in the resulting sequence. Clearly, such methods are not semantic conscious, and the resulting sequences are not only bulky but also prone to complexities arising from graph isomorphism and other problems in searching. In this paper, we introduce a novel sequencing method to capture the semantics of the underlying graph data. We find meaningful components in graph structures and use them as the most basic units in sequencing. It not only reduces the size of resulting sequences, but also enables semantic-based searching. In this paper, we base our approach on chemical compound databases, although it can be applied to searching other complicated graphs, such as protein structures. Experiments demonstrate that our approach outperforms state-of-the-art graph search methods.
5103963
Adaptive Load Diffusion for Multiway Windowed Stream Joins
In this paper, we present an adaptive load diffusion operator to enable scalable processing of multiway windowed stream joins (MWSJs) using a cluster system. The load diffusion is achieved by a set of novel semantics-pre serving tuple routing algorithms. Different from previous work, the load diffusion operator can (1) preserve the MWSJ semantics while spreading tuples to different hosts for parallel join processing; (2) achieve fine-grained load balancing among distributed hosts; and (3) perform semantics-preserving online adaptations to maintain optimal performance in dynamic stream environments. We have implemented a prototype of the distributed MWSJ framework on top of the System S distributed stream processing system. Our experiment results based on both real data streams and synthetic workloads show that the load diffusion algorithms can efficiently scale-up the performance of MWSJ processing with low overhead.
18937658
Mining associations by pattern structure in large relational tables
Association rule mining aims at discovering patterns whose support is beyond a given threshold. Mining patterns composed of items described by an arbitrary subset of attributes in a large relational table represents a new challenge and has various practical applications, including the event management systems that motivated this work. The attribute combinations that define the items in a pattern provide the structural information of the pattern. Current association algorithms do not make full use of the structural information of the patterns: the information is either lost after it is encoded with attribute values, or is constrained by a given hierarchy or taxonomy. Pattern structures convey important knowledge about the patterns. We present an architecture that organizes the mining space based on pattern structures. By exploiting the interrelationships among pattern structures, execution times for mining can be reduced significantly. This advantage is demonstrated by our experiments using both synthetic and real-life datasets.
14876394
User Defined Aggregates for Logical Data Languages
A new wave of data-intensive and knowledge-based applications|such as data mining and decision support|require the introduction of complex application-speciic aggregate functions. In this paper, we propose extensions for deductive database systems to support these new applications. We develop constructs, formal semantics, and implementation techniques for user-deened aggregates, and describe their realization in an extended LDL++ system recently built at UCLA. With these extensions, the system can support on-line aggregation, roll-ups for data cubing, temporal aggregates for time-series, iceberg queries, and other recently proposed operators used in decision support and data mining procedures. We then discuss the application of this technology to other DBMSs, and in particular to the SQL3 speciications that support the notion of user-deened aggregates. We show that SQL3 suuers from limitations that severely restrict its use in new applications; thus we propose simple extensions similar to those used for LDL++ to overcome such limitations.
1498767
Clustering by pattern similarity in large data sets
Clustering is the process of grouping a set of objects into classes of similar objects. Although definitions of similarity vary from one clustering model to another, in most of these models the concept of similarity is based on distances, e.g., Euclidean distance or cosine distance. In other words, similar objects are required to have close values on at least a set of dimensions. In this paper, we explore a more general type of similarity. Under the pCluster model we proposed, two objects are similar if they exhibit a coherent pattern on a subset of dimensions. For instance, in DNA microarray analysis, the expression levels of two genes may rise and fall synchronously in response to a set of environmental stimuli. Although the magnitude of their expression levels may not be close, the patterns they exhibit can be very much alike. Discovery of such clusters of genes is essential in revealing significant connections in gene regulatory networks. E-commerce applications, such as collaborative filtering, can also benefit from the new model, which captures not only the closeness of values of certain leading indicators but also the closeness of (purchasing, browsing, etc.) patterns exhibited by the customers. Our paper introduces an effective algorithm to detect such clusters, and we perform tests on several real and synthetic data sets to show its effectiveness.
5368193
Progressive modeling
Presently, inductive learning is still performed in a frustrating batch process. The user has little interaction with the system and no control over the final accuracy and training time. If the accuracy of the produced model is too low, all the computing resources are misspent. In this paper we propose a progressive modeling framework. In progressive modeling, the learning algorithm estimates online both the accuracy of the final model and remaining training time. If the estimated accuracy is far below expectation, the user can terminate training prior to completion without wasting further resources. If the user chooses to complete the learning process, progressive modeling will compute a model with expected accuracy in expected time. We describe one implementation of progressive modeling using ensemble of classifiers.
1542177
Out-of-core tensor approximation of multi-dimensional matrices of visual data
Tensor approximation is necessary to obtain compact multilinear models for multi-dimensional visual datasets. Traditionally, each multi-dimensional data item is represented as a vector. Such a scheme flattens the data and partially destroys the internal structures established throughout the multiple dimensions. In this paper, we retain the original dimensionality of the data items to more effectively exploit existing spatial redundancy and allow more efficient computation. Since the size of visual datasets can easily exceed the memory capacity of a single machine, we also present an out-of-core algorithm for higher-order tensor approximation. The basic idea is to partition a tensor into smaller blocks and perform tensor-related operations blockwise. We have successfully applied our techniques to three graphics-related data-driven models, including 6D bidirectional texture functions, 7D dynamic BTFs and 4D volume simulation sequences. Experimental results indicate that our techniques can not only process out-of-core data, but also achieve higher compression ratios and quality than previous methods.
16518536
Automatic singer recognition of popular music recordings via estimation and modeling of solo vocal signals
In this paper, we investigate the problem of automatic singer identification, detection and tracking in popular music recordings with one or multiple singers. This problem reflects an important issue in multimedia applications that require the transcription and indexing of music data to meet the increasing demand for content-based information retrieval. The major challenges for this study arise from the fact that a singer's voice tends to be arbitrarily altered from time to time and is inextricably intertwined with the signal of the background accompaniment. To determine who is singing, or whether or when a particular singer is present in a music recording, methods are presented for separating vocal from nonvocal regions, for isolating singers' vocal characteristics from background music, and for distinguishing singers from one another. Experimental evaluations conducted on a pop music database consisting of solo and duet tracks confirm the validity of the proposed methods.
12981432
A web-based tutoring system with styles-matching strategy for spatial geometric transformation
It has been a major objective for researchers to develop computer systems that can effectively deliver instruction to learners. Therefore, how to incorporate instructional strategies in computer-assisted learning systems in a systematic manner deserves further investigation. In this paper, a style-matching strategy that attempts to match learning materials' styles to learners' latent traits is proposed and realized in a web-based tutoring system, called CooTutor. The mechanism of adaptive material selection takes learners' different spatial ability and learning styles as an integral learning profile into account, and performs traits-based personalization of learning experience. This system is specifically designed to conquer the difficulty of tutoring the topic on fundamental spatial geometry in conventional curriculums. By conducting empirical evaluation with a small group of students, it is found that CooTutor is generally beneficial to learning the domain, but the effect of the styles-matching mechanism remains inconclusive. The work aims to contribute to the community of adaptive hypermedia in providing an explorative example adopting the concern of individual difference for personalization. The system design, a usage scenario, and an exploratory evaluation are presented in this paper as implications for further studies.
9019747
A Novel Alternative Hypothesis Characterization Using Kernel Classifiers for LLR-Based Speaker Verification
In a log-likelihood ratio (LLR)-based speaker verification system, the alternative hypothesis is usually ill-defined and hard to characterize a priori, since it should cover the space of all possible impostors. In this paper, we propose a new LLR measure in an attempt to characterize the alternative hypothesis in a more effective and robust way than conventional methods. This LLR measure can be further formulated as a non-linear discriminant classifier and solved by kernel-based techniques, such as the Kernel Fisher Discriminant (KFD) and Support Vector Machine (SVM). The results of experiments on two speaker verification tasks show that the proposed methods outperform classical LLR-based approaches.
2846401
Subgraph Join: Efficient Processing Subgraph Queries on Graph-Structured XML Document
The information in many applications can be naturally represented as graph-structured XML document. Structural query on graph structured XML document matches the subgraph of graph structured XML document on some given schema. The query processing of graph-structured XML document brings new challenges. 
 
In this paper, for the processing of subgraph query, we design a subgraph join algorithm based on reachability coding. Using efficient data structure, subgraph join algorithm can process subgraph query with various structures efficiently.