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”

Ares: an adaptively reoptimizing engine for stream query processing

Joseph Gomes, Hyeong-ah Choi · 2006

Applications dealing with continuous streaming data such as sensor data processing, network traffic engineering, network monitoring, intrusion detection, financial monitoring etc are becoming more and more predominant. Such applications have to deal with multiple continuous data streams with inputs arriving at highly variable and unpredictable rates from various sources. These applications have to perform various operations (e.g. filter, aggregate, join etc) on incoming data streams in real-time according to predefined queries or rules. Since the data rate and distribution fluctuate over time, an appropriate join tree for processing join queries must be adaptively maintained in response to dynamic environments to prevent rapid degradation of the system performance. In this paper we present ARES, an adaptively re-optimizing engine for stream queries that we have developed by extending Jess1. We also address the problem of finding an optimal join tree that maximizes throughput for sliding window based multi-join queries over continuous data streams. We present a dynamic programming algorithm OptDP, that produces the optimal tree but runs in an exponential time in the number of input streams. We then present a polynomial time greedy algorithm XGreedyJoin. Our experiments show that for almost all instances, trees from 1Jess is a popular RETE-based, forward chaining rule engine written in java 1 XGreedyJoin perform close to the optimal trees from OptDP, and significantly better than common heuristics-based XJoin algorithms. 1

Cited by 0

Query-Centric Failure Recovery for Distributed Stream Processing Engines

Li Su, Yongluan Zhou · 2018

Correlated failures that usually involve a number of nodes failing simultaneously have significant effect on systems' availability, especially for streaming applications that require real-time analysis. Most state-of-the-art distributed stream processing engines focus on recovering individual operator failure. By analyzing the existing recovery techniques, we identify the challenges and propose a fault-tolerance framework that can tolerate both individual and correlated failures with minimum overhead during the system's normal execution. Our progressive and query-centric recovery paradigm carefully schedules the recovery of failed operators based on the current availability of resources, such that the outputs of queries can be recovered as early as possible. We also formulate the new problem of recovery scheduling under correlated failures and design algorithms to optimize the recovery latency with a performance guarantee.

Cited by 0

State-Slice: A New Stream Query Optimization Paradigm for Multi-query and Distributed Processing

Song Wang · Digital WPI · 2008

Modern stream applications necessitate the handling of large numbers of continuous queries specified over high volume data streams. This dissertation proposes novel solutions to continuous query optimization in three core areas of stream query processing, namely state-slice based multiple continuous query sharing, ring-based multi-way join query distribution and scalable distributed multi-query optimization. The first part of the dissertation proposes efficient optimization strategies that utilize the novel state-slicing concept to achieve maximum memory and computation sharing for stream join queries with window constraints. Extensive analytical and experimental evaluations demonstrate that our proposed strategies is capable to minimize the memory or CPU consumptions for multiple join queries. The second part of this dissertation proposes a novel scheme for the distributed execution of generic multi-way joins with window constraints. The proposed scheme partitions the states into disjoint slices in the time domain, and then distributes the fine-grained states in the cluster, forming a virtual computation ring. New challenges to support this distributed state-slicing processing are answered by numerous new techniques. The extensive experimental evaluations show that the proposed strategies achieve significant performance improvements in terms of response time and memory usages for a wide range of configurations and workloads on a real system. Ring based distributed stream query processing and multi-query sharing both are based on the state-slice concept. The third part of this dissertation combines the first two parts of this dissertation work and proposes a novel distributed multi-query optimization technique.

Cited by 0Open access

Stream Processing of Shortest Path Query in Dynamic Road Networks

Mengxuan Zhang, Lei Li, Wen Hua et al. · IEEE Transactions on Knowledge and Data Engineering · 2020

Shortest path query in road network is pervasive in various location-based services nowadays. As the business expands, the scalability issue becomes severer and more servers are deployed to cope with it. Moreover, as the traffic condition keeps changing over time, the existing index-based approaches can hardly adapt to the real-life dynamic environment. Therefore, batch shortest path algorithms have been proposed recently to answer a set of queries together using shareable computation. Besides, they can also work in a highly dynamic environment as no index is needed. However, the existing batch algorithms either assume the batch queries are finely decomposed or just process them without differentiation, resulting in poor query efficiency. In this work, we assume the traffic condition is stable over a short period and treat the issued queries within that period as a stream of query sets. Specifically, we first propose three query set decomposition methods to cluster one query set into multiple query subsets: <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Zigzag</i> that considers the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1-N</i> shared computation; <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Co-Clustering</i> that considers the source and target's spatial locality; and <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Search-Space-Aware</i> that further incorporates search space estimation. After that, we propose two batch algorithms that take advantage of the previously decomposed query sets for efficient query answering: <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R2R</i> that finds a set of approximate shortest paths from one region to another with bounded error; and <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Local Cache</i> that improves the existing <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Global Cache</i> with higher cache hit ratio. Finally, we design three efficient stream processing methods for intra-batch shared computation. The experiments on a large real-world query sets verify the effectiveness and efficiency of our decomposition methods compared with the state-of-the-art batch algorithms.

Cited by 22

Efficient XML Stream Processing with Automata and Query Algebra APPROVED:

Jinhui Jian · 2003

XML Stream Processing is an emerging technology designed to support declar-ative 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 monitor-ing systems for stock, email, and sensor data that need to analyze incoming data streams. There are however several open challenges. One, we must develop effi-cient 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

Cited by 0

Kazemitabar 1 Geospatial Stream Query Processing using Microsoft SQL Server StreamInsight

Mohamed H Ali, Afsin Akdogan, Cyrus Shahabi · 2014

Microsoft SQL Server spatial libraries contain several components that handle geometrical and geographical data types. With advances in geo-sensing technologies, there has been an increasing demand for geospatial streaming applications. Microsoft SQL Server StreamInsight (StreamInsight, for brevity) is a platform for developing and deploying streaming applications that run continuous queries over high-rate streaming events. With its extensibility infrastructure, StreamInsight enables developers to integrate their domain expertise within the query pipeline in the form of user defined modules. This demo utilizes the extensibility infrastructure in Microsoft StreamInsight to leverage its continuous query processing capabilities in two directions. The first direction integrates SQL spatial libraries into the continuous query pipeline of StreamInsight. StreamInsight provides a well-defined temporal model over incoming events while SQL spatial libraries cover the spatial properties of events to deliver a solution for spatiotemporal stream query processing. The second direction extends the system with an analytical refinement and prediction layer. This layer analyzes historical data that has been accumulated and summarized over the years to refine, smooth and adjust the current query output as well as predict the output in the near future. The demo scenario is based on transportation data in Los Angeles County. 1.

Cited by 0

New Access Control for Secure Query Processing over XML Data Stream

Dong Chan An, Seog Park · 2007 International Conference on Convergence Information Technology (ICCIT 2007) · 2007

As secure query processing of XML data stream in ubiquitous environment has become very important, there is an increasing need to enforce efficient secure access control. In this paper we propose a new access control for secure query processing using dynamic XML documents labeling technique and XML fragmentation. In particular, Medical records XML document has the characteristic of an infinite addition in width rather than in depth because of the increment of patients. Our new access control method can fully manage the size of documents that increases to infinity. We show that our approach has little impact on the processing time through experimental evaluation.

Cited by 11

Query Processing, Resource Management, and Approximation in a Data Stream Management System

Rajeev Motwani, Jennifer Widom, Arvind Arasu et al. · 2003

This paper describes our ongoing work developing the Stanford Stream Data Manager (STREAM), a system for executing continuous queries over multiple continuous data streams. The STREAM system supports a declarative query language, and it copes with high data rates and query workloads by providing approximate answers when resources are limited. This paper describes specific contributions made so far and enumerates our next steps in developing a general-purpose Data Stream Management System.

Cited by 0

Handling Tradeoffs between Performance and Query-Result Quality in Data Stream Processing

Ji, Yuanzhen · Qucosa (Saxon State and University Library Dresden) · 2017

Data streams in the form of potentially unbounded sequences of tuples arise naturally in a large variety of domains including finance markets, sensor networks, social media, and network traffic management. The increasing number of applications that require processing data streams with high throughput and low latency have promoted the development of data stream processing systems (DSPS). A DSPS processes data streams with continuous queries, which are issued once and return query results to users continuously as new tuples arrive. For stream-based applications, both the query-execution performance (in terms of, e.g., throughput and end-to-end latency) and the quality of produced query results (in terms of, e.g., accuracy and completeness) are important. However, a DSPS often needs to make tradeoffs between these two requirements, either because of the data imperfection within the streams, or because of the limited computation capacity of the DSPS itself. Performance versus result-quality tradeoffs caused by data imperfection are inevitable, because the quality of the incoming data is beyond the control of a DSPS, whereas tradeoffs caused by system limitations can be alleviated—even erased—by enhancing the DSPS itself. This dissertation seeks to advance the state of the art on handling the performance versus result-quality tradeoffs in data stream processing caused by the above two aspects of reasons. For tradeoffs caused by data imperfection, this dissertation focuses on the typical data-imperfection problem of stream disorder and proposes the concept of quality-driven disorder handling (QDDH). QDDH enables a DSPS to make flexible and user-configurable tradeoffs between the end-to-end latency and the query-result quality when dealing with stream disorder. Moreover, compared to existing disorder handling approaches, QDDH can significantly reduce the end-to-end latency, and at the same time provide users with desired query-result quality. In this dissertation, a generic buffer-based QDDH framework and three instantiations of the generic framework for distinct query types are presented. For tradeoffs caused by system limitations, this dissertation proposes a system-enhancement approach that combines the row-oriented and the column-oriented data layout and processing techniques in data stream processing to improve the throughput. To fully exploit the potential of such hybrid execution of continuous queries, a static, cost-based query optimizer is introduced. The optimizer works at the operator level and takes the unique property of execution plans of continuous queries—feasibility—into account.

Cited by 0Open access