In the Princeton WordNet Gloss Corpus, the word forms from the definitions ("glosses") in WordNet's synsets are manually linked to the context-appropriate sense in the WordNet.The glosses then become a sense-disambiguated corpus annotated against WordNet version 3.0.The result is also called a semantic concordance, which can be seen as both a lexicon (WordNet extension) and an annotated corpus.In this work we motivate and present the initial steps to complete the annotation of all openclass words in this corpus.Finally, we introduce a freely-available annotation interface built as an Emacs extension, and evaluate a preliminary annotation effort.

SUMMARY This work presents an extensive case study on the model‐based design of a commercial‐grade stream processing middleware (IBM's InfoSphere Streams) its runtime and language (SPL) compiler. The model‐based underpinnings are pervasive throughout the whole environment, from describing inter‐process communication interfaces and objects to the design of the extensibility mechanism in the runtime and language. In addition to many software engineering advantages such as consistent, uniform, and self‐documented integration among the different parts of the system, we show intrinsic performance benefits to the platform derived from this design approach. First, we demonstrate how an incremental compilation strategy employed by theSPLcompiler and rooted on the model description of the application, extracted by the compiler as part of the application building process, leads to better compile‐time performance. Second, we discuss how the model‐based code generation strategy employed by theSPLcompiler also leads to increased runtime performance, by specializing the generated code to particular characteristics of the runtime environment. Finally, we show how the extensibility strategy used in theSPLlanguage leads to automatic syntactic and semantic checks at compile time, while enabling behavioral reasoning and specific optimizations at runtime. Copyright © 2011 John Wiley & Sons, Ltd.

SUMMARY A stock market data processing system that can handle high data volumes at low latencies is critical to market makers. Such systems play a critical role in algorithmic trading, risk analysis, market surveillance, and many other related areas. The current systems tend to use specialized software and custom processors. We show that such a system can be built with general‐purpose middleware and run on commodity hardware. The middleware we use is IBM System S which includes transport technology from IBM WebSphere MQ Low Latency Messaging (LLM). Our performance evaluation consists of two parts. First, we determined the effectiveness of each system optimization that the hardware and software infrastructure makes available. These optimizations were implemented at all software levels—application, middleware, and operating system. Second, we evaluated our system on different hardware platforms. Copyright © 2011 John Wiley & Sons, Ltd.

This paper describes a modeling framework for evaluating the impact of faults on the output of streaming applications. Our model is based on three abstractions: stream operators, stream connections, and tuples. By composing these abstractions within a Stochastic Activity Network, we allow the modeling of complete applications. We consider faults that lead to data loss and to silent data corruption (SDC). Our framework captures how faults originating in one operator propagate to other operators down the stream processing graph. We demonstrate the extensibility of our framework by evaluating three different fault tolerance techniques: checkpointing, partial graph replication, and full graph replication. We show that under crashes that lead to data loss, partial graph replication has a great advantage in maintaining the accuracy of the application output when compared to checkpointing. We also show that SDC can break the no data duplication guarantees of a full graph replication-based fault tolerance technique.

MapReduce and stream processing are two emerging, but different, paradigms for analyzing, processing and making sense of large volumes of modern day data. While MapReduce offers the capability to analyze several terabytes of stored data, stream processing solutions offer the ability to process, possibly, a few million updates every second. However, there is an increasing number of data processing applications which need a solution that effectively and efficiently combines the benefits of MapReduce and stream processing to address their data processing needs. For example, in the automated stock trading domain, applications usually require periodic analysis of large amounts of stored data to generate a model using MapReduce, which is then used to process a stream of incident updates using a stream processing system. This paper presents Deduce, which extends IBM's System S stream processing middleware with support for MapReduce by providing (1) language and runtime support for easily specifying and embedding MapReduce jobs as elements of a larger data-flow, (2) capability to describe reusable modules that can be used as map and reduce tasks, and (3) configuration parameters that can be tweaked to control and manage the usage of shared resources by the MapReduce and stream processing components. We describe the motivation for Deduce and the design and implementation of the MapReduce extensions for System S, and then present experimental results.

The emergence of large-field radio telescopes has generated the need to process huge amounts of data “on the fly” in order to avoid substantial costs in storage and signal processing. In this paper, we describe a streaming software approach to radio astronomy, and in particular, show how the IBM-developed stream computing architecture System S enables seamless “on the fly” radio astronomy imaging. This approach overcomes pertinent issues of memory limitation and latencies related to data processing, and it allows autonomous processor allocation to tasks as the need arises.

Applications from several domains are now being written to process live data originating from hardware and software-based streaming sources. Many of these applications have been written relying solely on database and data warehouse technologies, despite their lack of need for transactional support and ACID properties. In several extreme high-load cases, this approach does not scale to the processing speeds that these applications demand. In this paper we demonstrate an application acceleration approach whereby a regular ODBC-based application is converted into a true streaming application with minimal disruption from a software engineering standpoint. We showcase our approach on three real-world applications. We experimentally demonstrate the substantial performance improvements that can be observed when contrasting the accelerated implementation with the original database-oriented implementation.

Abstract Stream processing applications are used to ingest, process, and analyze continuous data streams from heterogeneous sources of live and stored data, generating streams of output results. These applications are, in many cases, complex, large‐scale, low‐latency, and distributed in nature. In this paper, we describe the design principles and architectural underpinnings for stream processing applications. These principles are distilled from our experience in building real‐world applications both for internal use as well as with customers from several industrial and academic domains. We provide principles, guidelines, as well as appropriate implementation examples to highlight the different aspects of stream processing application design and development. Copyright © 2010 John Wiley & Sons, Ltd.

We present a code-generation-based optimization approach to bringing performance and scalability to distributed stream processing applications. We express stream processing applications using an operator-based, stream-centric language called SPADE, which supports composing distributed data flow graphs out of toolkits of type-generic operators. A major challenge in building such applications is to find an effective and flexible way of mapping the logical graph of operators into a physical one that can be deployed on a set of distributed nodes. This involves finding how best operators map to processes and how best processes map to computing nodes. In this paper, we take a two-stage optimization approach, where an instrumented version of the application is first generated by the SPADE compiler to profile and collect statistics about the processing and communication characteristics of the operators within the application. In the second stage, the profiling information is fed to an optimizer to come up with a physical data flow graph that is deployable across nodes in a computing cluster. This approach not only creates highly optimized applications that are tailored to the underlying computing and networking infrastructure, but also makes it possible to re-target the application to a different hardware setup by simply repeating the optimization step and re-compiling the application to match the physical flow graph produced by the optimizer. Using real-world applications, from diverse domains such as finance and radio-astronomy, we demonstrate the effectiveness of our approach on System S -- a large-scale, distributed stream processing platform.

Many streaming applications demand continuous processing of live data with little or no downtime, therefore, making high-availability a crucial operational requirement. Fault tolerance techniques are generally expensive and when directly applied to streaming systems with stringent throughput and latency requirements, they might incur a prohibitive performance overhead. This paper describes a flexible, light-weight fault tolerance solution in the context of the SPADE language and the System S distributed stream processing engine. We devised language extensions so users can define and parameterize check-point policies easily. This configurable fault tolerance solution is implemented through code generation in SPADE, which reduces the overall application fault tolerance costs by incurring them only for the parts of the application that require it. In this paper we focus on the overall design of our checkpoint mechanism and we also describe an incremental checkpointing algorithm that is suitable for on-the-fly processing of high-rate data streams.

High performance stream processing is critical in sense-and-respond application domains – from environmental monitoring to algorithmic trading. In this paper, we focus on language and runtime support for improving the performance of sense-and-respond applications in processing data from high rate streams. The central tenet of this work is the definition of a streaming architectural pattern for these application domains and the programming model and the code generation framework to support it. Using IBM Research's System S middleware and the SPADE language, we demonstrate how to scale up a financial trading application.

We describe language- and code generation-based approaches to providing access to architecture-specific vectorization support for high-performance data stream processing applications. We provide an experimental performance evaluation of several stream operators, contrasting our code generation approach with the native auto-vectorization support available in the GNU gcc and Intel icc compilers.

We describe an approach to elastically scale the performance of a data analytics operator that is part of a streaming application. Our techniques focus on dynamically adjusting the amount of computation an operator can carry out in response to changes in incoming workload and the availability of processing cycles. We show that our elastic approach is beneficial in light of the dynamic aspects of streaming workloads and stream processing environments. Addressing another recent trend, we show the importance of our approach as a means to providing computational elasticity in multicore processor-based environments such that operators can automatically find their best operating point. Finally, we present experiments driven by synthetic workloads, showing the space where the optimizing efforts are most beneficial and a radioastronomy imaging application, where we observe substantial improvements in its performance-critical section.

Abstract Distributed data stream processing applications are often characterized by data flow graphs consisting of a large number of built‐in and user‐defined operators connected via streams. These flow graphs are typically deployed on a large set of nodes. The data processing is carried out on‐the‐fly, as tuples arrive at possibly very high rates, with minimum latency. It is well known that developing and debugging distributed, multi‐threaded, and asynchronous applications, such as stream processing applications, can be challenging. Thus, without domain‐specific debugging support, developers struggle when debugging distributed applications. In this paper, we describe tools and language support to support debugging distributed stream processing applications. Our key insight is to view debugging of stream processing applications from four different, but related, perspectives. First, debugging the semantics of the application involves verifying the operator‐level composition and inspecting the flows at the logical level. Second, debugging the user‐defined operators involves traditional source‐code debugging, but strongly tied to the stream‐level interactions. Third, debugging the deployment details of the application require understanding the runtime physical layout and configuration of the application. Fourth, debugging the performance of the application requires inspecting various performance metrics (such as communication rates, CPU utilization, etc.) associated with streams, operators, and nodes in the system. In light of this characterization, we developed several tools such as adebugger‐awarecompiler and an associatedstream debugger,composition and deployment visualizers, andperformance visualizers, as well as language support, such as configuration knobs for logging and tracing, deployment configurations such as operator‐to‐process and process‐to‐node mappings, monitoring directives to inspect streams, and special sink adapters to intercept and dump streaming data to files and sockets, to name a few. We describe these tools in the context ofSpade—a language for creating distributed stream processing applications, andSystem S—a distributed stream processing middleware under development at the IBM Watson Research Center. Published in 2009 by John Wiley & Sons, Ltd.

In this paper, we present Spade - the System S declarative stream processing engine. System S is a large-scale, distributed data stream processing middleware under development at IBM T. J. Watson Research Center. As a front-end for rapid application development for System S, Spade provides (1) an intermediate language for flexible composition of parallel and distributed data-flow graphs, (2) a toolkit of type-generic, built-in stream processing operators, that support scalar as well as vectorized processing and can seamlessly inter-operate with user-defined operators, and (3) a rich set of stream adapters to ingest/publish data from/to outside sources. More importantly, Spade automatically brings performance optimization and scalability to System S applications. To that end, Spade employs a code generation framework to create highly-optimized applications that run natively on the Stream Processing Core (SPC), the execution and communication substrate of System S, and take full advantage of other System S services. Spade allows developers to construct their applications with fine granular stream operators without worrying about the performance implications that might exist, even in a distributed system. Spade's optimizing compiler automatically maps applications into appropriately sized execution units in order to minimize communication overhead, while at the same time exploiting available parallelism. By virtue of the scalability of the System S runtime and Spade's effective code generation and optimization, we can scale applications to a large number of nodes. Currently, we can run Spade jobs on ≈ 500 processors within more than 100 physical nodes in a tightly connected cluster environment. Spade has been in use at IBM Research to create real-world streaming applications, ranging from monitoring financial market feeds to radio telescopes to semiconductor fabrication lines.

We consider a virtual computing environment that provides computational resources on demand to users with multi attribute task descriptions that include a valuation, resource (CPU) needs and a completion deadline. Achieving a high quality of service in this environment depends on finding a balance between processing high priority tasks before their deadlines expire, while maximizing resource utilization. The problem becomes more challenging in an economic setting, where the task valuation is private. We propose a bid-based server that publishes a history of the success rate table (SRT) for processed tasks. Clients use the history to optimize their bid for resources on a (single) multiprocessor server. The server schedules tasks in descending order of their bid- Highest Bid First (HBF) and backfills the schedule with smaller tasks when resources are still available. The scheduler follows a hard deadline model where tasks cannot be processed after their deadline. We propose three variations of the SRT where biding history is publicized at different granularity. Using a simulation based study, we analyze the behavior of clients' bids in respond to the SRT. We compare the best HBF variant with an efficient Earliest Deadline First (EDF) mechanism that charges a fixed price. Our results show that the HBF mechanism is able to exploit price discrimination and therefore complete the execution of more high value jobs under a heavy workload, leading to better weighted throughput. HBF can also maximize server profit and client surplus (the difference between value and the client bid) in different settings. Thus, HBF may yield solutions that benefit both the client and the server.

MQO is a distributed multiple query processing middleware that can use resources available on the Grid to optimize query processing for data analysis and visualization applications. It does so by introducing one or more proxies that act as front-ends to a collection of backend servers. The basic idea behind this architecture is active semantic caching, whereby queries can leverage available cached results in the proxy either directly or through transformations. While this approach has been shown to speed up query evaluation under multi-client workloads, the caching infrastructure in the backend servers is not used well for query processing. Because this collective caching infrastructure scales with the number of servers, it is an important asset. In this paper, we describe a distributed multidimensional indexing scheme that enables the proxy to directly consider the cache contents available at the backend servers for query planning and scheduling. This approach is shown to produce better query plans and faster query response times as we experimentally demonstrate.

Stream processing applications have recently gained significant attention in the networking and database community. At the core of these applications is a stream processing engine that performs resource allocation and management to support continuous tracking of queries over collections of physically-distributed and rapidly-updating data streams. While numerous stream processing systems exist, there has been little work on understanding the performance characteristics of these applications in a distributed setup. In this paper, we examine the performance bottlenecks of streaming data applications, in particular the Linear Road stream data management benchmark, in achieving good performance in large-scale distributed environments, using the Stream Processing Core (SPC), a stream processing middleware we have developed. First, we present the design and implementation of the Linear Road benchmark on the SPC middleware. SPC has been designed to scale to tens of thousands of processing nodes, while supporting concurrent applications and multiple simultaneous queries. Second, we identify the main performance bottlenecks in the Linear Road application in achieving scalability and low query response latency. Our results show that data locality, buffer capacity, physical allocation of processing elements to infrastructure nodes, and packaging for transporting streamed data are important factors in achieving good application performance. Though we evaluate our system primarily for the Linear Road application, we believe it also provides useful insights into the overall system behavior for supporting other distributed and large-scale continuous streaming data applications. Finally, we examine how SPC can be used and tuned to enable a very efficient implementation of the Linear Road application in a distributed environment.

The availability of massive datasets, comprising sensor measurements or the results of scientific simulations, has had a significant impact on the methodology of scientific reasoning. Scientists require storage, bandwidth and computational capacity to query and analyze these datasets, to understand physical phenomena or to test hypotheses. This paper addresses the challenge of identifying and selecting resources to develop an evaluation plan for large scale data analysis queries when data processing capabilities and datasets are dispersed across nodes in one or more computing and storage clusters. We show that generating an optimal plan is hard and we propose heuristic techniques to find a good choice of resources. We also consider heuristics to cope with dynamic resource availability; in this situation we have stale information about reusable cached results (datasets) and the load on various nodes.

Data analysis applications in areas as diverse as remote sensing and telepathology require operating on and processing very large datasets. For such applications to execute efficiently, careful attention must be paid to the storage, retrieval, and manipulation of the datasets. This paper addresses the optimizations performed by a high performance database system that processes groups of data analysis requests for these applications, which we call queries. The system performs end-to-end processing of the requests, formulated as PostgreSQL declarative queries. The queries are converted into imperative descriptions, multiple imperative descriptions are merged into a single execution plan, the plan is optimized to decrease execution time via common compiler optimization techniques, and, finally, the plan is optimized to decrease memory consumption. The last two steps are experimentally shown to effectively reduc the amount of time required while conserving memory space as a group of queries is processed by the database.

We investigate techniques for efficiently executing multiquery workloads from data and computation-intensive applications in parallel and/or distributed computing environments. In this context, we describe a database optimization framework that supports data and computation reuse, query scheduling, and active semantic caching to speed up the evaluation of multiquery workloads. Its most striking feature is the ability of optimizing the execution of queries in the presence of application-specific constructs by employing a customizable data and computation reuse model. Furthermore, we discuss how the proposed optimization model is flexible enough to work efficiently irrespective of the parallel/distributed environment underneath. In order to evaluate the proposed optimization techniques, we present experimental evidence using real data analysis applications. For this purpose, a common implementation for the queries under study was provided according to the database optimization framework and deployed on top of three distinct experimental configurations: a shared memory multiprocessor, a cluster of workstations, and a distributed computational Grid-like environment.

This paper is concerned with the efficient execution of multiple query workloads on a cluster of SMPs. We target applications that access and manipulate large scientific datasets. Queries in these applications involve user-defined processing operations and distributed data structures to hold intermediate and final results. Our goal is to implement system components to leverage previously computed query results and to effectively utilize processing power and aggregated I/O bandwidth on SMP nodes so that both single queries and multi-query batches can be efficiently executed.

We show how five low-cost and nonintrusive techniques that work using free commodity tools such as GDB can be used to improve the debugging process of multi-threaded and/or distributed parallel programs. These techniques have been used in the development of major software middleware - DataCutter and MQO - and have proven their value by lowering the time necessary to detect and correct bugs.

The Grid environment facilitates collaborative work and allows many users to query and process data over geographically dispersed data repositories. Over the past several years, there has been a growing interest in developing applications that interactively analyze datasets, potentially in a collaborative setting. We describe the Active Proxy-G service that is able to cache query results, use those results for answering new incoming queries, generate subqueries for the parts of a query that cannot be produced from the cache, and submit the subqueries for final processing at application servers that store the raw datasets. We present an experimental evaluation to illustrate the effects of various design tradeoffs. We also show the benefits that two real applications gain from using the middleware.

Applications that analyze, mine, and visualize large datasets are considered an important class of applications in many areas of science, engineering, and business. Queries commonly executed in data analysis applications often involve user-defined processing of data and application-specific data structures. If data analysis is employed in a collaborative environment, the data server should execute multiple such queries simultaneously to minimize the response time to clients. In this paper we present the design of a runtime system for executing multiple query workloads on a shared-memory machine. We describe experimental results using an application for browsing digitized microscopy images.