Skip to content
Free planNo credit card requiredStart writing
AI for Research home
AI for Research home
Dashboard
Sign inGet started

Search 250 million research papers

Read the abstract, see who wrote it and who cites it, and get the citation in APA, MLA, Chicago or Harvard.

About 1,006 papers for “stream query processing”

Data Stream Query Processing

Nick Koudas, Divesh Srivastava · 2005

This tutorial provides a comprehensive and cohesive overview of the key research results in the area of data stream query processing, both for SQL-like and XML query languages.

Cited by 16

XML Stream Query Processing

Mingzhu Wei, Ming Li, Elke A. Rundensteiner et al. · IGI Global eBooks · 2010

Stream applications bring the challenge of efficiently processing queries on sequentially accessible XML data streams. In this chapter, the authors study the current techniques and open challenges of XML stream processing. Firstly, they examine the input data semantics in XML streams and introduce the state-of-the-art of XML stream processing. Secondly, they compare and contrast the automatonbased and algebra-based techniques used in XML stream query execution. Thirdly, they study different optimization strategies that have been investigated for XML stream processing – in particular, they discuss cost-based optimization as well as schema-based optimization strategies. Lastly but not least, the authors list several key open challenges in XML stream processing.

Cited by 1

Ad-hoc stream query processing

Jeyhun Karimov · DepositOnce · 2020

Many modern applications require processing large amounts of data in a real-time fashion. As a result, distributed stream processing engines (SPEs) have gained significant attention as an important new class of big data processing systems. The central design principle of these SPEs is to handle queries that potentially run forever on data streams with a query-at-a-time model, i.e., each query is optimized and executed separately. However, in many real applications, not only long-running queries but also many short-running queries are processed on data streams. In these applications, multiple stream queries are created and deleted concurrently, in an ad-hoc manner. The best practice to handle ad-hoc stream queries is to fork input stream and add additional resources for each query. However, this approach leads to redundant computation and data copy. This thesis lays the foundation for efficient ad-hoc stream query processing. To bridge the gap between stream data processing and ad-hoc query processing, we follow a top-down approach. First, we propose a benchmarking framework to analyze state-of-the-art SPEs. We provide a definition of latency and throughput for stateful operators. Moreover, we carefully separate the system under test and the driver, to correctly represent the open-world model of typical stream processing deployments. This separation enables us to measure the system performance under realistic conditions. Our solution is the first benchmarking framework to define and test the sustainable performance of SPEs. Throughout our analysis, we realize that the state-of-the-art SPEs are unable to execute stream queries in an ad-hoc manner. Second, we propose the first ad-hoc stream query processing engine for distributed data processing environments. We develop our solution based on three main requirements: (1) Integration: Ad-hoc query processing should be a composable layer that can extend stream operators, such as join, aggregation, and window operators; (2) Consistency: Ad-hoc query creation and deletion must be performed consistently and ensure exactly-once semantics and correctness; (3) Performance: In contrast to modern SPEs, ad-hoc SPEs should not only maximize data throughput but also query throughout via incremental computation and resource sharing. Third, we propose an ad-hoc stream join processing framework that integrates dynamic query processing and query re-optimization techniques with ad-hoc stream query processing. Our solution comprises an optimization layer and a stream data processing layer. The optimization layer periodically re-optimizes the query execution plan, performing join reordering and vertical and horizontal scaling at runtime without stopping the execution. The data processing layer enables incremental and consistent query processing, supporting all the actions triggered by the optimizer. The result of the second and the third contributions forms a complete ad-hoc SPE. We utilize the first contribution not only for benchmarking modern SPEs but also for evaluating the ad-hoc SPE.

Cited by 0Open access

Scalable Scientific Stream Query Processing

Milena Ivanova · 2005

Scientific applications require processing of high-volume on-line streams of numerical data from instruments and simulations. In order to extract information and detect interesting patterns in thes ...

Cited by 3

Timestamp Embedding Query Stream Processing Engine

M. Ananthi, M. R. Sumalatha · Indian Journal of Science and Technology · 2015

Background/Objectives: To improve the performance of the streaming data through RDF vocabulary and multi query optimization. Methods/Statistical Analysis: The scalability and performance of the query processor is improved with the use of native timestamp embedding query processor with the help of semantic approach. This offers vibrant, scalable services for continuous query processing. Continuous data is controlled through dynamic sliding window for incremental evaluation of streaming data. Static queries are processed continuously and all processing is done within main memory. Semantic sensor web is used to process sensor data semantically by query processing engine and metadata will be stored as triple stores. Findings: The continuous stream of queries is properly handled by the dynamic sliding window and sent to the query optimizer for optimization. The triple formatted outcomes are warehoused into OWL, which stores and adopt the relational database format. The data conversion will be done by the data transformer and finally results will be realized as stream of data. In this proposed model, the RDF vocabulary has been redesigned by adding timestamps along with incoming triples. The classes and properties are depicted in terms of the triples (Subject S, Object O and Predicate P) and are designed as OWL. Data sets are split into smaller parts for continuous updates and collect them into massive data sets so as to obtain faster insertion rates. It takes less time to process temporal, complex and multi queries in proposed system. Since timestamp is attached as one of the object in the triples, it is easy to retrieve and execute timestamp embedding queries. The proposed system is appropriate for all types of queries and proves efficiency in execution time. Application/Improvement: Temporal, complex and multi join queries are executed and evaluated for weather monitoring system. Keywords: OWL, Semantic Web, Sliding Window, Stream Processor, Timestamp Data

Cited by 0Open access

Monitoring Stream Properties for Continuous Query Processing

Utkarsh Srivastava, Shivnath Babu, Jennifer Widom · 2003

focus now on properties related to stream data and arrival characteristics. As a simple example of property-based query execution, if a stream is known to be roughly sorted on an attribute , and is a join attribute or is the grouping attribute in an aggregate query, much less memory is required than for a plan that accommodates randomly arriving values of . More subtly, the best plan for an -way sliding-window stream join depends heavily on the relative arrival rates of the streams involved in the join [VNB02], and "traditional" data statistics such as histograms, but over recent stream elements [DGIM02]. Scheduling decisions depend on stream burstiness and data characteristics [BBDM03]. In [BW02] we studied three specific stream properties and how they affect query execution: sortedness, clustering, and stream-based referential integrity. We identified an adherence parameter for each type of constraint, which indicates how closely a stream (or pair of streams, for r

Cited by 6

Operator placement for innetwork stream query processing

Utkarsh Srivastava, Kamesh Munagala, Jennifer Widom · 2005

In sensor networks, data acquisition frequently takes place at low-capability devices. The acquired data is then transmitted through a hierarchy of nodes having progressively increasing network band-width and computational power. We consider the problem of ex-ecuting queries over these data streams, posed at the root of the hierarchy. To minimize data transmission, it is desirable to perform “in-network ” query processing: do some part of the work at inter-mediate nodes as the data travels to the root. Most previous work on in-network query processing has focused on aggregation and inex-pensive filters. In this paper, we address in-network processing for queries involving possibly expensive conjunctive filters, and joins. We consider the problem of placing operators along the nodes of the hierarchy so that the overall cost of computation and data trans-mission is minimized. We show that the problem is tractable, give an optimal algorithm, and demonstrate that a simpler greedy op-erator placement algorithm can fail to find the optimal solution. Finally we define a number of interesting variations of the basic operator placement problem and demonstrate their hardness. 1.

Cited by 0

Data stream processing and query optimization techniques

Carlo Zaniolo, Yijian Bai · 2007

Many modem applications require continuous processing of massive data streams, creating difficult research challenges on multiple fronts. Foremost among these there is the design and implementation of Data Stream Management Systems (DSMSs) that optimize the execution of multiple continuous queries, on massive and bursty data streams to produce fast, near-realtime, responses upon tuple arrival. Existing query constructs and query processing techniques of DataBase Management Systems must be greatly extended and revised to support efficiently continuous queries in DSMSs. In this dissertation, we propose novel query scheduling algorithms and query constructs whose effectiveness was demonstrated in the Stream Mill DSMS prototype. Thus, we introduce on-demand timestamp generation and propagation mechanisms based on a flexible query-execution model, to solve the idle-waiting problem, improve query response, and reduce memory consumption. Moreover, we introduce practical scheduling algorithms, which assume uniform cost for tuples on the same operator, to handle query graphs of arbitrary complexity. Finally, we compare the performance of these practical algorithms against the theoretically optimal ones that assume perfect knowledge on the costs of the individual topics being processed. Our experiments show that the performance of the former closely approximate that of the latter. In order to utilize DBMS languages for data stream processing, stream-oriented constructs, such as sliding windows, have to be defined and integrated into the query language. Thus, we introduce novel constructs and techniques for supporting sliding windows on arbitrary User Defined Aggregates, as to achieve their incremental maintenance on logical and physical windows. Finally, we explore some performance optimization issues in advanced applications, including RFID (Radio Frequency IDentification) applications, and load-shedding in multi-source stream classifiers.

Cited by 0

Interval query indexing for efficient stream processing

Kun‐Lung Wu, Shyh-Kwei Chen, Philip S. Yu · 2004

A large number of continual range queries can be issued against a data stream. Usually, 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 present a CEI-based query index that meets both criteria for efficient processing of continual interval queries in a streaming environment. This new query index is centered around a set of predefined virtual <i>containment-encoded intervals</i>, 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 because integer additions and logical shifts can be used to carry out most of the operations. 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.

Cited by 31

Query Processing Using Negative and Temporal Tuples in Stream Query Engines

Marcin Gorawski, Aleksander Chrószcz · Lecture notes in computer science · 2012

In this paper, we analyze how stream monotonicity classification can be adopted for the introduced developed model, which processes both temporal and negative events. As we show, information about stream monotonicity can be easily used to optimize individual stream operators as well as a full query plan. Comparing our stream engine with such engines as CEDR, STREAM and PIPES we demonstrate how a primary key constraint can be used in different types of the developed stream schemes. We implemented all of the above techniques in StreamAPAS.

Cited by 5Open access

Multi-Model Based Optimization for Stream Query Processing

2008

With recent explosive growth of sensors and instruments, large scale data-intensive and computation-intensive applications are emerging, especially in scientific fields. Helping scientists to efficiently, even in real time, process queries over those large scale scientific streams thus has great demand. However, query optimization for high volume stream applications – in particular its core component, the evaluation model – has not been systematically studied. We observe that evaluating stream query plans should consider three aspects: output rate, computation cost and memory consumption. However, to our knowledge, no existing research on evaluating stream query plans consider all three metrics. In this paper, we propose a new combined optimization goal which leverages all these aspects and develop a multi-model based optimization framework to accomplish this goal. Specifically, we build three models to evaluate a plan’s output rate, computation cost and memory consumption respectively. Based on such three models, we search for an optimal plan while considering systems’s computation resource and memory constraints. We also experimentally evaluate our optimization framework. 1

Cited by 0

Generalized data stream indexing and temporal query processing

T. Y. Cliff Leung, Richard R. Muntz · 2003

Presents a novel indexing technique for temporal data stream which are sorted on the effective start time attribute. The index can be exploited in processing complex temporal pattern queries (such as multi-way joins) that are qualified with snapshot operators (e.g. the 'as of' operator). The advantages and limitations of the proposed scheme and a quantitative analysis of the storage requirements are presented. The authors propose some optimization alternatives that can reduce the storage requirements.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>

Cited by 12

Unbounded Spatial Data Stream Query Processing using Spatial Semijoins

Wendy Osborn · Journal of Ubiquitous Systems and Pervasive Networks · 2021

In this paper, the problem of query processing in spatial data streams is explored, with a focus on the spatial join operation. Although the spatial join has been utilized in many proposed centralized and distributed query processing strategies, for its application to spatial data streams the spatial join operation has received very little attention. One identified limitation with existing strategies is that a bounded region of space (i.e., spatial extent) from which the spatial objects are generated needs to be known in advance. However, this information may not be available. Therefore, two strategies for spatial data stream join processing are proposed where the spatial extent of the spatial object stream is not required to be known in advance. Both strategies estimate the common region that is shared by two or more spatial data streams in order to process the spatial join. An evaluation of both strategies includes a comparison with a recently proposed approach in which the spatial extent of the data set is known. Experimental results show that one of the strategies performs very well at estimating the common region of space using only incoming objects on the spatial data streams. Other limitations of this work are also identified.

Cited by 2Open access

Efficient XML Stream Processing with Automata and Query Algebra

Jinhuj Jian · Digital WPI · 2003

"XML Stream Processing is an emerging technology designed to support declarative queries over continuous streams of data. The interest in this novel technology is growing due to the increasing number of real world applications such as monitoring systems for stock, email, and sensor data that need to analyze incoming data streams. There are however several open challenges. One, we must develop efficient techniques for pattern matching over the nested tag structure of XML as data streams in token by token. Two, we must develop techniques for query optimization to cope with complex user queries while given only incomplete knowledge of source data. When considering these challenges separately, then automata models have been shown by several recent works to be suited to tackle the first problem, while algebraic query models have been regarded as appropriate foundations to tackle the second problem. The question however remains how best to put these two models together to have an overall effective system. This thesis aims to exactly fill this gap. We propose a unified query framework to augment automata-style processing with algebra-based query optimization capabilities. We use the automata model to handle the token-oriented streaming XML data and use the algebraic model to support set-oriented optimization techniques. The framework has been designed in two layers such that the logical layer provides a uniform abstraction across the two models and any optimization techniques can be applied in either model uniformly using query rewritings. The physical layer, on the other hand, allows us to refine the implementation details after the logical layer optimization. We have successfully applied this framework in the Raindrop stream processing system. We have identified several trade-offs regarding which query functionality should be realized in which specific query model. We have developed novel optimization techniques to exploit these trade-offs. For example, a query rewrite rule can flexibly push down a pattern matching into the automata model when the optimizer decides that it is more efficient to do so. To deal with incomplete knowledge of source data, we have also developed novel techniques to monitor data statistics, based on which we can apply optimization techniques to choose the optimal query plan at runtime. Our experimental study confirms that considerable performance gains are being achieved when these optimization techniques are applied in our system."

Cited by 1Open access

An Adaptive Query Processing Mechanism in Data Stream System

Song Bao · 2006

Aimed at properties of continuous queries, we present an adaptive query processing mechanism. It can not only optimize the time at which the last result tuple appears, but also optimize for the number of answers computed at any specified time after the query evaluation. This mechanism depends mainly on an output-rate-based cost model. Firstly, this model treats changed input rate, predicative selectivity and execution time of operators as its function variables. Secondly, it will compute output rate as function output. So this cost model can continuously adapt to variable factors of environment and data stream itself. Meanwhile, it can be a standard to select query plan. Experiment has proved that this mechanism validly increases throughput and output rate, meanwhile reduces output time latency and memory requirements.

Cited by 1

High performance stream query processing with correlation-aware partitioning

Lei Cao, Elke A. Rundensteiner · Proceedings of the VLDB Endowment · 2013

State-of-the-art optimizers produce one single optimal query plan for all stream data, in spite of such a singleton plan typically being sub-optimal or even poor for highly correlated data. Recently a new stream processing paradigm, called multi-route approach, has emerged as a promising approach for tackling this problem. Multi-route first divides data streams into several partitions and then creates a separate query plan for each combination of partitions. Unfortunately current approaches suffer from severe shortcomings, in particular, the lack of an effective partitioning strategy and the prohibitive query optimization expense. In this work we propose the first practical multi-route optimizer named &lt;u&gt;c&lt;/u&gt;orrelation-aware &lt;u&gt;m&lt;/u&gt;ulti-&lt;u&gt;r&lt;/u&gt;oute stream query optimizer (or CMR) that solves both problems. By exploiting both intra- and inter-stream correlations of streams, CMR produces effective partitions without having to undertake repeated expensive query plan generation. The produced partitions not only are best served by distinct optimal query plans, but also leverage the partition-driven pruning opportunity. Experimental results with both synthetic and real life stream data confirm that CMR outperforms the state-of-the-art solutions up to an order of magnitude in both the query optimization time and the run-time execution performance.

Cited by 22