Junichi Tatemura · IGI Global eBooks · 2010
This chapter reviews recent advances on stream XML query evaluation algorithms with stack-based encoding of intermediary data. Originally proposed for disk-resident XML, the stack-based architecture has been extended for streaming algorithms for both single and multiple query processing, ranging from XPath filtering to more complex XQuery. The key benefit of the stack-based architecture is its succinct encoding of partial query results, which can cause exponential enumeration if encoded naively. In addition, the chapter discusses opportunities to integrate benefits demonstrated in the reviewed work. For single-query processing, a sketch is given for an integrated algorithm, StreamTwig2Stack, that achieves all the benefits of existing algorithms in terms of functionality, time complexity, and buffer memory optimality.
Cited by 2
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
Sven Schmidt, Rainer Gemulla, Wolfgang Lehner · Lecture notes in computer science · 2003
Cited by 1
DigiNole (Florida State University) · 2012
In this dissertation, I present a table-driven streaming XML (Extensible Markup Language) parsing and searching technique, called TDX, and investigate related techniques. TDX expedites XML parsing, validation and searching by pre-recording the states of an XML parser in tabular forms and by utilizing an efficient runtime streaming parsing engine based on a two-stack push-down automaton. The parsing tables are automatically produced from the XML schemas or from the WSDL (Web Services Description Language) service descriptions. Because the schema constraints and XPath expressions are pre-encoded in a parsing table, the approach effectively implements a schema-specific XML parser and/or query processor that combines parsing, validation and search into a single pass. Moreover, the runtime parsing engine is independent of XML schemas and XPath query expressions, parsing can be populated on-the-fly to the runtime engine, thus TDX efficiently eliminates the recompilation and redeployment requirements of schema-specific parsers to address the schema changes. Similarly, different XPath queries can also be preprocessed at compile time and populated on-the-fly to the TDX searching engine without runtime overhead. To construct the parsing tables, we developed a set of mapping rules that translate XML schemas to augmented grammars. The augmented grammars support the full expressive power of the W3C XML Schema by introducing permutation phrase grammars and multi-occurrence phrase grammars. The augmented grammars are suitable to construct a predicative parsing table. The predictive parsing table constructed from the augmented grammars can be integrated into the parser at any time to maximize the performance or be populated on-the-fly at runtime and address schema changes efficiently. Because parsing tables or searching tables are pre-processed at compile time, and looking up the tables at runtime is deterministic and takes constant time, TDX efficiently implements a single pass, predictive validating parser without backtracking or function calling overheads. Our experimental results show a significant performance improvement compared to widely used XML parsers, either validating and non-validating, and to XML query processors.
Cited by 0Open access
Wei Zhang · 2012
Cited by 0
Shaolei Feng, Giridhar Kumaran · 2007
Running XPath queries on XML data steams is a challenge. Current approaches that store the entire document tree in memory are more suited for static environments. We modify the existing YFilter architecture to support online execution of XPath queries. This is achieved by minimal buffering of the data stream and dynamic pruning of the document tree in memory. These modifications enable us to efficiently process XPath queries on streaming XML data. 1
Cited by 0
Minos Garofalakis, Amit Kumar · ACM Transactions on Database Systems · 2005
We propose the first known solution to the problem of correlating, in small space, continuous streams of XML data through approximate (structure and content) matching, as defined by a general tree-edit distance metric. The key element of our solution is a novel algorithm for obliviously embedding tree-edit distance metrics into an L 1 vector space while guaranteeing a (worst-case) upper bound of O (log 2 n log* n ) on the distance distortion between any data trees with at most n nodes. We demonstrate how our embedding algorithm can be applied in conjunction with known random sketching techniques to (1) build a compact synopsis of a massive, streaming XML data tree that can be used as a concise surrogate for the full tree in approximate tree-edit distance computations; and (2) approximate the result of tree-edit-distance similarity joins over continuous XML document streams. Experimental results from an empirical study with both synthetic and real-life XML data trees validate our approach, demonstrating that the average-case behavior of our embedding techniques is much better than what would be predicted from our theoretical worst-case distortion bounds. To the best of our knowledge, these are the first algorithmic results on low-distortion embeddings for tree-edit distance metrics, and on correlating (e.g., through similarity joins) XML data in the streaming model.
Cited by 46
2008
Several applications based on XML stream processing have recently emerged, such as those for air traffic control and the selective dissemination of information (SDI). Their common need is to process a large number of XPath expressions in continuous XML streams at high throughput. This paper proposes four techniques for XPath expression processing based on Deterministic Finite Automata (DFA) for two purposes: to improve the memory usage efficiency of the automata and to support the processing of branching XPath expressions. The first technique, called n-DFA, clusters the given XPath expressions into n clusters to reduce the number of DFA states. The second, called shared NFA state table, lets the Non-Deterministic Finite Automata (NFA) state set be shared among the DFA states. Our experiments show that memory usage in an 8-DFA can, with the shared NFA state table, be reduced to 1/40th that of the original 1-DFA. The optimized NFA conversion and general XPath expression processing algorithm techniques contribute to the processing of branching XPath expressions efficiently; overall performance is better than is possible with earlier approaches.
Cited by 0
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
Sangwook Lee, Jin Kim, Hyunchul Kang · Lecture notes in computer science · 2007
Cited by 2
Weidong Yang, Daewook Lee, Ning Gu et al. · 2006
Stream-based continuous query processing fits a large class of new applications, such as sensor networks, location tracking, network management and financial data analysis. In this paper, we propose an efficient system called LeoXSS that processes complex twig patterns with OR-predicates and AND-predicates over XML document streams. In LeoXSS, a set of twig patterns is processed in a single document-order pass over the input document stream avoiding the post-processing of nested paths.
Cited by 0
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
Hong Su, Elke A. Rundensteiner, Murali Mani · Data & Knowledge Engineering · 2005
Cited by 13
Mingzhu Wei, Elke A. Rundensteiner, Murali Mani · 2015
Because of high volumes and unpredictable arrival rates, stream processing systems cannot always keep up with input data streams, resulting in buffer overflow and uncontrolled loss of data. Load shedding and spilling, the two prevalent technologies designed to solve this overflow problem by dropping or flushing data to disk, suffer from serious shortcomings. Dropping data suffers in that partial output is lost forever, while flushing may waste precious resources due to making the strong assumption that flushed data can and will eventually still be processed. In this paper, we propose our solution, INSURE, integrating structure-based drop and flush techniques within one unified framework for XML stream systems. Our INSURE framework provides an optimized fine-grained load reduction solution that achieves high quality result production. First, the fusion candidate lattice models the space of load reduction solutions incorporating both drop and flush decisions, called fusion candidates. Second, our systematic analysis of fusion candidates and their interrelationships in the fusion candidate lattice reveals important relationships, including the monotonicity of their feasibility and profitability properties. Third, based upon this fusion candidate lattice model, a family of optimization strategies for the selection of fusion candidates is designed to successfully maximize the overall result quality. Experimental results demonstrate that INSURE consistently achieves higher quality results compared to the state-of-the-art techniques, yet with negligible overhead.
Cited by 0
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
Muath Alrammal, Gaétan Hains, Mohamed Zergaoui · HAL (Le Centre pour la Communication Scientifique Directe) · 2009
In this report we present the first experimental results to support our proposal [1] as an attempt to optimize stream processing for XML data. A core prototype called O-Search was implemented to have a concrete understanding for the complexity of stream-querying algorithms i, with respect to different structures of XML documents (wide, depth, various size). Space and time measurements are applied to state the possible performance gains from the use of meta data to orient searching in stream XML data.
Cited by 3Open access
Ranjan K. Dash · UTA ResearchCommons (University of Texas Arlington) · 2012
In recent years, we have witnessed the emergence of new types of systems that deal with large volumes of streaming data. Examples include nancial data analy- sis on feeds of stock tickers, sensor-based environmental monitoring, network tra c monitoring and click stream analysis to push customized advertisements or intrusion detection. Traditional database management systems (DBMS), which are very good at managing large volumes of stored data, fall short of serving this new class of appli- cations, which require low-latency processing on live data from push-based sources. Data Stream Management Systems (DSMS) are fast emerging to address this new type of data and processing requirements. A common but challenging issue in DSMS, is to deal with unpredictable data arrival rate. Data arrival may be fast and bursty at times that surpass available system capability to handle. When input rates exceed system capacity, the Quality of Service (QoS) of system outputs falls below the acceptable levels. The problem of system overloading is more acute in XML data streams than its counterpart in rela- tional streams, as XML streams have to spend extra resources on input processing and result construction. The main focus of this thesis is to nd out suitable ways to process this high volume of data streams dealing with the spikes in data arrival gracefully, under limited or xed system resources in the XML stream context. One established method is to shed load by selectively dropping tuples under these condi- tions. This method helps to improve the observed latency of the results but degrades the answer quality. In this dissertation, we rst de ne the QoS in the context of XML stream pro- cessing and then various mechanisms to improve the QoS, specially the method of load shedding. We provide a general solution framework for implementing Load Shed- ding using Synopses, while minimizing the loss in result accuracy. Then, we present speci c situations where issue of QoS is very critical, such as cases of aggregation and join queries. Finally, we provide techniques to handle load shedding in these cases that provide high QoS in the XML data stream systems. In the nal part of this thesis, we investigate issue of processing aggregation (group-by) join queries on data streams that provide exact results and we extend our solutions to address some of the OLAP issues in data streams.
Cited by 0Open access
Muath Alrammal, HAINS, Gaétan · theses.fr (ABES) · 2011
Plusieurs applications modernes nécessitent un traitement de flux massifs de données XML, cela crée de défis techniques. Parmi ces derniers, il y a la conception et la mise en ouvre d'outils pour optimiser le traitement des requêtes XPath et fournir une estimation précise des coûts de ces requêtes traitées sur un flux massif de données XML. Dans cette thèse, nous proposons un nouveau modèle de prédiction de performance qui estime a priori le coût (en termes d'espace utilisé et de temps écoulé) pour les requêtes structurelles de Forward XPath. Ce faisant, nous réalisons une étude expérimentale pour confirmer la relation linéaire entre le traitement de flux, et les ressources d'accès aux données. Par conséquent, nous présentons un modèle mathématique (fonctions de régression linéaire) pour prévoir le coût d'une requête XPath donnée. En outre, nous présentons une technique nouvelle d'estimation de sélectivité. Elle se compose de deux éléments. Le premier est le résumé path tree: une présentation concise et précise de la structure d'un document XML. Le second est l'algorithme d'estimation de sélectivité: un algorithme efficace de flux pour traverser le synopsis path tree pour estimer les valeurs des paramètres de coût. Ces paramètres sont utilisés par le modèle mathématique pour déterminer le coût d'une requête XPath donnée. Nous comparons les performances de notre modèle avec les approches existantes. De plus, nous présentons un cas d'utilisation d'un système en ligne appelé "online stream-querying system". Le système utilise notre modèle de prédiction de performance pour estimer le coût (en termes de temps / mémoire) d'une requête XPath donnée. En outre, il fournit une réponse précise à l'auteur de la requête. Ce cas d'utilisation illustre les avantages pratiques de gestion de performance avec nos techniques
Cited by 4Open access
Hong Su, Elke A. Rundensteiner, Murali Mani · 2008
Many systems such as Tukwila and YFilter combine automa-ton and algebra techniques to process queries over tokenized XML streams. Typically in this architecture, an automaton is first used to locate all query patterns in the input stream and compose the matched tokens into XML element nodes. These XML nodes are then passed to the tuple-based alge-braic operators for further filtering or restructuring. This common processing style is however not always optimal. At times it is more efficient to retrieve only a subset of the patterns in the automaton while retrieving the rest of the patterns on the XML element nodes. In this paper, we use a cost-based solution to explore this novel optimization op-portunity. We design three plan optimization algorithms, namely, MinExhaust, GreedyBasic and FastPrune. We also study how to migrate from a currently running plan to a new plan in a safe and efficient manner. Our experimentations have shown that the GreedyBasic or FastPrune algorithm can quickly find a plan that is close to optimal in most sce-narios. Also we illustrate that the overhead in our approach for run-time statistics collection and plan migration are very lightweight. 1.
Cited by 0
Samini Subramaniam, Su-Cheng Haw, Lay-Ki Soon et al. · 2016
Cited by 0