Serial episode mining is one of hot spots in temporal data mining with broad applications such as user-browsing behavior prediction, telecommunication alarm analysis, road traffic monitoring, and root cause diagnostics from faults log data in manufacturing. In this paper, as a step forward to analyzing patterns within an event sequence, we propose a novel algorithm FCEMiner (Frequent Closed Episodes Miner) for discovering all frequent closed episodes. To characterize the followed-by-closely relationships over event types well and avoid over-counting the support of long episodes, FCEMiner takes both minimal and non-overlapping occurrences of an episode into consideration. To perform iterative episode growth without generating any candidate, FCEMiner utilizes the depth-first search strategy with Apriori Property. To save the cost of post-processing on frequent episodes, FCEMiner checks the closures of some episodes during each valid episode growth. A set of performance studies on both synthetic and real-world datasets show that our algorithm is more efficient and effective.

Frequent serial episodes within an event sequence describe the behavior of users or systems about the application. Existing mining algorithms calculate the frequency of an episode based on overlapping or non-minimal occurrences, which is prone to over-counting the support of long episodes or poorly characterizing the followed-by-closely relationship over event types. In addition, due to utilizing the Apriori-style level wise approach, these algorithms are computationally expensive. In this paper, we propose an efficient algorithm MANEPI (Minimal And Non-overlapping EPIsode) for mining more interesting frequent episodes within the given event sequence. The proposed frequency measure takes both minimal and non-overlapping occurrences of an episode into consideration and ensures better mining quality. The introduced depth first search strategy with the Apriori Property for performing episode growth greatly improves the efficiency of mining long episodes because of scanning the given sequence only once and not generating candidate episodes. Moreover, an optimization technique is presented to narrow down search space and speed up the mining process. Experimental evaluation on both synthetic and real-world datasets demonstrates that our algorithms are more efficient and effective.

In this paper, we study the problem of making use of target constraints to integrate XML data from different sources under a target schema. We recognize that target constraints are necessary in data integration, as the constraints are essential part of data semantics, and should be satisfied by integrated data. When integrating data from multiple data sources with overlapping data, constraints can express data merging rules at the target as well. We give a general constraint model for XML to express target constraints, which extends the relational equality-generating and tuple- generating dependencies. We provide a chase method to reason about data in the integrated XML document based on target constraints, by inferring data values not given explicitly, and inserting new subtrees as necessary. Singleton and key constraints are used to uniquely specify a certain entity, as a rule for data merging in the integration.

Search engine technology plays an important role in Web information retrieval. However, with Internet information explosion, traditional searching techniques cannot provide satisfactory result due to problems such as huge number of result Web pages, unintuitive ranking, etc. Therefore, the reorganization and post-processing of Web search results have been extensively studied to help user effectively obtain useful information. Previous studies mainly focused on Web page clustering, document summary, visualization of search results, etc, which are applied separately to either text or image search. In this paper, we propose a demo to illustrate a new Web search result summary system - PictureBook, which combines text and image retrieval using techniques of multiple document summarization and image semantics analysis. Particularly, audience can interactively investigate the effect of the combined text and image summary in Web information searching and knowledge acquisition. We also introduce our new image semantic analysis method based on generalized discriminant analysis (GDA).

Information sharing becomes more frequently and easily than before. However, it also brings serious threats towards individual's privacy. It is no doubt that sharing personal data can cause privacy breaches. Moreover, sharing the knowledge discovered by data mining may also pose threats to personal privacy. In this paper, we consider the anonymity of patterns derived from the result of frequent itemset mining. A new projection-based approach for detecting anonymity of patterns is presented. We prove that the approach can detect all the maximal inference channels for non-k-anonymous patterns. The experimental results show that our approach is more efficient than previous work especially when the number of closed frequent itemsets in the mining result is close to or larger than the number of transactions in a database.

The knowledge discovered by frequent pattern mining is represented in the form of a collection of frequent patterns with their supports. Sharing the frequent patterns without discrimination may bring threats against privacy and security, because some of frequent patterns themselves may be sensitive and should not be disclosed. Furthermore, due to the existence of inference channels, an attacker may also derive sensitive patterns from a set of non-sensitive patterns. Therefore, just eliminating sensitive patterns from the mining result is not enough to prevent their disclosure. We classify the potential inference channels into three categories, and present two algorithms for blocking these inference channels by pattern sanitization. The main advantage of our work is that it does not bring about any fake knowledge, and also does not distort the original knowledge.

Active learning is a promising tool to improve the performance of content-based image retrieval (CBIR). As a commonly used active learning approach, angle-diversity provides the most informative images to user for feedback. However, it suffers from the problem that the query concept is diverse and the numbers of the positive and the negative images are imbalanced. As a consequence, the positive samples obtained by active learning are inadequate, which degrades the learning efficiency. To deal with this issue, we propose a novel method based on angle-diversity and hyperplane shifting to increase the number of positive images in the active learning results. The experiment is conducted on a test data set with 10,000 images. Compared with the traditional angle-diversity technique, our method can improve the retrieval performance significantly.

Many applications track streaming data for actionable alerts, which may include, for example, network intrusions, transaction frauds, bio-surveilence abnormalities, and so forth. Some stream classification models are built for this purpose. Due to concept drifts, maintaining a model's up-to-dateness has become one of the most challenging tasks in mining data streams. State-of-the-art approaches, including both the incrementally updated classifiers and the ensemble classifiers, have proved that model update is a very costly process. In this paper, we show that reducing model granularity reduces the update cost, as models of fine granularity enable us to efficiently pinpoint local components in the model that are affected by the concept drift. It also enables us to derive new model components to reflect the current data distribution, thus avoiding expensive updates on a global scale. Furthermore, those actionable alerts being monitored are usually rare occurrences. The existing stream classifiers cannot handle this problem. We address this problem and show that the low-granularity classifier handles rare events on stream data with ease. Experiments on real and synthetic data show that our approach is able to maintain good prediction accuracy at a fraction of the model updating cost of state-of-the-art approaches.

rdquoApplication-level multicast is a promising alternative to IP multicast due to its independence from the IP routing infrastructure and its flexibility in constructing the delivery trees. The existing overlay multicast systems either support a single data source or have high maintenance overhead when multiple sources are allowed. They are inefficient for applications that require any-source multicast with varied host capacities and dynamic membership. This paper proposes ACOM, an any-source capacity-constrained overlay multicast system, consisting of three distributed multicast algorithms on top of a non-DHT overlay network with simple structures (random overlay with a non-DHT ring) that are easy to manage as nodes join and depart. The nodes have different capacities, and they can support different numbers of direct children during a multicast session. No explicit multicast trees are maintained on top of the overlay. The distributed execution of the algorithms naturally defines an implicit, roughly balanced, capacity-constrained multicast tree for each source node. We prove that the system can deliver a multicast message from any source to all nodes in expected O(logcn) hops, which is asymptotically optimal, where c is the average node capacity and n is the number of members in a multicast group.

Currently technologies of Web services have greatly developed and provided a new application platform for CSCW. For a business process across enterprises, cooperation of multiple Web services is usually required to achieve the final goal. However, most current Web services choreography proposals, such as BPEL4WS or WSCI, only provide a fixed execution flow, lacking of flexibility and adaptability. In this paper, we propose a flexible workflow model TDWF, which can specify the execution process of Web services according to task dependency information, so that the Web services can be composed dynamically. We also put forward an algorithm to verify the correctness of the composition process. Besides, the proposed compensation mechanism of workflow could properly satisfy the requirements of end users

An avalanche of data available in the stream form is overstretching our data analyzing ability. In this paper, we propose a novel load shedding method that enables fast and accurate stream data classification. We transform input data so that its class information concentrates on a few features, and we introduce a progressive classifier that makes prediction with partial input. We take advantage of stream data's temporal locality -for example, readings from a temperature sensor usually do not change dramatically over a short period of time -for load shedding. We first show that temporal locality of the original data is preserved by our transform, then we utilize positive and negative knowledge about the data (which is of much smaller size than the data itself) for classification. We employ both analytical and empirical analysis to demonstrate the advantage of our approach.

Privacy becomes a more and more serious concern in applications involving microdata. Recently, efficient anonymization has attracted much research work. Most of the previous methods use global recoding, which maps the domains of the quasi-identifier attributes to generalized or changed values. However, global recoding may not always achieve effective anonymization in terms of discernability and query answering accuracy using the anonymized data. Moreover, anonymized data is often for analysis. As well accepted in many analytical applications, different attributes in a data set may have different utility in the analysis. The utility of attributes has not been considered in the previous methods.In this paper, we study the problem of utility-based anonymization. First, we propose a simple framework to specify utility of attributes. The framework covers both numeric and categorical data. Second, we develop two simple yet efficient heuristic local recoding methods for utility-based anonymization. Our extensive performance study using both real data sets and synthetic data sets shows that our methods outperform the state-of-the-art multidimensional global recoding methods in both discernability and query answering accuracy. Furthermore, our utility-based method can boost the quality of analysis using the anonymized data.

Wireless sensor networks have emerged recently as an effective way of gathering useful information from areas of interest. Prolonging the network lifetime has become the primary concern in data gathering due to the limited battery power of sensors. An underlying assumption of most existing work is that all the sensors are working simultaneously during the whole process of data gathering. In this paper, we introduce a new definition of the network lifetime in view of the coverage condition, and then investigate the coverage-based maximum lifetime data gathering problem theoretically. Two critical issues are how to selectively organize part of sensors to work and how to execute routing in a single working set. Considering both of these two problems together, we propose the algorithm CODAG. CODAG employs the tree structured routing scheme and enables the routing effects of two different sets theoretically comparable. Based on the maximal increased weight in the routing tree, it divides all the sensors into disjoint cover sets without redundant ones, which in turn leads to the better routing effect. Experimental results show that our algorithm has the good performance for prolonging the lifetime of the whole sensor network.

Many applications use classification models on streaming data to detect actionable alerts. Due to concept drifts in the underlying data, how to maintain a model's up-to-dateness has become one of the most challenging tasks in mining data streams. State of the art approaches, including both the incrementally updated classifiers and the ensemble classifiers, have proved that model update is a very costly process. In this paper, we introduce the concept of model granularity. We show that reducing model granularity will reduce model update cost. Indeed, models of fine granularity enable us to efficiently pinpoint local components in the model that are affected by the concept drift. It also enables us to derive new components that can easily integrate with the model to reflect the current data distribution, thus avoiding expensive updates on a global scale. Experiments on real and synthetic data show that our approach is able to maintain good prediction accuracy at a fraction of model updating cost of state of the art approaches.

Mining frequent structural patterns from graph databases is an important research problem with broad applications. Recently, we developed an effective index structure, ADI, and efficient algorithms for mining frequent patterns from large, disk-based graph databases [5], as well as constraint-based mining techniques. The techniques have been integrated into a research prototype system--- GraphMiner. In this paper, we describe a demo of GraphMiner which showcases the technical details of the index structure and the mining algorithms including their efficient implementation, the mining performance and the comparison with some state-of-the-art methods, the constraint-based graph-pattern mining techniques and the procedure of constrained graph mining, as well as mining real data sets in novel applications.

The compatibility analysis is absolutely necessary for guaranteeing the correct composition of Web services, no matter what styles the composition takes, statically or dynamically. In this paper, we provide a formalization of Web services behavior using the approach of automata. With this understanding, we propose a definition of role among Web services interactions. As a result, we can check whether two or more Web services are compatible in collaboration or not.

Mining frequent structural patterns from graph databases is an interesting problem with broad applications. Most of the previous studies focus on pruning unfruitful search subspaces effectively, but few of them address the mining on large, disk-based databases. As many graph databases in applications cannot be held into main memory, scalable mining of large, disk-based graph databases remains a challenging problem. In this paper, we develop an effective index structure, ADI (for adjacency index), to support mining various graph patterns over large databases that cannot be held into main memory. The index is simple and efficient to build. Moreover, the new index structure can be easily adopted in various existing graph pattern mining algorithms. As an example, we adapt the well-known gSpan algorithm by using the ADI structure. The experimental results show that the new index structure enables the scalable graph pattern mining over large databases. In one set of the experiments, the new disk-based method can mine graph databases with one million graphs, while the original gSpan algorithm can only handle databases of up to 300 thousand graphs. Moreover, our new method is faster than gSpan when both can run in main memory.

The Web resource is a rich collection of the dynamic information, which is useful in various disciplines. There has also been much research work related to improving the quality of information searching in the Web. However, most of the work is still inadequate to satisfy a diversified demand from users. In this paper, we exploit the hyperlinks in the Web and propose a new approach called SFP in order to improve the quality of research results obtain from search engines. The SFP algorithm evolves from the frequent pattern mining technique, which is a common data mining technique for conventional databases. The essential idea of our approach is to mine the frequent structures of links from a given Web topology. By using the SFP algorithm, we extract the authoritative pages and communities from the complex Web topology. We demonstrate our approach by running several experiments and show that the performance and functionalities of using the SFP in managing search results are better than other known methods such as HITS.

A great deal of Web table information exists in cooperative learning activities. The paper presents a new method that extracts information from tables of Web documents. Using a tabled abstract semantic model to describe complicated tables and understand tables from the point of view of semantics, the method reduces the dependence for the design difference of table constructions in the extraction process. At the same time, it utilizes the characteristics of HTML and the techniques of natural language processing to design some heuristic rules, and thus aids the identification of table items. On the above basis, we design a prototype, "EXTable", and then gain a better result according to experimentation.

In mobile wireless systems data on air can be accessed by a large number of mobile users. Many of these applications such as wireless internets and traffic information systems are pull-based, that is, they respond to on-demand user requests. In this paper, we study the scheduling problems of on-demand broadcast environments. Traditionally, the response time of the requests has been used as a performance measure. In this paper we consider the performance as the average cost of request composed of three kinds of costs—access time cost, tuning time cost, and cost of handling failure request. Our main contribution is a self-adaptive scheduling algorithm named LDFC, which computes the delay cost of data item as the priority for broadcast. It performs well compared with some previous algorithms in this context.

Test generation algorithms are being developed with the continuous creation of incredibly sophisticated computer systems. Although dozens of algorithms have been proposed to cope with these issues, there still remains much to be desired in solving such problems as to determine: which of the existing test generation algorithms could be the most efficient for some particular sequential circuits because different algorithms will be better in different circuits; which testability parameters will have the most or the least influences on test generations so that the designers of circuits can have a global understanding during the designing stage. Testability predicting methodology for sequential circuits using a neural network model has been presented, which a user usually needs for analyzing his/her own circuits and selecting the most suitable test generation algorithm from all the possible algorithms they have, and which a designer for VLSI circuits always needs for making his/her circuits being designed more testable.