The papers in this special section were presented at the 32nd International Conference on Data Engineering that was held in Helsinki, Finland, May 16- May 20, 2016.

Users often write reviews on different themes involving linguistic structures with complex sentiments. The sentiment polarity of a word can be different across themes. Moreover, contextual valence shifters may change sentiment polarity depending on the contexts that they appear in. Both challenges cannot be modeled effectively and explicitly in traditional sentiment analysis. Studying both phenomena requires multi-theme sentiment analysis at the word level, which is very interesting but significantly more challenging than overall polarity classification. To simultaneously resolve the multi-theme and sentiment shifting problems, we propose a data-driven framework to enable both capabilities: (1) polarity predictions of the same word in reviews of different themes, and (2) discovery and quantification of contextual valence shifters. The framework formulates multi-theme sentiment by factorizing the review sentiments with theme/word embeddings and then derives the shifter effect learning problem as a logistic regression. The improvement of sentiment polarity classification accuracy demonstrates not only the importance of multi-theme and sentiment shifting, but also effectiveness of our framework. Human evaluations and case studies further show the success of multi-theme word sentiment predictions and automatic effect quantification of contextual valence shifters.

Enterprise customers increasingly require greater flexibility in the way they access and process their Big Data while at the same time they continue to request advanced analytics and access to diverse data sources. Yet customers also still require the robustness of enterprise class analytics for their mission-critical data. In this paper, we present our initial efforts toward a solution that satisfies the above requirements by integrating the HPE Vertica enterprise database with Apache Spark's open source big data computation engine. In particular, it enables fast, reliable transferring of data between Vertica and Spark; and deploying Machine Learning models created by Spark into Vertica for predictive analytics on Vertica data. This integration provides a fabric on which our customers get the best of both worlds: it extends Vertica's extensive SQL analytics capabilities with Spark's machine learning library (MLlib), giving Vertica users access to a wide range of ML functions; it also enables customers to leverage Spark as an advanced ETL engine for all data that require the guarantees offered by Vertica.

Due to R's popularity as a data-mining tool, many distributed systems expose an R-based API to users who need to build a distributed application in R. As a result, data scientists have to learn to use different interfaces such as RHadoop, SparkR, Revolution R's ScaleR, and HPE's Distributed R. Unfortunately, these interfaces are custom, non-standard, and difficult to learn. Not surprisingly, R applications written in one framework do not work in another, and each backend infrastructure has spent redundant effort in implementing distributed machine learning algorithms. Working with the members of R-core, we have created ddR (Distributed Data structures in R), a unified system that works across different distributed frameworks. In ddR, we introduce a novel programming primitive called dmapply that executes functions on distributed data structures. The dmapply primitive encapsulates different computation patterns: from function and data broadcast to pair-wise communication. We show that dmapply is powerful enough to express algorithms that fit the statistical query model, which includes many popular machine learning algorithms, as well as applications written in MapReduce. We have integrated ddR with many backends, such as R's single-node parallel framework, multi-node SNOW framework, Spark, and HPE Distributed R, with few or no modifications to any of these systems. We have also implemented multiple machine learning algorithms which are not only portable across different distributed systems, but also have performance comparable to the "native" implementations on the backends. We believe that ddR will standardize distributed computing in R, just like the SQL interface has standardized how relational data is manipulated.

Graph analytics is becoming increasingly popular, with a number of new applications and systems developed in the past few years. In this paper, we study Vertica relational database as a platform for graph analytics. We show that vertex-centric graph analysis can be translated to SQL queries, typically involving table scans and joins, and that modern column-oriented databases are very well suited to running such queries. Furthermore, we show how developers can trade memory footprint for significantly reduced I/O costs in Vertica. We present an experimental evaluation of the Vertica relational database system on a variety of graph analytics, including iterative analysis, a combination of graph and relational analyses, and more complex 1-hop neighborhood graph analytics, showing that it is competitive to two popular vertex-centric graph analytics systems, namely Giraph and GraphLab.

A typical predictive analytics workflow will pre-process data in a database, transfer the resulting data to an external statistical tool such as R, create machine learning models in R, and then apply the model on newly arriving data. Today, this workflow is slow and cumbersome. Extracting data from databases, using ODBC connectors, can take hours on multi-gigabyte datasets. Building models on single-threaded R does not scale. Finally, it is nearly impossible to use R or other common tools, to apply models on terabytes of newly arriving data.

Adverse reactions to drugs are a major public health care issue. Currently, the Food and Drug Administration (FDA) publishes quarterly reports that typically contain on the order of 200,000 adverse incidents. In such numerous incidents, low frequency events that are clinically highly significant often remain undetected. In this paper, we introduce a visual analytics system to solve this problem using (1) high scalable interfaces for analyzing correlations between a number of complex variables (e.g., drug and reaction); (2) enhanced statistical computations and interactive relevance filters to quickly identify significant events including those with a low frequency; and (3) a tight integration of expert knowledge for detecting and validating adverse drug events. We applied these techniques to the FDA Adverse Event Reporting System and were able to identify important adverse drug events, such as the known association of the drug Avandia with myocardial infarction and Seroquel with diabetes mellitus, as well as low frequency events such as the association of Boniva with femur fracture. In our evaluation, we found over 90% of the adverse drug events that were published in the Institute for Safe Medication Practices (ISMP) reports from 2009 to 2012. In addition, our domain expert was able to identify some previously unknown adverse drug events.

Topic models have been widely used to discover latent topics in text documents. However, they may produce topics that are not interpretable for an application. Researchers have proposed to incorporate prior domain knowledge into topic models to help produce coherent topics. The knowledge used in existing models is typically domain dependent and assumed to be correct. However, one key weakness of this knowledge-based approach is that it requires the user to know the domain very well and to be able to provide knowledge suitable for the domain, which is not always the case because in most real-life applications, the user wants to find what they do not know. In this paper, we propose a framework to leverage the general knowledge in topic models. Such knowledge is domain independent. Specifically, we use one form of general knowledge, i.e., lexical semantic relations of words such as synonyms, antonyms and adjective attributes, to help produce more coherent topics. However, there is a major obstacle, i.e., a word can have multiple meanings/senses and each meaning often has a different set of synonyms and antonyms. Not every meaning is suitable or correct for a domain. Wrong knowledge can result in poor quality topics. To deal with wrong knowledge, we propose a new model, called GK-LDA, which is able to effectively exploit the knowledge of lexical relations in dictionaries. To the best of our knowledge, GK-LDA is the first such model that can incorporate the domain independent knowledge. Our experiments using online product reviews show that GK-LDA performs significantly better than existing state-of-the-art models.

In this paper, we propose a novel opinion summarization problem called compact explanatory opinion summarization (CEOS) which aims to extract within-sentence explanatory text segments from input opinionated texts to help users better understand the detailed reasons of sentiments. We propose and study general methods for identifying candidate boundaries and scoring the explanatoriness of text segments using Hidden Markov Models. We create new data sets and use a new evaluation measure to evaluate CEOS. Experimental results show that the proposed methods are effective for generating an explanatory opinion summary, outperforming a standard text summarization method.

Many applications require analyzing textual topics in conjunction with external time series variables such as stock prices. We develop a novel general text mining framework for discovering such causal topics from text. Our framework naturally combines any given probabilistic topic model with time-series causal analysis to discover topics that are both coherent semantically and correlated with time series data. We iteratively refine topics, increasing the correlation of discovered topics with the time series. Time series data provides feedback at each iteration by imposing prior distributions on parameters. Experimental results show that the proposed framework is effective.

Text analytics has become increasingly important with the rapid growth of text data. Particularly, information extraction (IE), which extracts structured data from text, has received significant attention. Unfortunately, IE is often computationally intensive. To address this issue, MapReduce has been used for large scale IE. Recently, there are emerging efforts from both academia and industry on pushing IE inside DBMSs. This leads to an interesting and important question: Given that both MapReduce and parallel DBMSs are for large scale analytics, which platform is a better choice for large scale IE? In this paper, we propose a benchmark to systematically study the performance of both platforms for large scale IE tasks. The benchmark includes both statistical learning based and rule based IE programs, which have been extensively used in real-world IE tasks. We show how to express these programs on both platforms and conduct experiments on real-world datasets. Our results show that parallel DBMSs is a viable alternative for large scale IE.

Aspect extraction is one of the key tasks in sentiment analysis.In recent years, statistical models have been used for the task.However, such models without any domain knowledge often produce aspects that are not interpretable in applications.To tackle the issue, some knowledge-based topic models have been proposed, which allow the user to input some prior domain knowledge to generate coherent aspects.However, existing knowledge-based topic models have several major shortcomings, e.g., little work has been done to incorporate the cannot-link type of knowledge or to automatically adjust the number of topics based on domain knowledge.This paper proposes a more advanced topic model, called MC-LDA (LDA with m-set and c-set), to address these problems, which is based on an Extended generalized Pólya urn (E-GPU) model (which is also proposed in this paper).Experiments on real-life product reviews from a variety of domains show that MC-LDA outperforms the existing state-of-the-art models markedly.

Aeolus is a prototype implementation of a topology optimizer on top of the distributed streaming system Storm. Aeolus extends Storm with a batching layer which can increase the topology's throughput by more than one order of magnitude. Furthermore, Aeolus implements an optimization algorithm that computes the optimal batch size and degree of parallelism for each node in the topology automatically. Even if Aeolus is built on top of Storm, the developed concepts are not limited to Storm and can be applied to any distributed intra-node-parallel streaming system. We propose to demo Aeolus using an interactive Web UI. One part of the Web UI is a topology builder allowing the user to interact with the system. Topologies can be created from scratch and their structure and/or parameters can be modified. Furthermore, the user is able to observe the impact of the changes on the optimization decisions and runtime behavior. Additionally, the Web UI gives a deep insight in the optimization process by visualizing it. The user can interactively step through the optimization process while the UI shows the optimizer's state, computations, and decisions. The Web UI is also able to monitor the execution of a non-optimized and optimized topology simultaneously showing the advantage of using Aeolus.

To enable the interactive exploration of large social media datasets we exploit the temporal distributions of word n-grams within the message stream to discover “interesting” concepts, determine “relatedness” between concepts, and find representative examples for display. We present a new algorithm for context-dependent “interestingness” using the coefficient of variation of the temporal distribution, apply the well-known technique of Pearson's Correlation to tweets using equi-height histogramming to determine correlation, and employ an asymmetric variant for computing “relatedness” to encourage exploration. We further introduce techniques using interestingness, correlation, and relatedness to automatically discover concepts and select preferred word N-grams for display. These techniques are demonstrated on an 800,000 tweet dataset from the Academy Awards.

To remain competitive, enterprises are evolving their business intelligence systems to provide dynamic, near realtime views of business activities. To enable this, they deploy complex workflows of analytic data flows that access multiple storage repositories and execution engines and that span the enterprise and even outside the enterprise. We call these multi-engine flows hybrid flows. Designing and optimizing hybrid flows is a challenging task. Managing a workload of hybrid flows is even more challenging since their execution engines are likely under different administrative domains and there is no single point of control. To address these needs, we present a Hybrid Flow Management System (HFMS). It is an independent software layer over a number of independent execution engines and storage repositories. It simplifies the design of analytic data flows and includes optimization and executor modules to produce optimized executable flows that can run across multiple execution engines. HFMS dispatches flows for execution and monitors their progress. To meet service level objectives for a workload, it may dynamically change a flow's execution plan to avoid processing bottlenecks in the computing infrastructure. We present the architecture of HFMS and describe its components. To demonstrate its potential benefit, we describe performance results for running sample batch workloads with and without HFMS. The ability to monitor multiple execution engines and to dynamically adjust plans enables HFMS to provide better service guarantees and better system utilization.

Opinionated social media such as product reviews are now widely used by individuals and organizations for their decision making. However, due to the reason of profit or fame, people try to game the system by opinion spamming (e.g., writing fake reviews) to promote or to demote some target products. In recent years, fake review detection has attracted significant attention from both the business and research communities. However, due to the difficulty of human labeling needed for supervised learning and evaluation, the problem remains to be highly challenging. This work proposes a novel angle to the problem by modeling spamicity as latent. An unsupervised model, called Author Spamicity Model (ASM), is proposed. It works in the Bayesian setting, which facilitates modeling spamicity of authors as latent and allows us to exploit various observed behavioral footprints of reviewers. The intuition is that opinion spammers have different behavioral distributions than non-spammers. This creates a distributional divergence between the latent population distributions of two clusters: spammers and non-spammers. Model inference results in learning the population distributions of the two clusters. Several extensions of ASM are also considered leveraging from different priors. Experiments on a real-life Amazon review dataset demonstrate the effectiveness of the proposed models which significantly outperform the state-of-the-art competitors.

We introduce a novel sentence ranking problem called explanatory sentence extraction (ESE) which aims to rank sentences in opinionated text based on their usefulness for helping users understand the detailed reasons of sentiments (i.e., "explanatoriness"). We propose and study several general methods for scoring the explanatoriness of a sentence. We create new data sets and propose a new measure for evaluation. Experiment results show that the proposed methods are effective, outperforming a state of the art sentence ranking method for standard text summarization.

Even though scripting languages like Pig allow for simpler coding, performing analytics over Big Data using Map-Reduce engines remains challenging. To further assist developers, and support novice users, we offer "The Farm", a catalog of scriptable services supporting creation, discovery, composition, and optimized execution. Each Pig script added to The Farm becomes an executable service, with inputs and outputs defined by relation schemas. Those services are discoverable using natural language search, and composable using a drag-and-drop interface. To support efficient execution, composed services are automatically merged to a single executable script, which can then be run by a growing selection of platform-specific optimizers and interpreters.

Since stream analytics is treated as a kind of cloud service, there exists a pressing need for its reliability and fault-tolerance. In a streaming process, the parallel and distributed tasks are chained in a graph-structure with each task transforming a stream to a new stream, the transaction property guarantees the streaming data, called tuples, to be processed in the order of their generation in every dataflow path, with each tuple processed once and only once. The failure recovery of a task allows the previously produced results to be corrected for eventual consistency, which is different from the instant consistency of global state enforced by the failure recovery of general distributed systems, and therefore presents new technical challenges. Transactional stream processing typically requires every task to checkpoint its execution state, and when it is restored from a failure, to have the last state recovered from the checkpoint and missing tuple re-acquired and processed. Currently there exist two kind approaches: one treats the whole process as a single transaction, and therefore suffers from the loss of intermediate results during failures, the other relies on the receipt of acknowledgement (ACK) to decide whether moving forward to emit the next resulting tuple or resending the current one after timeout, on the per-tuple basis, thus incurs extremely high latency penalty. In contradistinction to the above, we propose the backtrack mechanism for failure recovery, which allows a task to process tuples continuously without waiting for ACKs and without resending tuples in the failure-free case, but to request (ASK) the source tasks to resend the missing tuples only when it is restored from a failure which is a rare case thus has limited impact on the overall performance. We have implemented the proposed mechanisms on Fontainebleau, the distributed stream analytics infrastructure we developed on top of Storm. As a principle, we ensure all the transactional properties to be system supported and transparent to users. Our experience shows that the ASK-based recovery mechanism significantly outperforms the ACK-based one.

Topic modeling is popular for text mining tasks. Recently, topic modeling has been combined with time lines when textual data is related to external non-textual time series data such as stock prices. However, no previous work has used the external non-textual time series data in the process of topic modeling. In this paper, we describe a novel text mining system, Integrative Causal Topic Miner (InCaToMi) that integrates textual and non-textual time series data. InCaToMi automatically finds causal relationships and topics using text data and external non-textual time series data using Granger Testing. Moreover, InCaToMi considers the non-textual time series data in the topic modeling process, using the time series data to iteratively improve modeling results through interactions between it and the textual data at both topic and word levels.

The rapid proliferation of online forums has made it possible for people to share their intentions, wishes and experiences by posting comments with the aim of getting advice from other members of the forum. Extracting intentions from these comments provides valuable insight for companies who can exploit it to get a competitive edge. However, given the very large amount of this kind of online comments, manually extracting intentions is impractical, time consuming and expensive. Companies need tools that analyze the text to extract intentions and details about them. In this paper we propose to demo one such tool called Intention Insider which has been developed at HP Labs in close collaboration with business units and a few selected customers. The tool can ingest content from online forums or from uploaded files and quickly sift through very large amounts of comments to extract intention information. This information is loaded into a data warehouse to be correlated with other structured data and queried to produce interactive reports and dynamic visualizations that facilitate its exploration at detailed and aggregate levels.

The current generation of stream processing systems is in general built separately from the query engine thus lacks the expressive power of SQL and causes significant overhead in data access and movement. This situation has motivated us to leverage the query engine for stream processing.

Mobile applications, such as those on WebOS, increasingly depend on continuous analytics results of real-time events, for monitoring oil & gas production, watching traffic status and detecting accident, etc, which has given rise to the need of providing Continuous analytics as a Service (CaaaS). While representing a paradigm shift in cloud computing, CaaaS poses several challenges in scalability, latency, time-window semantics, transaction control and result-set staging. A data stream is infinite thus can only be analyzed in granules. We propose a continuous query model over both static relations and dynamic streaming data, which allows a long-standing SQL query instance to run cycle by cycle, each cycle for a chunk of data from the data stream, using a cut-and-rewind mechanism. We further support the cycle-based transaction model with cyclebased isolation and visibility, for delivering analytics results to the clients continuously while the query is running. To have the continuously generated analytics results staged efficiently, we developed the table-ring and label switching mechanism characterized by staging data through metadata manipulation without physical data moving and copying. To scale-out analytics computation, we support both parallel database based and network distributed Map-Reduce based infrastructure with multiple cooperating engines. We have built the proposed infrastructure by extending the PostgreSQL engine. We tested the throughput and latency of this service based on a well-known stream processing benchmark; the results show that the proposed approach is highly competitive. Our experiments indicate that the database technology can be extended and applied to real-time continuous analytics service provisioning.

To achieve scalable data intensive analytics, we investigate methods to integrate general purpose analytic computation into a query pipeline using User Defined Functions (UDFs). However, an existing UDF cannot act as a block operator with chunk-wise input along the tuple-wise query processing pipeline, therefore unable to deal with the application semantics definable on the set of incoming tuples representing a single object or falling in a time window, and unable to leverage external computation engines for efficient batch processing.

The rise of Web 2.0 with its increasingly popular social sites like Twitter, Facebook, blogs and review sites has motivated people to express their opinions publicly and more frequently than ever before. This has fueled the emerging field known as sentiment analysis whose goal is to translate the vagaries of human emotion into hard data. LCI is a social channel analysis platform that taps into what is being said to understand the sentiment with the particular ability of doing so in near real-time. LCI integrates novel algorithms for sentiment analysis and a configurable dashboard with different kinds of charts including dynamic ones that change as new data is ingested. LCI has been researched and prototyped at HP Labs in close interaction with the Business Intelligence Solutions (BIS) Division and a few customers. This paper presents an overview of the architecture and some of its key components and algorithms, focusing in particular on how LCI deals with Twitter and illustrating its capabilities with selected use cases.

While parallel DBMSs do support large scale parallel query processing on partitioned data, the reach of more general applications relies on User Defined Functions (UDFs). However, the existent UDF technology is insufficient both conceptually and practically. A UDF is not a relation-in, relation-out operator, which restricts its ability to model complex applications defined on a set of tuples rather than on a single one, and to be composed with other relational operators in a query. Further, to interact with the query execution efficiently, a UDF must be coded with complex interactions with DBMS internal data structures and system calls which is often beyond the expertise of an analytics application developer.

Video analytics is a data-intensive and knowledge-rich computation chain from collected video frames to high-level scene and behavior descriptions. The platform separation of video storage and video analysis, as it is now, has become the major bottleneck for scalability, efficiency and effectiveness of video analysis. We solve this problem by (a) completely pushing down video analysis computation to the database engine for fast data access and reduced data transfer; (b) systematically managing domain knowledge and context information, and consistently applying them to video analysis; (c) combining multilevel, multidimensional analytics with data loading for "just-in-time" meta-data materialization; (d) supporting analytical data streaming by database engine, towards a new paradigm for Operational Business Intelligence (OpBI). An OpBI system integrates the management of data, knowledge and analytics programs, along the canonical "eco-chain" of information abstraction, derivation, induction, and feedback.

Sequential pattern mining is an important data mining problem with broad applications. However, it is also a difficult problem since the mining may have to generate or examine a combinatorially explosive number of intermediate subsequences. Most of the previously developed sequential pattern mining methods, such as GSP, explore a candidate generation-and-test approach [R. Agrawal et al. (1994)] to reduce the number of candidates to be examined. However, this approach may not be efficient in mining large sequence databases having numerous patterns and/or long patterns. In this paper, we propose a projection-based, sequential pattern-growth approach for efficient mining of sequential patterns. In this approach, a sequence database is recursively projected into a set of smaller projected databases, and sequential patterns are grown in each projected database by exploring only locally frequent fragments. Based on an initial study of the pattern growth-based sequential pattern mining, FreeSpan [J. Han et al. (2000)], we propose a more efficient method, called PSP, which offers ordered growth and reduced projected databases. To further improve the performance, a pseudoprojection technique is developed in PrefixSpan. A comprehensive performance study shows that PrefixSpan, in most cases, outperforms the a priori-based algorithm GSP, FreeSpan, and SPADE [M. Zaki, (2001)] (a sequential pattern mining algorithm that adopts vertical data format), and PrefixSpan integrated with pseudoprojection is the fastest among all the tested algorithms. Furthermore, this mining methodology can be extended to mining sequential patterns with user-specified constraints. The high promise of the pattern-growth approach may lead to its further extension toward efficient mining of other kinds of frequent patterns, such as frequent substructures.

Effectively managing security policies in a large distributed Web Services environment is the key to secure e-business transactions. Security policy must ensure the end-to-end agreement for many-to-many interoperation; ensure the versioning interoperability and privacy of collaborating partners; and ensure the dynamic establishment of security policies because any statically defined security policy tends to be unsecured after a certain period of time. The traditional security policy configuration mechanisms, either the local configuration mechanism or the centralized configuration mechanism, cannot fully meet the above requirements. In this paper we describe a solution for managing security policies in a collaborative Web Services environment. This solution is based on ebXML CPP/CPA model and uses Interoperability Contract Document (ICD). It allows the collaboration parties to establish security policy dynamically for each individual interoperation; makes the selected policy confidential; and addresses the software, message, and policy versioning and interoperability issues. Our experience reveals the advantages of this approach over others.

To enable intra- and inter-enterprise application integration, enterprises have invested heavily in EAI (Enterprise Application Integration) and B2B (Business to Business) technologies. However, the first generation B2B technologies, represented by the Marketplace platform and its associated tools and applications offered in the mid to late 1990s, have left much to be desired. Recent momentum in Web Services based on the SOAP, WSDL, and UDDI specifications promises a standardized connectivity at a lower cost that would transform the business connectivity paradigm. In this talk, we will provide an anatomy and diagnosis of the B2B technologies. We will also analyze the current Web service specifications and technologies from the perspectives of protocol layers, service descriptions, and business service registries. We will describe the problems that must be solved in order for Web services to evolve from its simplistic form today to enable the vision of dynamic business process integration within and across enterprise boundaries.

Conventional workflow systems are primarily designed for intra-enterprise process management, and they are hardly used to handle processes with tasks and data separated by enterprise boundaries, for reasons such as security, privacy, sharability, firewalls, etc. Further, the cooperation of multiple enterprises is often based on peer-to-peer interactions rather than centralized coordination. As a result, the conventional centralized process management architecture does not fit into the picture of inter-enterprise business-to-business e-commerce. We have developed a Collaborative Process Manager (CPM) to support decentralized, peer-to-peer process management for inter-enterprise collaboration at the business process level. A collaborative process is not handled by a centralized workflow engine, but by multiple CPMs, each representing a player in the business process. Each CPM is used to schedule, dispatch and control the tasks of the process that the player is responsible for, and the CPMs interoperate through an inter-CPM messaging protocol. We have implemented CPM and embedded it into a dynamic software agent architecture, E-Carry, that we developed at HP Labs, to elevate multi-agent cooperation from the conversation level to the process level for mediating e-commerce applications.

Sequential pattern mining is an important data mining problem with broad applications. It is challenging since one may need to examine a combinatorially explosive number of possible subsequence patterns. Most of the previously developed sequential pattern mining methods follow the methodology of \t which may substantially reduce the number of combinations to be examined. However, \t still encounters problems when a sequence database is large and/or when sequential patterns to be mined are numerous and/or long. In this paper, we propose a novel sequential pattern mining method, called PrefixSpan (i.e., Prefix-projected Sequential pattern mining), which explores prefixprojection in sequential pattern mining. PrefixSpan mines the complete set of patterns but greatly reduces the efforts of candidate subsequence generation. Moreover, prefix-projection substantially reduces the size of projected databases and leads to efficient processing. Our performance study shows that PrefixSpan outperforms both the -based GSP algorithm and another recently proposed method, FreeSpan, in mining large sequence databases. 1

Using agent technology to support e-commerce automation is a promising direction. However, previous "proof-of-concept" efforts do not scale well in e-commerce automation. An essential reason is that the conventional agent infrastructures are primarily designed for intra-enterprise, group-based agent cooperation, but most e-commerce applications are based on inter-enterprise business partnership. Agents across enterprise boundaries are unlikely to be organized into the same "agent group" and under a centralized coordination. We tackle the issue of scaling inter-enterprise agent cooperation from the following three angles. First, we have introduced the point of presence (POP) approach for integrating message-based agent communication with interface-based service invocation. This approach allows us to unify the messaging service interface for all the agents, and therefore greatly simplify both server-side and client-side interface implementation and maintenance. Next, we have developed the agent-embedded cooperative process manager, for elevating multi-agent cooperation from the conversation level to the business process level, and from centralized process management to peer-to-peer cooperative process management. These emerging technologies are integrated with the E-Carry agent infrastructure, an autonomous and decentralized system we developed at HP Labs. The feasibility of this approach have been demonstrated in a prototyping system.

In a telecommunication network, hundreds of millions of call detail records (CDRs) are generated daily. Applications such as tandem traffic analysis require the collection and mining of CDRs on a continuous basis. The data volumes and data flow rates pose serious scalability and performance challenges. This has motivated us to develop a scalable data-warehouse/OLAP framework, and based on this framework, tackle the issue of scaling the whole operation chain, including data cleansing, loading, maintenance, access and analysis. We introduce the notion of dynamic data warehousing for managing information at different aggregation levels with different life spans. We use OLAP servers, together with the associated multidimensional databases, as a computation platform for data caching, reduction and aggregation, in addition to data analysis. The framework supports parallel computation for scaling up data mining, and supports incremental OLAP for providing continuous data mining. A tandem traffic analysis engine is implemented on the proposed framework. In addition to the parallel and incremental computation architecture, we provide a set of application-specific optimization mechanisms for scaling performance. These mechanisms fit well into the above framework. Our experience demonstrates the practical value of the above framework in supporting an important class of telecommunication business intelligence applications.

Article FreeSpan: frequent pattern-projected sequential pattern mining Share on Authors: Jiawei Han Intelligent Database Systems Research Lab. School of Computing Science, Simon Fraser University, Burnaby, B.C., Canada V5A 1S6 Intelligent Database Systems Research Lab. School of Computing Science, Simon Fraser University, Burnaby, B.C., Canada V5A 1S6View Profile , Jian Pei Intelligent Database Systems Research Lab. School of Computing Science, Simon Fraser University, Burnaby, B.C., Canada V5A 1S6 Intelligent Database Systems Research Lab. School of Computing Science, Simon Fraser University, Burnaby, B.C., Canada V5A 1S6View Profile , Behzad Mortazavi-Asl Intelligent Database Systems Research Lab. School of Computing Science, Simon Fraser University, Burnaby, B.C., Canada V5A 1S6 Intelligent Database Systems Research Lab. School of Computing Science, Simon Fraser University, Burnaby, B.C., Canada V5A 1S6View Profile , Qiming Chen Hewlett-Packard Labs. 1501 Page Mills Road, P.O. Box 10490, Palo Alto, California Hewlett-Packard Labs. 1501 Page Mills Road, P.O. Box 10490, Palo Alto, CaliforniaView Profile , Umeshwar Dayal Hewlett-Packard Labs. 1501 Page Mills Road, P.O. Box 10490, Palo Alto, California Hewlett-Packard Labs. 1501 Page Mills Road, P.O. Box 10490, Palo Alto, CaliforniaView Profile , Mei-Chun Hsu Hewlett-Packard Labs. 1501 Page Mills Road, P.O. Box 10490, Palo Alto, California Hewlett-Packard Labs. 1501 Page Mills Road, P.O. Box 10490, Palo Alto, CaliforniaView Profile Authors Info & Claims KDD '00: Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data miningAugust 2000 Pages 355–359https://doi.org/10.1145/347090.347167Online:01 August 2000Publication History 503citation3,103DownloadsMetricsTotal Citations503Total Downloads3,103Last 12 Months105Last 6 weeks11 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

Warehousing and mining sales transaction data to generate summary information, customer profiles, and business rules has become increasingly important in e-commerce. Such summary information and rules have to be extracted from very large collections of transaction data gathered at many distributed sites. This is challenging data mining, both in terms of the magnitude of data involved, and the need to incrementally adapt the mined patterns and rules as new data is collected. This paper describes a distributed and cooperative data warehousing, OLAP, and data mining infrastructure that addresses these challenges. Our contributions are as follows. First, we define various new classes of multidimensional and multi-level association rules (scoped multidimensional, with conjoint items, and functional) that can be extracted from customer profiles and are used for e-commerce applications. Then, we show how customer profiles and different classes of association rules can be computed in a distributed, cooperative manner using OLAP tools. Finally, we show how the summaries, profiles, and rules can be incrementally updated as new transaction data is collected. This infrastructure has been prototyped at HP Labs.

We claim that a dynamic agent infrastructure can provide a shift from static distributed computing to dynamic distributed computing, and we have developed an infrastructure to realize such a shift. We shall compare this infrastructure with other distributed computing infrastructures such as CORBA and DCOM, and demonstrate its value in highly dynamic system integration, service provisioning and distributed applications such as data mining on the Web. The infrastructure is Java-based, light-weight, and extensible. It differs from other agent platforms and client/server infrastructures in its support of dynamic behavior modification of agents. A dynamic agent is not designed to have a fixed set of predefined functions, but instead, to carry application-specific actions, which can be loaded and modified on the fly. This allows a dynamic agent to adjust its capability to accommodate changes in the environment and requirements, and play different roles across multiple applications. The above features are supported by the light-weight, built-in management facilities of dynamic agents, which can be commonly used by the "carried" application programs to communicate, manage resources and modify their problem-solving capabilities. Therefore, the proposed infrastructure allows application-specific multi-agent systems to be developed easily on top of it, provides "nuts and bolts" for run-time system integration, and supports dynamic service construction, modification and movement. A prototype has been developed at HP Labs and made available to several external research groups.

We claim that a dynamic-agent infrastructure can provide a shift from static distributed computing to dynamic distributed computing, and we have developed such an infrastructure to realize such a shift. We shall show its impact on software engineering through a comparison with other distributed object-oriented systems such as CORBA and DCOM, and demonstrate its value in highly dynamic system integration and service provisioning. The infrastructure is Java-based, light-weight, and extensible. It differs from other agent platforms and client/server infrastructures in its support of dynamic behavior modification of agents. A dynamic-agent is not designed to have a fixed set of predefined functions but instead, to carry application-specific actions, which can be loaded and modified on theory. This allows a dynamic-agent to adjust its capability for accommodating environment and requirement changes, and play different roles across multiple applications. The above features are supported by the light-weight, built-in management facilities of dynamic-agents, which can be commonly used by the "carried" application programs to communicate, manage resources and modify their problem solving capabilities. Therefore, the proposed infrastructure allows application-specific multi-agent systems to be developed easily on top of it, provides "nuts and bolts" for run-time system integration, and supports dynamic service construction, modification and movement. A prototype has been developed at HP Labs and made available to several external research groups.

In a 1976 book, “Algorithms + Data Structures = Programs” [15], Niklaus Wirth defined programs to be algorithms and data structures. Of course, by now we know that man does not live from programs alone, and that there is a second fundamental computer science equation: “Programs + Databases = Information Systems.”

We study a deadlock-free locking-based concurrency control algorithm, called cautious waiting , which allows for a limited form of waiting. The algorithm is very simple to implement. We present an analytical solution to its performance evaluation based on the mean-value approach proposed by Tay et al. [18]. From the modeling point of view, we are able to do away with a major assumption used in Tay's previous work, and therefore capture more accurately both the restart and the blocking rates in the system. We show that to solve for this model we only need to solve for the root of a polynomial. The analytical tools developed enable us to see that the cautious waiting algorithm manages to achieve a delicate balance between restart and blocking, and therefore is superior (i.e., has higher throughput to both the no-waiting (i.e., immediate restart) and the general waiting algorithms under a wide range of system parameters. The study substantiates the argument that balancing restart and blocking is important in locking systems.

An alternative approach to distributed transaction processing based on the unilateral commit paradigm (UCP) and on persistent transmission is proposed. Instead of executing a unit of work as a single distributed transaction, as in the traditional transaction execution paradigm, opportunities are looked for to execute it as a structured set or a sequence of smaller, possibly single-site atomic transactions. Each such transaction, once executed, is committed independently of other transactions in the task. A method for rigorously maintaining the linkage between the steps is provided for by a persistent transmission mechanism. It is argued that UCP is especially attractive since it relies on a site's ability to execute conventional flat local transactions and does not require additional capabilities such as the ability to execute nested transactions.>

The problem of system failure and recovery of distributed shared virtual memory (DSVM) is studied. Most DSVM systems use the notion of tokens to indicate a site's access rights on the data pages it caches, and a locating scheme to get to the most up-to-date version of a data page. The problem is to recovery this token directory after a site has failed. The authors' solution is to treat the token directory at each site as a fragment of a global token database and the page migration activities as token transactions that update this distributed database. By the use of the unilateral commit protocol for token transactions, fast recovery of the token state at minimal run-time overhead of token transaction execution is achieved.>

A distributed memory hierarchy (DMH) is a memory system consisting of storage modules distributed over a high-bandwidth local area network. It provides for transaction applications an abstraction of single virtual memory space to which shared data are mapped. As in a conventional memory hierarchy (MH) in a single-machine system, a DMH is responsible for locating, migrating, and caching data pages; however, unlike a conventional MH, a DMH must do so across the storage modules in a network. In addition, a DMH must handle the problem of propagation of transaction updates preserving serializability of transactions. The performance of a DMH system is strongly influenced by concurrency control and update propagation. It is also crucial that performance analysis accounts for memory resources and network requirements. A DMH system is presented, the tradeoffs between conservative and aggressive update propagation strategies are defined, and promising new strategies are identified.>

Executing a transaction in a conventional distributed database system involves the execution of several subtransactions, each at a remote site where the data reside and running a two-phase commit protocol at the end of the transaction. With the advent of fast communication networks, we consider an alternative paradigm where the remote data being accessed are dynamically migrated to the initiation site of the transaction. One example of such a system is a distributed shared virtual memory system.

Transactions have been rigorously defined and extensively studied in the database and transaction processing literature, but little has been said about the handling of the requests for transaction execution in commercial TP systems, especially distributed ones, managing the flow of requests is often as important as executing the transactions themselves.

This paper addresses the problem of organising and controlling activities that involve multiple steps of processing and that typically are of long duration. We explore the use of triggers and transactions to specify and organize such long-running activities. Triggers offer data- or event-driven specification of control flow, and thus provide a flexible and modular framework with which the control structures of the activities can be extended or modified. We describe a model based on event-condition-action rules and coupling modes. The execution of these rules is governed by an extended nested transaction model. Through a detailed example, we illustrate the utility of the various features of the model for chaining related steps without sacrificing concurrency, for enforcing integrity constraints, and for providing flexible failure and exception handling.

Synchronization in DSVM (distributed shared virtual memory) can be approached top-down by first understanding the synchronization needs at the process level instead of only at the memory access level. The authors demonstrate this idea in the context of transaction synchronization, devising two-phase locking-based algorithms under two DSVM scenarios: with and without an underlying memory coherence system. They compare the performances of the two algorithms and argue that significant performance gain can potentially result from bypassing memory coherence and supporting process synchronization directly on distributed memory. They also study the role of the optimistic algorithms in transaction synchronization in DSVM and show that some optimistic policy appears promising under the scenarios studied.>

A framework is presented for analysis of time-critical scheduling algorithms. The main assumptions are analyzed behind real-time scheduling and concurrency control algorithms, and a unified approach is proposed. Two main classes of schedulers are identified according to the availability of information about resource requirements and execution times: conflict-resolving schedulers resolve conflicts at run-time, and hence can only produce a sequence of operations satisfying task priorities and resource constraints; and conflict-avoiding schedulers determine resource requirements and expected execution times through offline transaction-class preanalysis and produce a complete time-critical schedule satisfying both timing and resource constraints. For the latter case, the resolution of overload is essential. Examples are given to illustrate the framework and the main classes of scheduling algorithms.>

Summary form only given. The issue of ease of using shared data in a data-intensive parallel computing environment is discussed. An approach is investigated for transparently supporting data sharing in a loosely coupled parallel computing environment, where a moderate to a large number of individual computing elements are connected via a high-bandwidth network without necessarily physically sharing memory. A system called VOYAGER is discussed which serves as the underlying system facility that supervises the distributed shared virtual memory. VOYAGER allows shared-data parallel applications to take advantage of parallel and distributed processing with relative ease. The application program merely maps the shared data onto its virtual address space replicates itself on distributed machines and spawns appropriate execution threads; the threads would automatically be given coordinated access to the shared data distributed in the network. Multiple computation threads migrate and populate the processors of a number of computing elements, making use of the multiple processors to achieve a high degree of parallelism. The low-level resource management chores are made available once and for all in the underlying facility VOYAGER, usable by many different data-intensive applications.>

In a large integrated database, there often exists an “information hierarchy,” where both raw data and derived data are stored and used together. Therefore, among update transactions, there will often be some that perform only read accesses from a certain (i.e., the “raw” data) portion of the database and write into another (i.e., the “derived” data) portion. A conventional concurrency control algorithm would have treated such transactions as regular update transactions and subjected them to the usual protocols for synchronizing update transactions. In this paper such transactions are examined more closely. The purpose is to devise concurrency control methods that allow the computation of derived information to proceed without interfering with the updating of raw data. The first part of the paper presents a proof method for correctness of concurrency control algorithms in a hierarchically decomposed database. The proof method provides a framework for understanding the intricacies in dealing with hierarchically decomposed databases. The second part of the paper is an application of the proof method to show the correctness of a two-phase-locking- based algorithm, called partitioned two-phase locking, for hierarchically decomposed databases. This algorithm is a natural extension to the Version Pool method proposed previously in the literature.

The classical approaches to enforcing serializability are the two-phase locking technique and the timestamp ondering technique. Either approach requires that a read operation from a transaction be negistered (in the form of either a read timestamp or a read lock), so that a write operation from a concurrent transaction will not interfere improperly with the read operation. However, setting a lock or leaving a timestamp with a data element is an expensive operation. The purpose of the current research is to seek ways to reduce the overhead of synchronizing certain types of read accesses while achieving the goal of serializability.To this end, a new technique of concurrency control for database management systems has been proposed. The technique makes use of a hierarchical database decomposition, a procedure which decomposes the entire database into data segments based on the access pattern of the update transactions to be run in the system. A corresponding classification of the update transactions is derived where each transaction class is 'rooted' in one of the data segments. The technique requires a timestamp ordering protocol be observed for acesses within an update transaction's own root segment, but enables read accesses to other data segments to proceed without ever having to wait or to leave any trace of these accesses, thereby reducing the overhead of concurrency control. An algorithm for handling ad-hoc read-only transactions in this environment is also devised, which does not require read-only transactions to wait or set any read timestamp.