检索结果-内蒙古大学图书馆

multi-query optimization for sketch-based estimation

INFORMATION SYSTEMS 2009年第2期34卷 209-230页

作者： Dobra, Alin Garofalakis, Minos Gehrke, Johannes Rastogi, Rajeev Univ Florida Gainesville FL 32611 USA Yahoo Res Santa Clara CA 95054 USA Cornell Univ Ithaca NY 14853 USA Bell Labs Murray Hill NJ 07974 USA

Randomized techniques, based on computing small "sketch" synopses for each stream, have recently been shown to be a very effective tool for approximating the result of a single SQL query over streaming data tuples. In this paper, we investigate the problems arising when data-stream sketches are used to process multiple such queries concurrently. We demonstrate that, in the presence of multiple query expressions, intelligently sharing sketches among concurrent query evaluations can result in substantial improvements in the utilization of the available sketching space and the quality of the resulting approximation error guarantees. We provide necessary and sufficient conditions for multi-query sketch sharing that guarantee the correctness of the result-estimation process. We also investigate the difficult optimization problem of determining sketch-sharing configurations that are optimal (e.g., under a certain error metric for a given amount of space). We prove that optimal sketch sharing typically gives rise to N P-hard questions, and we propose novel heuristic algorithms for finding good sketch-sharing configurations in practice. Results from our experimental study with queries from the TPC-H benchmark verify the effectiveness of our approach, clearly demonstrating the benefits of our sketch-sharing methodology. (c) 2008 Elsevier B.V. All rights reserved.

关键词： Data streaming Sketches Approximate query processing multi-query optimization

来源：评论

学校读者我要写书评

暂无评论

multi-query optimization on RSS Feeds

引用

JOURNAL ON DATA SEMANTICS 2018年第1期7卷 47-64页

作者： Getahun, Fekade Chbeir, Richard Univ Addis Ababa Dept Comp Sci Addis Ababa 1180 Ethiopia Univ Pau & Pays Adour LIUPPA F-64400 Anglet France

RSS feeds are text-content rich, semantically heterogeneous, and contain dynamic XML elements streamed in asynchronous and pull strategies. Hence, for efficient retrieval of RSS feeds, semantic-aware querying operators have been proposed in the literature (Getahun and Chbeir in Inf Sci 237(237):313-342, 2013). However, it is commonly admitted that the use of semantic information would improve, on one hand, the relevance of query result but, on the other hand, at the cost of degrading the efficiency and the performance of the system. To benefit from query execution on semantic information while keeping the efficiency of the system, we propose here a multi-query optimization approach for semantic RSS feed queries. Our approach processes queries by examining the semantic relationship between them and their corresponding windows. It generates a multi-query chain for queries using their window relations for faster execution at runtime. In addition, we propose an operator called quickDrop for semantic load shedding to gracefully decrease irrelevant data load. To validate the proposed approach, we developed a prototype and conducted a set of experiments. The obtained results show that the use of our approach significantly improves the performance of the system.

关键词： Semantic RSS feed query multi-query optimization NAT MQE chain generator Window relationship QuickDrop operator

来源：评论

学校读者我要写书评

暂无评论

multi-query optimization in Federated Databases using Evolutionary Algorithm 14

Multi-Query Optimization in Federated Databases using Evolut...

引用

IEEE 14th International Conference on Machine Learning and Applications ICMLA

作者： Mansha, Sameen Kamiran, Faisal Univ Punjab Informat Technol Lahore Pakistan

ISBN: (纸本)9781509002870

multi query optimization in federated database systems is a well-studied area. Studies have shown that similar problem arises in wide range of applications, e.g., distributed stream processing systems and wireless sensor networks. In this paper, a general distributed multiquery processing problem motivated by the need to speedup data acquisition in federated databases using evolutionary algorithm is studied. We setup a simple framework in which each individual in population is evolved in terms of cost, uniform labeling of hyper edges and validity of resource constraints through a number of generations. Variations of our general problem can be shown to be NP-Hard. Our extensive empirical evaluation over five different synthetic datasets shows a significant improvement of 8 percent in results as compared to the state-of-the-art methods.

关键词： Federated Database multi-query optimization Load balancing Evolutionary Algorithm

来源：评论

学校读者我要写书评

暂无评论

multi-query optimization in Wide-Area Streaming Analytics

Multi-Query Optimization in Wide-Area Streaming Analytics

引用

ACM Symposium on Cloud Computing (SoCC)

作者： Jonathan, Albert Chandra, Abhishek Weissman, Jon Univ Minnesota Twin Cities Minneapolis MN 55455 USA

ISBN: (纸本)9781450360111

Wide-area data analytics has gained much attention in recent years due to the increasing need for analyzing data that are geographically distributed. Many of such queries often require real-time analysis on data streams that are continuously being generated across multiple locations. Yet, analyzing these geo-distributed data streams in a timely manner is very challenging due to the highly heterogeneous and limited bandwidth availability of the wide-area network (WAN). This paper examines the opportunity of applying multi-query optimization in the context of wide-area streaming analytics, with the goal of utilizing WAN bandwidth efficiently while achieving high throughput and low latency execution. Our approach is based on the insight that many streaming analytics queries often exhibit common executions, whether in consuming a common set of input data or performing the same data processing. In this work, we study different types of sharing opportunities and propose a practical online algorithm that allows streaming analytics queries to share their common executions incrementally. We further address the importance of WAN awareness in applying multi-query optimization. Without WAN awareness, sharing executions in a wide-area environment may lead to performance degradation. We have implemented our WAN-aware multi-query optimization in a prototype implementation based on Apache Flink. Experimental evaluation using Twitter traces on a real wide-area system deployment across geo-distributed EC2 data centers shows that our technique is able to achieve 21% higher throughput while saving WAN bandwidth consumption by 33% compared to a WAN-aware, sharing-agnostic system.

关键词： Geo-distributed systems stream processing systems multi-query optimization execution sharing

来源：评论

学校读者我要写书评

暂无评论

multi-query optimization of sliding window aggregates by schedule synchronization 06

Multi-query optimization of sliding window aggregates by sch...

引用

15th ACM Conference on Information and Knowledge Management, CIKM 2006

作者： Golab, Lukasz Bijay, Kumar Gaurav Zsu, M. Tamer University of Waterloo Canada Indian Inst. of Tech. Bombay India AT and T Labs. Florham Park NJ United States

No abstract available

ISBN: (纸本)1595934332

No abstract available

关键词： data streams multi-query optimization persistent queries sliding windows

来源：评论

学校读者我要写书评

暂无评论

Exploiting coarse-grained reused-based opportunities in Big Data multi-query optimization

引用

JOURNAL OF COMPUTATIONAL SCIENCE 2018年 26卷 432-452页

作者： Sahal, Radhya Khafagy, Mohamed H. Omara, Fatma A. Cairo Univ Fac Comp & Informat Dept Comp Sci Giza Egypt Cairo Univ Fac Comp & Informat Giza Egypt Fayoum Univ Fac Comp & Informat Dept Comp Sci Faiyum Egypt

multi-query optimization in Big Data becomes a promising research direction due to the popularity of massive data analytical systems (e.g., MapReduce and Flink). The multi-query is translated into jobs. These jobs are routinely submitted with similar tasks to the underling Big Data analytical systems. These similar tasks are considered complicated and computation overhead. Therefore, there are some existing techniques that have been proposed for exploiting sharing tasks in Big Data multi-query optimization (e.g., MRShare and Relaxed MRShare). These techniques are heavily tailored relaxed optimizing factors of fine-grained reused-based opportunities. In accordance with Big Data multi-query optimization, the existing fine-grained techniques are only concerned with equal tuples size and uniform data distribution. These issues are not applicable to the real-world distributed applications which depend on coarse-grained reused-based opportunities, such as non-equal tuples size and non-uniform data distribution. These two issues receive more-attention in Big Data multi-query optimization, to minimize the data read from or written back to Big Data infrastructures (e.g., Hadoop). In this paper, multi-query optimization using Tuple Size and Histogram (MOTH) system has been proposed to consider the granularity of the reused-based opportunities. The proposed MOTH system exploits the coarse-grained of the fully and partially reused-based opportunities among queries with considering non-equal tuples size and non-uniform data distribution to avoid repeated computations. According to the proposed MOTH system, a combined technique has been introduced for estimating the coarse-grained reused-based opportunities horizontally and vertically. The horizontal estimation of non-equal tuples size has been done by extracting metadata in column-level, while the vertical estimation of non-uniform data distribution is concerned with using pre-computed histogram in row-level. In addition, the MO

关键词： Big Data multi-query optimization Coarse-grained Sharing opportunity Reused-based

来源：评论

学校读者我要写书评

暂无评论

Exploiting Shared Sub-Expression and Materialized View Reuse for multi-query optimization

引用

INFORMATION SYSTEMS FRONTIERS 2024年 1-16页

作者： Gurumurthy, Bala Bidarkar, Vasudev Raghavendra Broneske, David Pionteck, Thilo Saake, Gunter Otto Von Guericke Univ Magdeburg Germany German Ctr Higher Educ Res & Sci Studies Hannover Germany

querying in isolation lacks the potential of reusing intermediate results, which ends up wasting computational resources. multi-query optimization (MQO) addresses this challenge by devising a shared execution strategy across queries, with two generally used strategies: batched or cached. These strategies are shown to improve performance, but hardly any study explores the combination of both. In this work we explore such a hybrid MQO, combining batching (Shared Sub-Expression) and caching (Materialized View Reuse) techniques. Our hybrid-MQO system merges batched query results as well as caches the intermediate results, thereby any new query is given a path within the previous plan as well as reusing the results. Since caching is a key component for improving performance, we measure the impact of common caching techniques such as FIFO, LRU, MRU and LFU. Our results show LRU to be the optimal for our usecase, which we use in our subsequent evaluations. To study the influence of batching, we vary the factor - derivability - which represents the similarity of the results within a query batch. Similarly, we vary the cache sizes to study the influence of caching. Moreover, we also study the role of different database operators in the performance of our hybrid system. The results suggest that, depending on the individual operators, our hybrid method gains a speed-up between 4x to a slowdown of 2x from using MQO techniques in isolation. Furthermore, our results show that workloads with a generously sized cache that contain similar queries benefit from using our hybrid method, with an observed speed-up of 2x over sequential execution in the best case.

关键词： multi-query optimization Batched query execution Materialized view reuse Caching policies MQO

来源：评论

学校读者我要写书评

暂无评论

Continuous multi-query optimization for subgraph matching over dynamic graphs

引用

SEMANTIC WEB 2022年第4期13卷 601-622页

作者： Wang, Xi Zhang, Qianzhen Guo, Deke Zhao, Xiang Univ Def Technol Sci & Technol Informat Syst Engn Lab Changsha Peoples R China Tianjin Univ Coll Intelligence & Comp Tianjin Key Lab Adv Networking Tank Tianjin Peoples R China

There is a growing need to perform real-time analytics on dynamic graphs in order to deliver the values of big data to users. An important problem from such applications is continuously identifying and monitoring critical patterns when fine-grained updates at a high velocity occur on the graphs. A lot of efforts have been made to develop practical solutions for these problems. Despite the efforts, existing algorithms showed limited running time and scalability in dealing with large and/or many graphs. In this paper, we study the problem of continuous multi-query optimization for subgraph matching over dynamic graph data. (1) We propose annotated query graph, which is obtained by merging the multi-queries into one. (2) Based on the annotated query, we employ a concise auxiliary data structure to represent partial solutions in a compact form. (3) In addition, we propose an efficient maintenance strategy to detect the affected queries for each update and report corresponding matches in one pass. (4) Extensive experiments over real-life and synthetic datasets verify the effectiveness and efficiency of our approach and confirm a two orders of magnitude improvement of the proposed solution.

关键词： multi-query optimization annotated query graph incremental maintenance strategy dynamic graph

来源：评论

学校读者我要写书评

暂无评论

Comparative Study of multi-query optimization Techniques using Shared Predicate-based for Big Data

引用

INTERNATIONAL JOURNAL OF GRID AND DISTRIBUTED COMPUTING 2016年第5期9卷 229-240页

作者： Sahal, Radhya Khafagy, Mohamed H. Omara, Fatma A. Cairo Univ Fac Comp & Informat Dept Comp Sci Cairo Egypt Fayoum Univ Fac Comp & Informat Dept Comp Sci Faiyum Egypt

Big data analytical systems, such as MapReduce, have become main issues for many enterprises and research groups. Currently, multi-query which translated into MapReduce jobs is submitted repeatedly with similar tasks. So, exploiting these similar tasks can offer possibilities to avoid repeated computations of MapReduce jobs. Therefore, many researches have addressed the sharing opportunity to optimize multi query processing. Consequently, the main goal of this work is to study and compare comprehensively two existed sharing opportunity techniques using predicate-based filters;MRShare and relaxed MRShare. The comparative study has been performed over TPC-H benchmark and confirmed that the relaxed MRShare technique significantly outperforms the MRShare for shared data in terms of predicate-based filters among multi-query.

关键词： Big data MapReduce Sharing Opportunity multi-query optimization filter predicates

来源：评论

学校读者我要写书评

暂无评论

RDF multi-query optimization Algorithm for query Rewriting Using Common Subgraphs 19

RDF Multi-query Optimization Algorithm for Query Rewriting U...

引用

3rd International Conference on Computer Science and Application Engineering (CSAE)

作者： Wang, Manzi Fu, Haidong Xu, Fangfang Wuhan Univ Sci & Technol Sch Comp Sci & Technol Wuhan 430065 Peoples R China

ISBN: (纸本)9781450362948

In the current trend of rapid development of big data, there are frequent application scenarios of high concurrent query processing on RDF data sets. The multi-query optimization scheme for solving concurrent queries needs to provide a global approximate optimal solution for the query set composed of a set of queries, so as to minimize the overall time cost of the query set. Under the premise of accelerating statistics by RDF storage index and narrowing the scope of semantic pruning, firstly, simplified multiple queries are converted into connection graphs, and then all queries are clustered and grouped. In each group, all common subgraphs of connection graphs are iteratively searched and mapping tables are established. Then, the common subgraph is arranged in descending order by the number of vertices to construct the query rewriting scheme. Finally, for all the rewritten queries, the dynamic programming algorithm based on selection rate estimation is used for secondary optimization. On the one hand, the common subgraph is used to rewrite the query to reduce the number of queries, so as to reduce the cost through the reusable common result set. On the other hand, because of the establishment of RDF storage index, the selection rate can be estimated quickly, and the rewritten queries can be optimized again to improve the overall query efficiency. The experimental results show that the proposed algorithm has better query performance than the existing query schemes, especially when the RDF dataset is large, the number of queries in the query set is large, and the query statements are complex, the multi-query optimization method in this paper works better.

关键词： Common Subgraph query Rewrite Selection Rate Estimation multi-query optimization

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：