The cloud service marketplace (CSM) is an exploratory project aiming to provide “an AppStore for Services.” It is an intelligent online marketplace that facilitates service discovery and acquisition for enterprise customers. Traditional service discovery and acquisition are time-consuming. In the era of OneClick Checkout and pay-as-you-go service plans, users expect services to be purchased online efficiently and conveniently. However, as services are complex and different from software apps, the currently prevailing App Store based on keyword search is inadequate for services. In CSM, exploring and configuring services are an iterative process. Customers provide their requirements in natural language and interact with the system through questioning and answering. Learning from the input, the system can incrementally clarify users’ intention, narrow down the candidate services, and profile the configuration information for the candidates at the same time. CSM’s back end is built around the Services Knowledge Graph (SKG) and leverages data mining technologies to enable the semantic understanding of customers’ requirements. To quantitatively assess the value of CSM, empirical evaluation on real and synthetic datasets and case studies are given to demonstrate the efficacy and effectiveness of the proposed system.

Event summarization is an effective process that mines and organizes event patterns to represent the original events. It allows the analysts to quickly gain the general idea of the events. In recent years, several event summarization algorithms have been proposed, but they all focus on how to find out the optimal summarization results, and are designed for one-time analysis. As event summarization is a comprehensive analysis work, merely handling this problem with a single optimal algorithm is not enough. In the absence of an integrated summarization solution, we propose an extensible framework – META – to enable analysts to easily and selectively extract and summarize events from different views with different resolutions. In this framework, we store the original events in a carefully-designed data structure that enables an efficient storage and multiresolution analysis. On top of the data model, we define a summarization language that includes a set of atomic operators to manipulate the meta-data. Furthermore, we present 5 commonly used summarization tasks, and show that all these tasks can be easily expressed by the language. Experimental evaluation on both real and synthetic datasets demonstrates the efficiency and effectiveness of our framework.

Service network analysis is an essential aspect of web service discovery, search, mining and recommendation. Many popular web service networks are content-rich in terms of heterogeneous types of entities, attributes and links. A main challenge for ranking services is how to incorporate multiple complex and heterogeneous factors, such as service attributes, relationships between services, relationships between services and service providers or service consumers, into the design of service ranking functions. In this paper, we model services, attributes, and the associated entities, such as providers, consumers, by a heterogeneous service network. We propose a unified neighborhood random walk distance measure, which integrates various types of links and vertex attributes by a local optimal weight assignment. Based on this unified distance measure, a reinforcement algorithm, ServiceRank, is provided to tightly integrate ranking and clustering by mutually and simultaneously enhancing each other such that the performance of both can be improved. An additional clustering matching strategy is proposed to efficiently align clusters from different types of objects. Our extensive evaluation on both synthetic and real service networks demonstrates the effectiveness of ServiceRank in terms of the quality of both clustering and ranking among multiple types of entity, link and attribute similarities in a service network.

The popularity of cloud service spurs the increasing demands of virtual resources to the service vendors. Along with the promising business opportunities, it also brings new technique challenges such as effective capacity planning and instant cloud resource provisioning. In this paper, we describe our research efforts on improving the service quality for the capacity planning and instant cloud resource provisioning problem. We first formulate both of the two problems as a generic cost-sensitive prediction problem. Then, considering the highly dynamic environment of cloud, we propose an asymmetric and heterogeneous measure to quantify the prediction error. Finally, we design an ensemble prediction mechanism by combining the prediction power of a set of prediction techniques based on the proposed measure. To evaluate the effectiveness of our proposed solution, we design and implement an integrated prototype system to help improve the service quality of the cloud. Our system considers many practical situations of the cloud system, and is able to dynamically adapt to the changing environment. A series of experiments on the IBM Smart Cloud Enterprise (SCE) trace data demonstrate that our method can significantly improve the service quality by reducing the resource provisioning time while maintaining a low cloud overhead.

Cloud computing as a service promises many business benefits. The cost to pay is that it also faces many technique challenges. One of the challenges is to effectively manage cloud capacity in response to the increased demand changes in clouds, as computing customers now can provision and de-provision virtual machines more frequently. This paper studies cloud capacity prediction as a response to the challenge. We propose an integrated solution for intelligent cloud capacity estimation. In this solution, a novel measure is introduced to quantify and guide the prediction process. Then an ensemble method is utilized to predict the future provisioning/de-provisioning demands respectively. The cloud capacity is estimated using the active virtual machines and the future provisioning/de-provisioning demands altogether. Our proposed solution is simple and with low computational cost. The experiments on the IBM Smart Cloud Enterprise trace data shows our solution is effective.

Economic analysis on the financial benefits and risks is crucial for deciding whether an IT transformation should take place. While the financial analysis techniques for general investment is well known, and there have been case studies for many IT types of IT transformations, there is no good methodology that an IT professional can follow and readily conduct return on investment or total cost analysis. This paper aims to fill this void and proposes an economic analysis methodology that is applicable to all IT transformations.

For as long as there have been services there has been a desire to have a convenient medium to expose and discover service offerings. Since early on, various efforts have attempted various approaches at the exchange of computational services, prompting the question of whether there is a market for Web services. We believe that a services marketplace should fulfill the promise of an electronic emporium where third party service providers are able to offer their services in a ubiquitous ecosystem, and where service consumers are able to acquire service solutions that are tailored to their requirements. This paper explores the landscape of cloud services marketplaces, where we are, what enablers are needed to realize the vision, and it presents a prospective architecture to that end.

Event mining is a useful way to understand computer system behaviors. The focus of recent works on event mining has been shifted to event summarization from discovering frequent patterns. Event summarization seeks to provide a comprehensible explanation of the event sequence on certain aspects. Previous methods have several limitations such as ignoring temporal information, generating the same set of boundaries for all event patterns, and providing a summary which is difficult for human to understand. In this paper, we propose a novel framework called natural event summarization that summarizes an event sequence using inter-arrival histograms to capture the temporal relationship among events. Our framework uses the minimum description length principle to guide the process in order to balance between accuracy and brevity. Also, we use multi-resolution analysis for pruning the problem space. We demonstrate how the principles can be applied to generate summaries with periodic patterns and correlation patterns in the framework. Experimental results on synthetic and real data show our method is capable of producing usable event summary, robust to noises, and scalable.

Modern computing systems generate large amounts of log data. System administrators or domain experts utilize the log data to understand and optimize system behaviors. Most system logs are raw textual and unstructured. One main fundamental challenge in automated log analysis is the generation of system events from raw textual logs. Log messages are relatively short text messages but may have a large vocabulary, which often result in poor performance when applying traditional text clustering techniques to the log data. Other related methods have various limitations and only work well for some particular system logs. In this paper, we propose a message signature based algorithm logSig to generate system events from textual log messages. By searching the most representative message signatures, logSig categorizes log messages into a set of event types. logSig can handle various types of log data, and is able to incorporate human's domain knowledge to achieve a high performance. We conduct experiments on five real system log data. Experiments show that logSig outperforms other alternative algorithms in terms of the overall performance.

The promise of cloud computing is to provide computing resources instantly whenever they are needed. The state-of-art virtual machine (VM) provisioning technology can provision a VM in tens of minutes. This latency is unacceptable for jobs that need to scale out during computation. To truly enable on-the-fly scaling, new VM needs to be ready in seconds upon request. In this paper, We present an online temporal data mining system called ASAP, to model and predict the cloud VM demands. ASAP aims to extract high level characteristics from VM provisioning request stream and notify the provisioning system to prepare VMs in advance. For quantification issue, we propose Cloud Prediction Cost to encodes the cost and constraints of the cloud and guide the training of prediction algorithms. Moreover, we utilize a two-level ensemble method to capture the characteristics of the high transient demands time series. Experimental results using historical data from an IBM cloud in operation demonstrate that ASAP significantly improves the cloud service quality and provides possibility for on-the-fly provisioning.

In database outsourcing, an enterprise contracts its database management tasks to an outside database service provider to eliminate in-house hardware, software, and expertise needs for running DBMSs. This is attractive especially for the parties with limited abilities in managing their own data. Typically, the client applications want to obtain quality assurance (e.g., data authenticity and query completeness) of the outsourced database service at a low cost. Previous work on database outsourcing has focused on issues such as communication overhead, secure data access, and data privacy. Recent work has introduced the issue of query integrity assurance, but usually, to obtain such assurance incurs a high cost. In this paper, we present a new method called dual encryption to provide low-cost query integrity assurance for outsourced database services. Dual encryption enables cross examination of the outsourced data, which consists of the original data stored under a certain encryption scheme, and another small percentage of the original data stored under a different encryption scheme. We generate queries against the additional piece of data and analyze their results to obtain integrity assurance. Our scheme is provable secure, that is, it is impossible to break our scheme unless some security primitives can be broken. Experiments on commercial workloads show the effectiveness of our approach.

Effective management of Web Services systems relies on accurate understanding of end-to-end transaction flows, which may change over time as the service composition evolves. This work takes a data mining approach to automatically recovering end-to-end transaction flows from (potentially obscure) monitoring events produced by monitoring tools. We classify the caller-callee relationships among monitoring events into three categories(identity, direct-invoke, and cascaded-invoke), and propose unsupervised learning algorithms to generate rules for each type of relationship. The key idea is to leverage the temporal information available in the monitoring data and extract patterns that have statistical significance. By piecing together the caller-callee relationships a teach step along the invocation path, we can recover the end-to-end flow for every executed transaction. Experiments demonstrate that our algorithms outperform human experts in terms of solution quality, scale well with the data size, and are robust against noises in monitoring data.

In this paper, we introduce the DD-STAR project and explain how a data mining service can be offered as an effective way to discover knowledge that is essential to self-healing infrastructure design and optimization. One of the central issues in proactive problem prediction, avoidance, and diagnosis is to model the infrastructure dynamics based on historical monitoring data, and then apply the models to construct self-management self-healing rules.

In this paper, we propose to model time series from a new angle: state transition points. When fluctuation of values in a time series crosses a certain point, it may trigger state transition in the system, which may lead to abrupt changes in many other time series. The concept of state transition points is essential in understanding the behavior of the time series and the behavior of the system. The new measure is robust and is capable of discovering correlations that Pearson's coefficient cannot reveal. We propose efficient algorithms to identify state transition points and to compute correlation between two time series. We also introduce some triangular inequalities to efficiently find highly correlated time series among many time series.

Business system management (BSM), or called business service management, has drawn tremendous attention in recent years. The emergence of the phenomenon is a natural development after system management practitioners realized that understanding the status of a particular IT resource is to comprehend only a small part of the big picture. To truly maximize the business value of IT investments, it is essential to know how resources affects the applications and business processes supported. Equally important is the capability to properly configure IT resource monitoring mechanism to allow system administrators to focus on critical resources with business significance. While much effort has been put into real-time monitoring and reporting mechanism, monitoring design of business systems received comparatively little attention. In this paper, we describe a data-driven approach for monitoring design for both service level and resource utilization.

In this paper, we study the near-neighbor problem based on pattern similarity, a new type of similarity which conventional distance metrics such as Lp norm cannot model effectively. The problem, however, is important to many applications. For example, in DNA microarray analysis, the expression levels of two closely related genes may rise and fall under different external conditions or at different time. Although the magnitude of their expression levels may not be close, the patterns they exhibit over the time or under different conditions can be very similar. In this paper, we measure the distance between two objects by pattern similarity, i.e., whether the two objects exhibit a synchronous pattern of rise and fall under different conditions. We then present an efficient algorithm for near-neighbor search based on pattern similarity, and we perform tests on several real and synthetic data sets to show its effectiveness.

We present an index structure for managing weighted-sequences in large databases. A weighted-sequence is defined as a two-dimensional structure where each element in the sequence is associated with a weight. A series of network events, for instance, is a weighted-sequence in that each event has a timestamp. Querying a large sequence database by events' occurrence patterns is a first step towards understanding the temporal causal relationships among the events. The index structure proposed enables us to efficiently retrieve from the database all subsequences, possibly noncontiguous, that match a given query sequence both by events and by weights. The index method also takes into consideration the nonuniformfrequency distribution of events in the sequence data. In addition, our method finds a broad range of applications in indexing scientific data consisting of multiple numerical columns for discovery of correlations among these columns. For instance, indexing a DNA microarray that records expression levels of genes under different conditions enables us to search for genes whose responses to various experimental perturbations follow a given pattern. We demonstrate, using real-world data sets, that our method is effective and efficient.

Event management is a focal point in building and maintaining high quality information infrastructures. We have witnessed the shift of the paradigm of event management in practice from root cause analysis (RCA) to action-oriented analysis (AOA). IBM has developed a pioneer event management methodology (EMD) based on the AOA paradigm and applied it to more than two hundred production sites with success. Foreseeably, more and more event management professionals will apply AOA in different incarnations in building proactive management facilities. By that, building correct and effective Event Relationship Networks (ERNs) becomes the dominating activity in AOA service design process. Currently, the quality of ERNs and the cost of building them largely depend on the knowledge of domain experts. We believe that we can utilize historical event logs in shortening the ERNs design process and perfecting the quality of ERNs. In this paper, we describe in detail how to apply this data-driven approach in ERN validation, completion and construction.

Exploring large data sets typically involves activities that iterate between data selection and data analysis, in which insights obtained from analysis result in new data selection. Further, data analysis needs to use a combination of analysis techniques: data summarization, mining algorithms and visualization. This interweaving of functions arises both from the semantics of what the analyst hopes to achieve and from scalability requirements for dealing with large data volumes. We refer to such a process as a progressive analysis. Herein is described a tool, Event Miner, that integrates data selection, mining and visualization for progressive analysis of temporal, categorical data. We discuss a data model and architecture. We illustrate how our tool can be used for complex mining tasks such as finding patterns not occurring on Monday. Further, we discuss the novel visualization employed, such as visualizing categorical data and the results of data mining. Also, we discuss the extension of the existing mining framework needed to mine temporal events with multiple attributes. Throughout, we illustrate the capabilities of Event Miner by applying it to event data from large computer networks.

There has been a growing interest in mining frequent itemsets in relational data with multiple attributes. A key step in this approach is to select a set of attributes that group data into transactions and a separate set of attributes that labels data into items. Unsupervised and unrestricted mining, however is stymied by the combinatorial complexity and the quantity of patterns as the number of attributes grows. In this paper we focus on leveraging the semantics of the underlying data for mining frequent itemsets. For instance, there are usually taxonomies in the data schema and functional dependencies among the attributes. Domain knowledge and user preferences often have the potential to significantly reduce the exponentially growing mining space. These observations motivate the design of a user-directed data mining framework that allows such domain knowledge to guide the mining process and control the mining strategy. We show examples of tremendous reduction in computation by using domain knowledge in mining relational data with multiple attributes.

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.

Mining for frequent itemsets typically involves a preprocessing step in which data with multiple attributes are grouped into transactions, and items are defined based on attribute values. We hake observed that such fixed attribute mining can severely constrain the patterns that are discovered. Herein, we introduce mining spaces, a new framework for mining multi-attribute data that includes the discovery of transaction and item definitions (with the exploitation of taxonomies and functional dependencies if they are available). We prove that special downward closure properties (or anti-monotonic property) hold for mining spaces, a result that allows us to construct efficient algorithms for mining patterns without the constraints of fixed attribute mining. We apply our algorithms to real world data collected from a production computer network. The results show that by exploiting the special kinds of downward closure in mining spaces, execution times for mining can be reduced by a factor of three to four.

For large installations, event management is critical to ensuring service quality by responding rapidly to exceptional situations. The key to this is having experts encode their knowledge (e.g., in rules, state machines, codebooks) about the relationship between event patterns and actions to take. Unfortunately, doing so is time-consuming and knowledge-intensive. We propose reducing this burden by using offline decision support consisting of visualizing and mining event histories to discover patterns in event data. Our experience with a wide variety of production data has identified several patterns of interest such as, event bursts and partial periodicities. Herein, we use production data to illustrate how to visualize and mine event patterns, and we describe a tool we have developed to aid in pattern discovery.

An important issue in visualizing categorical data is how to order categorical values. The focus of this paper is on constructing such orderings efficiently without compromising their visual quality.

In this paper we present the landmark model, a model for time series that yields new techniques for similarity-based time series pattern querying. The landmark model does not follow traditional similarity models that rely on pointwise Euclidean distance. Instead, it leads to landmark similarity, a general model of similarity that is consistent with human intuition and episodic memory. By tracking different specific subsets of features of landmarks, we can efficiently compute different landmark similarity measures that are invariant under corresponding subsets of six transformations; namely, shifting, uniform amplitude scaling, uniform time scaling, uniform bi-scaling, time warping and non-uniform amplitude scaling. A method of identifying features that are invariant under these transformations is proposed. We also discuss a generalized approach for removing noise from raw time series without smoothing out the peaks and bottoms. Beside these new capabilities, our experiments show that landmark indexing is considerably fast.