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

RRPJ: Result-rate based progressive relational join

12th International Conference on Database Systems for Advanced Applications

作者： Tok, Wee Hyong Bressan, Stephane Lee, Mong-Li Natl Univ Singapore Sch Comp Singapore 117548 Singapore

ISBN: (纸本)9783540717027

Progressive join algorithms are join algorithms that produce results incrementally as input data is available. Because they are non-blocking, they are particularly suitable for online processing of data streams. Reference algorithms of this family are the symmetric hash join, the X-join and more recently, the rate-based progressive join (RPJ). While the symmetric hash join introduces the idea of a symmetric processing of the input streams but assumes sufficient main memory, the X-join suggests that the processing can scale to very large amounts of data if main memory is regularly flushed to disk, and a reactive/cleanup phase is triggered for disk-resident data. The X-join flushing strategy is based on a simple largest-first strategy, where the largest partition is flushed to disk. The recently proposed RPJ predicts the main memory tuples or partitions that should be flushed to disk in order to maximize throughput by computing their probabilities to contribute to a result. In this paper, we discuss the limitations of RPJ and propose a novel extension, called Result Rate-based Progressive join (RRPJ), which addresses these limitations. Instead of computing the probabilities from statistics over the input data, RRPJ directly observes the output (result) statistics. This not only yields a better performance, but also simplifies the generalization of the algorithm to non-relational data such as multidimensional data and hierarchical data. We empirically show that RRPJ is effective and efficient and outperforms the state-of-art RPJ. We also investigate the relevance and performance of an adaptive version of these algorithms using amortization parameters.

关键词： query processing join algorithms data streams

来源：评论

学校读者我要写书评

暂无评论

Plexus: Optimizing join Approximation for Geo-Distributed Data Analytics 14

Plexus: Optimizing Join Approximation for Geo-Distributed Da...

引用

14th Annual ACM Symposium on Cloud Computing (SoCC)

作者： Wolfrath, Joel Chandra, Abhishek Univ Minnesota Minneapolis MN 55417 USA

ISBN: (纸本)9798400703874

Modern applications are increasingly generating and persisting data across geo-distributed data centers or edge clusters rather than a single cloud. This paradigm introduces challenges for traditional query execution due to increased latency when transferring data over wide-area network links. join queries in particular are heavily affected, due to their large output size and amount of data that must be shuffled over the network. join sampling-computing a uniform sample from the join results-is a useful technique for reducing resource requirements. However, applying it to a geo-distributed setting is challenging, since acquiring independent samples from each location and joining on the samples does not produce uniform and independent tuples from the join result. To address these challenges, we first generalize an existing join sampling algorithm to the geo-distributed setting. We then present our system, Plexus, which introduces three additional optimizations to further reduce the network overhead and handle network and data heterogeneity: (i) weight approximation, (ii) heterogeneity awareness and (iii) sample prefetching. We evaluate Plexus on a geo-distributed system deployed across multiple AWS regions, with an implementation based on Apache Spark. Using three real-world datasets, we show that Plexus can reduce query latency by up to 80% over the default Spark join implementation on a wide class of join queries without substantially impacting sample uniformity.

关键词： join algorithms Distributed Systems Query Optimization Wide Area Network

来源：评论

学校读者我要写书评

暂无评论

join algorithm costs revisited

引用

VLDB Journal 1996年第1期5卷 64-84页

作者： Harris, Evan P. Ramamohanarao, Kotagiri Department of Computer Science University of Melbourne Parkville Vic. 3052 Australia University of Melbourne

A method of analysing join algorithms based upon the time required to access, transfer and perform the relevant CPU-based operations on a disk page is proposed. The costs of variations of several of the standard join algorithms, including nested block, sort-merge, GRACE hash and hybrid hash, are presented. For a given total buffer size, the cost of these join algorithms depends on the parts of the buffer allocated for each purpose. For example, when joining two relations using the nested block join algorithm, the amount of buffer space allocated for the outer and inner relations can significantly affect the cost of the join. Analysis of expected and experimental results of various join algorithms show that a combination of the optimal nested block and optimal GRACE hash join algorithms usually provide the greatest cost benefit, unless the relation size is a small multiple of the memory size. algorithms to quickly determine a buffer allocation producing the minimal cost for each of these algorithms are presented. When the relation size is a small multiple of the amount of main memory available (typically up to three to six times), the hybrid hash join algorithm is preferable. © Springer-Verlag 1996.

关键词： join algorithms Minimisation Optimal buffer allocation

来源：评论

学校读者我要写书评

暂无评论

Authenticated join Processing in Outsourced Databases

Authenticated Join Processing in Outsourced Databases

引用

35th ACM SIGMOD Conference

作者： Yang, Yin Papadias, Dimitris Papadopoulos, Stavros Kalnis, Panos Hong Kong Univ Sci & Technol Dept Comp Sci & Engn Hong Kong Hong Kong Peoples R China

ISBN: (纸本)9781605585543

Database outsourcing requires that a query server constructs a proof of result correctness, which can be verified by the client using the data owner's signature. Previous authentication techniques deal with range queries on a single relation using an authenticated data structure (ADS). On the other hand, authenticated join processing is inherently more complex than ranges since only the base relations (but not their combination) are signed by the owner. In this paper, we present three novel join algorithms depending on the ADS availability: (i) Authenticated Indexed Sort Merge join (AISM), which utilizes a single ADS on the join attribute, (ii) Authenticated Index Merge join (AIM) that requires an ADS (on the join attribute) for both relations, and (iii) Authenticated Sort Merge join (ASM), which does not rely on any ADS. We experimentally demonstrate that the proposed methods outperform two benchmark algorithms, often by several orders of magnitude, on all performance metrics, and effectively shift the workload to the outsourcing service. Finally, we extend our techniques to complex queries that combine multi-way joins with selections and projections.

关键词： Database Outsourcing join algorithms Query Authentication

来源：评论

学校读者我要写书评

暂无评论

OPTIMIZATION STRATEGIES FOR RELATIONAL DISJUNCTIVE QUERIES

引用

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING 1989年第10期15卷 1217-1235页

作者： CIACCIA, P SCALAS, MR UNIV BOLOGNA DEPT ELECTR COMP SCI & SYSTI-40136 BOLOGNAITALY UNIV TRIESTE DIPARTIMENTO MATEMAT APPL SCI ECON STAT ATTURIALII-34127 TRIESTEITALY UNIV BOLOGNA CNRCIOCI-40136 BOLOGNAITALY

The main purpose of this work is to extend the processing capabilities of the optimizer of a relational DBMS in order to effectively include the treatment of disjunctive queries. To this aim two new strategies are presented, whose main features are based on the application of splitting techniques during the execution of the join operations. Their effectiveness is first shown by means of an example; then some comparisons with standard procedures are made, showing promising results. The inclusion of these techniques in the relational query processing environment requires a broader view of the evaluation phase, where more than one expression can now be present. A heuristic algorithm for the reduction of the number of candidate relational expressions is also proposed. [ABSTRACT FROM AUTHOR]

关键词： Disjunctive expressions join algorithms query models query optimization relational databases

来源：评论

学校读者我要写书评

暂无评论

OPTIMIZING THE COST OF RELATIONAL QUERIES USING PARTIAL-RELATION SCHEMES

引用

INFORMATION SYSTEMS 1988年第1期13卷 71-79页

作者： PRAMANIK, S FOTOUHI, F United States

In this paper we propose a new access path to a relation, called a Partial-Relation scheme, in order to speed up the relational join operations. We present two join algorithms which preprocess the Partial-Relations first and then join the selected tuples of the relations. We have considered join-only queries and queries involving restrictions, projections and joins. The performance of these algorithms is compared with sort-merge and hash-based join algorithms. The analysis is based on the cost of accesses to the secondary storage and the CPU usage. It has been shown that for wide range of selectivity factors and/or join factors the proposed algorithms perform better than the sort-merge and hash-based join algorithms.

关键词： join algorithms hybrid-hash semijoin Partial-Relations

来源：评论

学校读者我要写书评

暂无评论

Delaunay based algorithm for finding polygonal voids in planar point sets

引用

ASTRONOMY AND COMPUTING 2018年 22卷 48-62页

作者： Alonso, R. Ojeda, J. Hitschfeld, N. Hervias, C. Campusano, L. E. Univ Chile Dept Comp Sci Fac Phys & Math Sci Santiago Chile Univ Chile Astron Dept Fac Phys & Math Sci Santiago Chile

This paper presents a new algorithm to find under-dense regions called voids inside a 2D point set. The algorithm starts from terminal-edges (local longest-edges) in a Delaunay triangulation and builds the largest possible low density terminal-edge regions around them. A terminal-edge region can represent either an entire void or part of a void (subvoid). Using artificial data sets, the case of voids that are detected as several adjacent subvoids is analyzed and four subvoid joining criteria are proposed and evaluated. Since this work is inspired on searches of a more robust, effective and efficient algorithm to find 3D cosmological voids the evaluation of the joining criteria considers this context. However, the design of the algorithm permits its adaption to the requirements of any similar application. (c) 2018 Elsevier B.V. All rights reserved.

关键词： Mesh geometry models join algorithms Data analysis Large-scale structure of universe

来源：评论

学校读者我要写书评

暂无评论

Optimizing database architecture for the new bottleneck: memory access

引用

VLDB JOURNAL 2000年第3期9卷 231-246页

作者： Manegold, S Boncz, PA Kersten, ML CWI NL-1098 SJ Amsterdam Netherlands Data Distilleries BV NL-1098 SM Amsterdam Netherlands

In the past decade, advances in the speed of commodity CPUs have far out-paced advances in memory latency. Main-memory access is therefore increasingly a performance bottleneck for many computer applications, including database systems, in this article, we use a simple scan test to show the severe impact of this bottleneck. The insights gained are translated into guidelines for database architecture, in terms of both data structures and algorithms. We discuss how vertically fragmented data structures optimize cache performance on sequential data access. We then focus on equi-join, typically a random-access operation, and introduce radix algorithms for partitioned hash-join. The performance of these algorithms is quantified using a detailed analytical model that incorporates memory access cost. Experiments that validate this model were performed on the Monet database system. We obtained exact statistics on events such as TLB misses and L1 and L2 cache misses by using hardware performance counters found in modern CPUs. Using our cost model, we show how the carefully tuned memory access pattern of our radix algorithms makes them perform well, which is confirmed by experimental results.

关键词： main-memory databases query processing memory access optimization decomposed storage model join algorithms implementation techniques

来源：评论

学校读者我要写书评

暂无评论

Bloom filter and its variants for the optimization of MapReduce's algorithms: A review 5

Bloom filter and its variants for the optimization of MapRed...

引用

5th International Conference on Cloud Computing and Artificial Intelligence - Technologies and Applications (CloudTech)

作者： Ezzaki, F. Abghour, N. Elomri, A. Moussaid, K. Rida, M. Univ Hassan 2 Lab Informat Modelisat Syst & Aide Decis LIMSAD Fac Sci Dept Math & Informat Casablanca Morocco

ISBN: (纸本)9781728161754

The bloom filter is a probabilistic data model used to test the existence of an element in a set, i.e., for any given item, the bloom filter could test the membership query on this candidate. The bloom filter has many advantages due to its simplicity and efficiency in highly solving the issue of data representation in many fields and to support membership queries, it has been known as space and time-efficient randomized data structure, by filtering out redundant data and optimizing the memory consumption. However, bloom filters are limited to membership tests and don't support the deletion of elements. They also generate the false positive probability as they are based on a probabilistic model, this error rate is generated when an element that doesn't belong to a set is considered as a member of this set by the bloom filter. Our goal is to compare a number of well- existed algorithms related to the boom filter for future work on the optimization of the join's algorithms in MapReduce. This paper provides an overview of the different variants of the bloom filter and analyses the studies that have been interested in this area of research.

关键词： big data storage optimization bloom filter cuckoo filter membership data structure join algorithms mapreduce

来源：评论

学校读者我要写书评

暂无评论

Compressed Representations of Conjunctive Query Results 37

Compressed Representations of Conjunctive Query Results

引用

37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS)

作者： Deep, Shaleen Koutris, Paraschos Univ Wisconsin Madison WI 53706 USA

ISBN: (纸本)9781450347068

Relational queries, and in particular join queries, often generate large output results when executed over a huge dataset. In such cases, it is often infeasible to store the whole materialized output if we plan to reuse it further down a data processing pipeline. Motivated by this problem, we study the construction of space-efficient compressed representations of the output of conjunctive queries, with the goal of supporting the efficient access of the intermediate compressed result for a given access pattern. In particular, we initiate the study of an important tradeoff: minimizing the space necessary to store the compressed result, versus minimizing the answer time and delay for an access request over the result. Our main contribution is a novel parameterized data structure, which can be tuned to trade off space for answer time. The tradeoff allows us to control the space requirement of the data structure precisely, and depends both on the structure of the query and the access pattern. We show how we can use the data structure in conjunction with query decomposition techniques in order to efficiently represent the outputs for several classes of conjunctive queries.

关键词： Query enumeration Compressed representation Space delay tradeoff join algorithms Constant delay enumeration

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：