Modeling and execution of event stream processing in business processes

The Internet of Things and Cyber-physical Systems provide enormous amounts of real-time data in the form of streams of events. Businesses can benefit from the integration of these real-world data; new services can be provided to customers, or existing business processes can be improved. Events are a well-known concept in business processes. However, there is no appropriate abstraction mechanism to encapsulate event stream processing in units that represent business functions in a coherent manner across the process modeling, process execution, and IT infrastructure layer. In this paper we present Event Stream Processing Units (SPUs) as such an abstraction mechanism. SPUs encapsulate application logic for event stream processing and enable a seamless transition between process models, executable process representations, and components at the IT layer. We derive requirements for SPUs and introduce EPC and BPMN extensions to model SPUs at the abstract and at the technical process layer. We introduce a transformation from SPUs in EPCs to SPUs in BPMN and implement our modeling notation extensions in Software AG ARIS. We present a runtime infrastructure that executes SPUs and supports implicit invocation and completion semantics. We illustrate our approach using a logistics process as running example.     

Hiding in stream semantics of uniform concurrency

Summary This paper shows how to treat the hiding operator originally defined by Hoare et al. for finite observations of processes, in an order theoretic setting based on finite and infinite streams. The main technical contribution is the continuity proof of the hiding operator based on a mixture of topological and order-theoretic arguments. As an application of the continuity of hiding, syntactic transformation rules for its calculation are derived. This calculus utilizes a general fixed point transformation technique.     

Order and metric in the stream semantics of elemental concurrency

Summary Two denotational semantics for a language with simple concurrency are presented. The language has parallel composition in the form of the shuffle operation, in addition to the usual sequential concepts including full recursion. Two linear time models, both involving sets of finite and infinite streams, are given. The first model is order-theoretic and based on the Smyth order. The second model employs complete metric spaces. Various technical results are obtained relating the order-theoretic and metric notions. The paper culminates in the proof that the two semantics for the language considered coincide. The paper completes previous investigations of the same language, establishing the equivalence of altogether four semantic models for it.     

The effect of execution policies on the semantics and analysis ofstochastic Petri nets

Petri nets in which random delays are associated with atomic transitions are defined in a comprehensive framework that contains most of the models already proposed in the literature. To include generally distributed firing times into the model one must specify the way in which the next transition to fire is chosen, and how the model keeps track of its past history; this set of specifications is called an execution policy. A discussion is presented of the impact that different execution policies have on semantics of the mode, as well as the characteristics of the stochastic process associated with each of these policies. When the execution policy is completely specified by the transition with the minimum delay (race policy) and the firing distributions are of the phase type, an algorithm is provided that automatically converts the stochastic process into a continuous time homogeneous Markov chain. An execution policy based on the choice of the next transition to fire independently of the associated delay (preselection policy) is introduced, and its semantics is discussed together with possible implementation strategies     

Dispatching stream operators in parallel execution of continuous queries

Data stream is a continuous, rapid, time-varying sequence of data elements which should be processed in an online manner. These matters are under research in Data Stream Management Systems (DSMSs). Single processor DSMSs cannot satisfy data stream applications?? requirements properly. Main shortcomings are tuple latency, tuple loss, and throughput. In our previous publications, we introduced parallel execution of continuous queries to overcome these problems via performance improvement, especially in terms of tuple latency. We scheduled operators in an event-driven manner which caused system performance reduction in periods between consecutive scheduling instances. In this paper, a continuous scheduling method (dispatching) is presented to be more compatible with the continuous nature of data streams as well as queries to improve system adaptivity and performance. In a multiprocessing environment, the dispatching method forces processing nodes (logical machines) to send partially-processed tuples to next machines with minimum workload to execute the next operator on them. So, operator scheduling is done continuously and dynamically for each tuple processed by each operator. The dispatching method is described, formally presented, and its correctness is proved. Also, it is modeled in PetriNets and is evaluated via simulation. Results show that the dispatching method significantly improves system performance in terms of tuple latency, throughput, and tuple loss. Furthermore, the fluctuation of system performance parameters (against variation of system and stream characteristics) diminishes considerably and leads to high adaptivity with the underlying system.     

A backtracking algorithm for the stream AND-parallel execution of logic programs

We present the first backtracking algorithm for stream AND-parallel logic programs. It relies on compile-time knowledge of the dataflow graph of each clause to let it figure out efficiently which goals to kill or restart when a goal fails. This crucial information, which we derive from mode declarations, was not available at compile-time in any previous stream AND-parallel system. We show that modes can increase the precision of the backtracking algorithm, though our algorithm allows this precision to be traded off against overhead on a procedure-by-procedure and call-by-call basis. The modes also allow our algorithm to handle efficiently programs that manipulate partially instantiated data structures and an important class of programs with circular dependency graphs. On code that does not need backtracking, the efficiency of our algorithm approaches that of the committed-choice languages; on code that does need backtracking its overhead is comparable to that of the independent AND-parallel backtracking algorithms.     

Distributed stream join query processing with semijoins

This paper addresses the distributed stream processing of window-based multi-way join queries considering the semijoin as a key join operator. In distributed stream processing, data streams arriving at remote sites need to be shipped to the processing site for query execution. This typically introduces high communication overhead. Our observation is that semijoin, effective in reducing communication overhead in distributed database query processing, can be also effective in distributed stream query processing. The challenge, however, lies in the streaming nature of the tuples, as it requires continuous and incremental processing of an unbounded sequence of tuples instead of one-time processing of a set of stored tuples. This paper describes our comprehensive work done to address the challenge. Specifically, we first propose a distributed stream join processing model that handles the issue of network delays introduced from the shipment of data streams, and allows for efficient batch processing. Then, based on the model, we propose join algorithms in a multi-way join case: first, one-way join algorithms for different combinations of join placement and join method and, then, multi-way join algorithms assuming linear join ordering. Regarding the join method, two distributed join methods are introduced: (1) simple join, in which full tuples are forwarded to the query processing site and (2) semijoin-based join, in which partial tuples are forwarded. A semijoin-based join can be executed with different possible semijoin strategies which incur different communication overheads. We present a complete set of join algorithms considering all possible semijoin strategies, and propose an optimization algorithm. The join algorithms are executed continuously in an incremental manner as tuples arrive, and never ship tuples redundantly. The optimization algorithm constructs an efficient multi-way join plan by using a greedy heuristic which adds to the plan one stream with the minimum join execution cost in each step. Through extensive experiments, we conduct comparative studies of the performance among the proposed one-way join algorithms and the efficiency of the generated plan between the optimization algorithm based on the greedy heuristic and the exhaustive search, respectively.     

A survey of stream processing

  Stream processing is a term that is used widely in the literature to describe a variety of systems. We present an overview of the historical development of stream processing and a detailed discussion of the different languages and techniques for programming with streams that can be found in the literature. This includes an analysis of dataflow, specialized  functional and logic programming with streams, reactive systems, signal processing systems, and the use of streams in the design and verification of hardware. The aim of this survey is an analysis of the development of each of these specialized topics to determine if a general theory of stream processing has emerged. As such, we discuss and classify the different classes of stream processing systems found in the literature from the perspective of programming primitives, implementation techniques, and computability issues, including a comparison of the semantic models that are used to formalize stream based computation. Received: 16 February 1995/ 27 March 1996     

Dynamic Meta Modeling with time: Specifying the semantics of multimedia sequence diagrams

The Unified Modeling Langugage (UML) offers different diagram types to model the behavior of software systems. In some domains like embedded real-time systems or multimedia systems, it is necessary to include specifications of time in behavioral models since the correctness of these applications depends on the fulfillment of temporal requirements in addition to functional requirements. UML thus already incorporates language features to model time and temporal constraints. Such model elements must have an equivalent in the semantic domain.We have proposed Dynamic Meta Modeling (DMM), an approach based on graph transformation, as a means for specifying operational semantics of dynamic UML diagrams. In this article, we extend this approach to also account for time by extending the semantic domain to timed graph transformation. This enables us to define the operational semantics of UML diagrams with time specifications. As an example, we provide semantics for special sequence diagrams from the domain of multimedia application modeling.     

基于语义的Web服务自动发现、匹配及执行平台

基于UDDI技术的普遍的Web服务发现、匹配、执行平台有可能产生严重的效率及服务响应延迟问题，文中介绍了一个限定于特定领域的Web服务自动发现、匹配及执行系统以试图解决此问题，同时给出了一个基于OWL-S本体语言的系统实现。在服务选择过程中实现了地域匹配功能，并为服务请求代理提供了一个初步的行为记忆功能。     

GS4: Graph stream summarization based on both the structure and semantics

The Journal of Supercomputing - Nowadays internet-based applications collect and distribute large datasets, which are mostly modeled by pertinent massive graphs. One solution to process such...     

Query indexing with containment-encoded intervals for efficient stream processing

Many continual range queries can be issued against data streams. To efficiently evaluate continual queries against a stream, a main memory-based query index with a small storage cost and a fast search time is needed, especially if the stream is rapid. In this paper, we study a CEI-based query index that meets both criteria for efficient processing of continual interval queries. This new query index is an indirect indexing approach. It centres around a set of predefined virtual containment-encoded intervals, or CEIs. The CEIs are used to first decompose query intervals and then perform efficient search operations. The CEIs are defined and labeled such that containment relationships among them are encoded in their IDs. The containment encoding makes decomposition and search operations efficient; from the encoding of the smallest CEI containing a data point, the encodings of other containing CEIs can be easily derived. Closed-form formulae for the bounds of the average index storage cost are derived. Simulations are conducted to evaluate the effectiveness of the CEI-based query index and to compare it with alternative approaches. The results show that the CEI-based query index significantly outperforms existing approaches in terms of both storage cost and search time. Kun-Lung Wu received the B.S. degree in electrical engineering from the National Taiwan University, Taipei, Taiwan, the M.S. and Ph.D. degrees in computer science from the University of Illinois at Urbana–Champaign. He is with the IBM Thomas J. Watson Research Center, currently a member of the Software Tools and Techniques Group. His current research interests include data streams, continual queries, mobile computing, Internet technologies and applications, database systems and distributed and parallel computing. He has published extensively and holds various patents in these areas. Dr. Wu is a Senior Member of the IEEE Computer Society and a member of the ACM. He was an Associate Editor for the IEEE Transactions on Knowledge and Data Engineering, 2000–2004. He was the general chair for the 3rd International Workshop on e-Commerce and Web-Based Information Systems (WECWIS 2001). He has served as an organising and program committee member on various conferences. He has received various IBM awards, including IBM Corporate Environmental Affair Excellence Award, Research Division Award and Invention Achievement Awards. He received a best paper award from IEEE EEE 2004. He is an IBM Master Inventor. Shyh-Kwei Chen received the B.S. degree in computer science and information engineering from National Taiwan University, Taipei, Taiwan, in 1983, the M.S. degree in computer science from the University of Minnesota, Minneapolis, in 1987, and the Ph.D. degree in computer science from University of Illinois at Urbana–Champaign, in 1994. Dr. Chen has been with the IBM Thomas J. Watson Research Center, Yorktown Heights, New York since October 1994, where he is currently a research staff member. His current research interests include XML, electronic commerce, business performance management, data engineering and compilers. He is a member of the ACM, the IEEE and the IEEE Computer Society. Philip S. Yu received the B.S. degree in electrical engineering from National Taiwan University, the M.S. and Ph.D. degrees in electrical engineering from Stanford University, and the M.B.A. degree from New York University. He is with the IBM Thomas J. Watson Research Center and is currently manager of the Software Tools and Techniques group. His research interests include data mining, Internet applications and technologies, database systems, multimedia systems, parallel and distributed processing and performance modelling. Dr. Yu has published more than 400 papers in refereed journals and conferences. He holds or has applied for more than 250 US patents. Dr. Yu is a Fellow of the ACM and a Fellow of the IEEE. He is an associate editor of ACM Transactions on Internet Technology. He is a member of the IEEE Data Engineering steering committee and is also on the steering committee of IEEE Conference on Data Mining. He was the Editor-in-Chief of IEEE Transactions on Knowledge and Data Engineering (2001–2004), an editor and advisory board member of IEEE Transactions on Knowledge and Data Engineering and also a guest coeditor of the special issue on mining of databases. He had also served as an associate editor of Knowledge and Information Systems. In addition to serving as program committee member on various conferences, he was the program cochair of the 11th International Conference on Data Engineering, the 6th Pacific Area Conference on Knowledge Discovery and Data Mining, and the 9th ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, and the program chair of the 2nd International Workshop on Research Issues on Data Engineering: Transaction and Query Processing, the PAKDD Workshop on Knowledge Discovery from Advanced Databases and the 2nd International Workshop on Advanced Issues of E-Commerce and Web-based Information Systems. He served as the general chair of the 14th International Conference on Data Engineering and the general cochair of the 2nd IEEE International Conference on Data Mining. He has received several IBM honours, including two IBM Outstanding Innovation Awards, an Outstanding Technical Achievement Award, two Research Division Awards and the 81st Plateau of Invention Achievement Awards. He received an Outstanding Contributions Award from IEEE International Conference on Data Mining in 2003 and also an IEEE Region 1 Award for “promoting and perpetuating numerous new electrical engineering concepts” in 1999. Dr. Yu is an IBM Master Inventor and was recognised as one of the IBM's 10 top leading inventors in 1999.     

QoS-aware placement of stream processing service

Many emerging online stream processing services require the consideration of quality of service (QoS), which is highly dependent on the placement of services at various hosts. This paper investigates the QoS-aware placement problems of stream processing services under different contexts. On condition that the client demands are stable, the QoS-aware placement problem aiming to minimize the cost when servers are CPU-uncapacitated, is equivalent to the set cover problem, and can be solved by a greedy algorithm with approximation factor O(log?n), where n is the number of clients. However, when CPU capacity constraints on servers are taken into account, the QoS-aware placement problem cannot be approximated unless P=NP. Therefore, we propose two heuristic algorithms: (1) ISCA (Iterated Set Cover-based Algorithm) and (2) KBA (Knapsack-Based Algorithm). We also consider the placement problem of client demands increasing over time. Two objectives, called extension factor and system lifetime, are proposed for demand increment-blind and increment-aware models respectively. Both of them can be solved by extending ISCA and KBA. The experimental results show that ISCA and KBA have distinct effects on different demand sizes. ISCA is more efficient when client demands are relatively small, while KBA performs better for larger demands.     

AES多引擎并行处理技术研究

为了提高AES的加密效率,在分析影响AES多引擎并行处理的相关因素的基础上,提出了AES多引擎并行处理架构,并分析了基于ECB工作模式下的数据分配调度机制.通过对AES密码算法的逻辑综合和多密码处理引擎的参数定量分析表明,在100MHz的核心频率下,对128比特长度的密钥,4个AES密码处理引擎并行处理的数据吞吐率可以达到4.98Gb/s.     

Modeling and analysis of transaction execution in database systems

The controlled-generator model of P.J. Ramadge and W.M. Wonham (1988) is used to formulate the concurrent execution of transactions in database systems as a control problem for a partially observed discrete-event dynamical system. The control objectives of this problem (for concurrency control and recovery) and the properties of some important transaction scheduling techniques are characterized in terms of the language generated by the controlled process and in terms of the stage of an ideal complete-information scheduler. Results about the performance of these techniques are presented     

Query processing of multi-way stream window joins

This paper introduces a class of join algorithms, termed W-join, for joining multiple infinite data streams. W-join addresses the infinite nature of the data streams by joining stream data items that lie within a sliding window and that match a certain join condition. In addition to its general applicability in stream query processing, W-join can be used to track the motion of a moving object or detect the propagation of clouds of hazardous material or pollution spills over time in a sensor network environment. We describe two new algorithms for W-join and address variations and local/global optimizations related to specifying the nature of the window constraints to fulfill the posed queries. The performance of the proposed algorithms is studied experimentally in a prototype stream database system, using synthetic data streams and real time-series data. Tradeoffs of the proposed algorithms and their advantages and disadvantages are highlighted, given variations in the aggregate arrival rates of the input data streams and the desired response times per query. This is an extended version of the paper published in the Proceedings of the 15th International Conference on Scientific and Statistical Database Management, SSDBM 2003, Boston, U.S.A., pp. 75–84.     

Modeling cycle-to-cycle dynamics and mode transition in HCCI engines with variable valve actuation

Due to dilution limits, homogeneous charge compression ignition (HCCI) engines will need to switch to a conventional spark ignition (SI) or diesel mode at very low and high load conditions. This paper outlines a simple and accurate control-oriented model of a single-cylinder multi-mode HCCI engine using exhaust reinduction. An exhaust manifold model ties the exhausted gas from one cycle to that reinducted on the next cycle. The results show that the cyclic dynamics which occur during an SI-to-HCCI mode transition are essentially just an extension of the inherent cycle-to-cycle dynamics of HCCI. Multi-cycle, multi-mode simulations demonstrate the steady state and dynamic behavior seen on an experimental system. Predicted combustion timing, in-cylinder pressure, work output and exhaust temperature values agree very well with experiment. This model provides a basis for developing and validating controllers capable of controlling HCCI during mode transitions.     

基于OpenCV的视频图像处理应用研究

以嵌入式ARM为硬件平台,以ARM-Linux为软件平台,在QT/Qtopia图形用户界面下,通过调用OpenCV图形处理库设计摄像头应用程序,最终实现把摄像头采集到的视频流数据显示在Qtopia图形用户界面窗体上.介绍了QT编程的基本原理,阐述了OpenCV图像处理库的工作机制与使用方法.     

Applying big data and stream processing to the real estate domain

ABSTRACT

In this paper, we propose an architecture that combines Big Data and Stream Processing which can be applied to the Real Estate Domain. Our approach consists of a specialisation of Lambda architecture and it is inspired by some aspects of Kappa architecture. As a proof of this solution, we show a prototype developed following it and a comparison of the three architecture quality models. Finally, we highlight the differences between the proposed architecture and similar ones and draw some future lines following the present approach.