LCA-based algorithms for efficiently processing multiple keyword queries over XML streams

详细信息    查看全文

• 作者：Evandrino G. Barros^a ; ^{ebarros@decom.cefetmg.br" class="auth_mail" title="E-mail the corresponding author} ; Alberto H.F. Laender^b ; ^{laender@dcc.ufmg.br" class="auth_mail" title="E-mail the corresponding author} ; Mirella M. Moro^b ; ^{mirella@dcc.ufmg.br" class="auth_mail" title="E-mail the corresponding author} ; Altigran S. da Silva^c ; ^{alti@icomp.ufam.edu.br" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Multi-query processing ; Keyword-based queries ; XML streams ; LCA semantics
• 刊名：Data & Knowledge Engineering
• 出版年：2016
• 出版时间：May 2016
• 年：2016
• 卷：103
• 期：Complete
• 页码：1-18
• 全文大小：1499 K

文摘

In a stream environment, differently from traditional databases, data arrive continuously, unindexed and potentially unbounded, whereas queries must be evaluated for producing results on the fly. In this article, we propose two new algorithms (called SLCAStream and ELCAStream) for processing multiple keyword queries over XML streams. Both algorithms process keyword-based queries that require minimal or no schema knowledge to be formulated, follow the lowest common ancestor (LCA) semantics, and provide optimized methods to improve the overall performance. Moreover, SLCAStream, which implements the smallest LCA (SLCA) semantics, outperforms the state-of-the-art, with up to 49% reduction in response time and 36% in memory usage. In turn, ELCAStream is the first to explore the exclusive LCA (ELCA) semantics over XML streams.

A comprehensive set of experiments evaluates several aspects related to performance and scalability of both algorithms, which shows they are effective alternatives to search services over XML streams.