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

Handling data skew in join algorithms using MapReduce

EXPERT SYSTEMS WITH APPLICATIONS 2016年 51卷 286-299页

作者： Myung, Jaeseok Shim, Junho Yeon, Jongheum Lee, Sang-goo Samsung Elect Co Ltd Corp Design Ctr Seoul South Korea Sookmyung Womens Univ Div Comp Sci Seoul South Korea Seoul Natl Univ Sch Comp Sci & Engn Seoul 151 South Korea Seoul Natl Univ Seoul 151 South Korea

One of the major obstacles hindering effective join processing on MapReduce is data skew. Since MapReduce's basic hash-based partitioning method cannot solve the problem properly, two alternatives have been proposed: range-based and randomized methods. However, they still remain some drawbacks: the range-based method does not handle join product skew, and the randomized method performs worse than the basic hash-based partitioning when input relations are not skewed. In this paper, we present a new skew handling method, called multi-dimensional range partitioning (MDRP). The proposed method overcomes the limitations of traditional algorithms in two ways: 1) the number of output records expected at each, machine is considered, which leads to better handling of join product skew, and 2) a small number of input records are sampled before the actual join begins so that an efficient execution plan considering the degree of data skew can be created. As a result, in a scalar skew experiment, the proposed join algorithm is about 6.76 times faster than the range-based algorithm when join product skew exists and about 5.14 times than the randomized algorithm when input relations are not skewed. Moreover, through the worst-case analysis, we show that the input and the output imbalances are less than or equal to 2. The proposed algorithm does not require any modification to the original MapReduce environment and is applicable to complex join operations such as theta joins and multi-way joins. (C) 2016 Elsevier Ltd. All rights reserved.

关键词： MapReduce join algorithm Skew handling Multi-dimensional range partitioning

来源：评论

学校读者我要写书评

暂无评论

A Cloud-based Storage and Retrieval Solution for RDF Data

A Cloud-based Storage and Retrieval Solution for RDF Data

引用

作者： Sun Yuxiang Yongju Lee School of Computer Science and Engineering Kyungpook National University

In recent years,RDF(Resource Description Framework) has been widely recognized as a standard data storage *** is a real issue that how to store and retrieve RDF data efficiently,because it is the foundation of all semantic-based application *** this paper,we propose a novel storage and retrieval solution based on cloud and R*-*** to existing approaches,we use cloud-based storage approach to compress RDF data,meanwhile R*-tree is adapted to retrieve compressed *** advantage is that it not only reduces the local storage pressure but also improves the retrieval performance compare to existing *** we separate the storage and retrieval and adapt dictionary-based compression approaches,in terms of security and flexibility,our solution is better than existing approaches.

关键词： Cloud-based Storage RDF Compression Linked Data Indexed Approach join algorithm R*-tree Sorted Lists

来源：评论

学校读者我要写书评

暂无评论

Advanced Block Nested Loop join for Extending SSD Lifetime

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2017年第4期29卷 743-756页

作者： Roh, Hongchan Shin, Mincheol Jung, Wonmook Park, Sanghyun SK Telecom Seoul 04539 South Korea Yonsei Univ Dept Comp Sci 134 Shinchon Dong Seoul 04539 South Korea

Flash technology trends have shown that greater densities between flash memory cells increase read/write error rates and shorten solid-state drive (SSD) device lifetimes. This is critical for enterprise systems, causing such problems as service instability and increased total cost of ownership (TCO) because of SSD replacement. Therefore, numerous studies have focused on decreasing the amount of the DBMS writes. However, there has been no research that focused on decreasing the amount of temporary writes, which are primarily created by join processing. In DBMSs, there are two major join-processing algorithms, i.e., hybrid hash join (HHJ) and sort merge join (SMJ), proven to be the best according to DBMS workload;however, the two algorithms produce temporary writes of intermediate results. Therefore, we instead look to the block-nested loop join (BNLJ);it is well-known that the two algorithms are better than BNLJ, but BNLJ creates no intermediate result writes. It is reasonable to use BNLJ for a major join algorithm if its performance can be enhanced similar to those of HHJ and SMJ, considering BNLJ's advantage of extending SSD lifetimes. Therefore, in this paper, we propose an advanced BNLJ (ANLJ) algorithm that can match the performance of the two main join algorithms.

关键词： Query processing join algorithm block nested loop join ANLJ SSD

来源：评论

学校读者我要写书评

暂无评论

Optimizing Distributed join for Array Database System 8

Optimizing Distributed Join for Array Database System

引用

8th International Conference on Information Technology in Medicine and Education (ITME)

作者： Li, Jing Li, Hui Chen, Mei Zhu, Ming Guizhou Univ Guizhou Engn Lab ACMIS Guiyang Guizhou Peoples R China Chinese Acad Sci Natl Astron Observ Beijing Peoples R China

ISBN: (纸本)9781509039067

With the sustained and rapid development of science and technology, the explosion of scientific data for analysis has brought the huge pressure. In order to reduce pressure, scientists use the array database instead of RDBMS to store and manage the scientific data. But according to our experiments, we find that the array database outperforms RDBMS on the simple queries but it can't support the complex multi-table join query very well. And because the network communication is the slowest component of multi-table join queries in distributed parallel databases, we introduce an optimized join algorithm that not only can minimize network communication by optimizing the transfer schedule, but also can reduce the CPU utilization, prevent it to become the bottleneck for the intensive computations. Our evaluation based on real scientific data and database shows the optimized algorithm adapts to diverse datasets and query types and it makes the array database outperforms RDBMS on multi-table queries of real workloads.

关键词： distributed array database join algorithm network overhead CPU cost

来源：评论

学校读者我要写书评

暂无评论

Computing join Queries with Functional Dependencies 16

Computing Join Queries with Functional Dependencies

引用

35th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS)

作者： Khamis, Mahmoud Abo Ngo, Hung Q. Suciu, Dan LogicBlox Inc Atlanta GA 30309 USA SUNY Buffalo Buffalo NY 14260 USA Univ Washington Seattle WA 98195 USA

ISBN: (纸本)9781450341912

Recently, Gottlob, Lee, Valiant, and Valiant (GLVV) presented an output size bound for join queries with functional dependencies (FD), based on a linear program on polymatroids. GLVV bound strictly generalizes the bound of At-serias, Grohe and Marx (AGM) for queries with no FD, in which case there are known algorithms running within the AGM-bound and thus are worst-case optimal. A main result of this paper is an algorithm for computing join queries with FDs, running within GLVV bound up to a poly-log factor. In particular, our algorithm is worst-case optimal for any query where the GLVV bound is tight. As an unexpected by-product, our algorithm manages to solve a harder problem, where (some) input relations may have prescribed maximum degree bounds, of which both functional dependencies and cardinality bounds are special cases. We extend Gottlob et al. framework by replacing all variable subsets with the lattice of closed sets (under the given FDs). This gives us new insights into the structure of the worst-case bound and worst-case instances. While it is still open whether GLVV bound is tight in general, we show that it is tight on distributive lattices and some other simple lattices. Distributive lattices capture a strict superset of queries with no FD and with simple FDs. We also present two simpler algorithms which are also worst-case optimal on distributive lattices within a single-log factor, but they do not match GLVV bound on a general lattice. Our algorithms are designed based on a novel principle: we turn a proof of a polymatroid-based output size bound into an algorithm.

关键词： Worst-case optimal join algorithm Functional dependency Entropy Polymatroid

来源：评论

学校读者我要写书评

暂无评论

FAQ: Questions Asked Frequently 16

FAQ: Questions Asked Frequently

引用

35th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS)

作者： Khamis, Mahmoud Abo Ngo, Hung Q. Rudra, Atri LogicBlox Inc New York NY 10011 USA SUNY Buffalo Buffalo NY 14260 USA SUNY Buffalo Comp Sci & Engn Buffalo NY USA

ISBN: (纸本)9781450341912

We define and study the Functional A ggregate Query (FAQ) problem, which encompasses many frequently asked questions in constraint satisfaction, databases, matrix operations, probabilistic graphical models and logic. This is our main conceptual contribution. We then present a simple algorithm called InsideOut to solve this general problem. InsideOut is a variation of the traditional dynamic programming approach for constraint programming based on variable elimination. Our variation adds a couple of simple twists to basic variable elimination in order to deal with the generality of FAQ, to take full advantage of Grohe and Marx's fractional edge cover framework, and of the analysis of recent worst-case optimal relational join algorithms. As is the case with constraint programming and graphical model inference, to make InsideOut run efficiently we need to solve an optimization problem to compute an appropriate variable ordering. The main technical contribution of this work is a precise characterization of when a variable ordering is 'semantically equivalent' to the variable ordering given by the input FAQ expression. Then, we design an approximation algorithm to find an equivalent variable ordering that has the best 'fractional FAQ-width'. Our results imply a host of known and a few new results in graphical model inference, matrix operations, relational joins, and logic. We also briefly explain how recent algorithms on beyond worst-case analysis for joins and those for solving SAT and #SAT can be viewed as variable elimination to solve FAQ over compactly represented input functions.

关键词： join algorithm Quantified conjunctive query Logic Semiring Probabilistic graphical model Constraint satisfaction

来源：评论

学校读者我要写书评

暂无评论

Integration of Big Data for Connected Cars Applications Based on Tethered Connectivity

Integration of Big Data for Connected Cars Applications Base...

引用

7th International Conference on Emerging Ubiquitous Systems and Pervasive Networks (EUSPN) / 6th International Conference on Current and Future Trends of Information and Communication Technologies in Healthcare (ICTH)

作者： Nkenyereye, Lionel Jang, Jong-wook Dong Eui Univ 176 Eomgwangro Busan 614714 South Korea

The wireless communication technologies built-in or brought in the vehicle enable new in-car telematics services. The development of connected cars emphasizes the use of sophisticated computation framework for gathering, analyzing a large volume of data generated in all aspects of vehicle operations using Big Data technologies. Since these data are essential for many connected cars applications, the design and monitoring of MapReduce algorithms for processing vehicle's data using Hadoop framework will allow to build a hosting of analytics data source. This hosting data source allows different connected cars industry ecosystem to access useful data they need to afford connected cars applications. This paper studies design steps to take in consideration when implementing MapReduce patterns to analyze vehicle's data in order to produce accurate useful data that are hosted at the automakers and connect cars services providers. Experiment results show that MapReduce join algorithm is highly scalable and optimized for distributed computing than Statistical Analysis System (SAS) framework and HiveQL declarative language. (C) 2016 The Authors. Published by Elsevier B.V.

关键词： Connected Car remote on-line vehicle diagnostics system MapReduce framework Hadoop Big data join algorithm

来源：评论

学校读者我要写书评

暂无评论

Integration of Big Data for Connected Cars Applications Based on Tethered Connectivity

引用

Procedia Computer Science 2016年 98卷 554-559页

作者： Lionel Nkenyereye Jong-wook Jang Dong-Eui University 176 EomgwangroBusanjin-Gu Busan614-714 Korea

关键词： Connected Car remote on-line vehicle diagnostics system MapReduce framework Hadoop Big data join algorithm

来源：评论

学校读者我要写书评

暂无评论

Bt-join: A join Operator for Asymmetric Storage Device 15

Bt-Join: A Join Operator for Asymmetric Storage Device

引用

30th ACM Symposium on Applied Computing (SAC)

作者： Evangelista, Neusa L. de Aguiar M. Filho, Jose Brayner, Angelo Alencar, Namom Univ Fortaleza Fortaleza Ceara Brazil

ISBN: (纸本)9781450331968

Nowadays the use of solid state drives (SSDs) is a reality for storing large databases. SSDs are capable to provide IOPS rates up to three orders of magnitude greater than the rates delivered by hard disk drives (HDD). Nonetheless, SSDs presents time asymmetry for executing read/write operations, which poses challenges on the database technology. This is because existing database management systems (DBMS) have been designed by assuming that databases are stored on devices, in which read/write operations are executed in the same amount of time. Thus, we claim that to take full profit from SSD properties, components of DBMS should be aware of read/write asymmetry in SSDs. It is well known that the join operation is the query operator which requires the highest amount of accesses (read/write operations) to the secondary memory. In this paper, we present a new join algorithm, called Bt-join. The key goal of Bt-join is to reduce the amount of write operations during the execution of any join operation R xa S. We have empirically evaluated Bt-join. The results show that the proposed join operator can be up to 50% faster than Flashjoin, a wellknown join operator proposed to be deployed in SSDs.

关键词： asymmetric media database query operator join algorithm

来源：评论

学校读者我要写书评

暂无评论

Low-Latency Handshake join

引用

PROCEEDINGS OF THE VLDB ENDOWMENT 2014年第9期7卷 709-720页

作者： Roy, Pratanu Teubner, Jens Gemulla, Rainer Swiss Fed Inst Technol Dept Comp Sci Syst Grp Zurich Switzerland TU Dortmund Univ Dept Comp Sci DBIS Grp Dortmund Germany Max Planck Inst Informat Saarbrucken Germany

This work revisits the processing of stream joins on modern hardware architectures. Our work is based on the recently proposed handshake join algorithm, which is a mechanism to parallelize the processing of stream joins in a NUMA-aware and hardware-friendly manner. Handshake join achieves high throughput and scalability, but it suffers from a high latency penalty and a non-deterministic ordering of the tuples in the physical result stream. In this paper, we first characterize the latency behavior of the handshake join and then propose a new low-latency handshake join algorithm, which substantially reduces latency without sacrificing throughput or scalability. We also present a technique to generate punctuated result streams with very little overhead;such punctuations allow the generation of correctly ordered physical output streams with negligible effect on overall throughput and latency.

关键词： Computer hardware description languages Hardware Scalability Throughput Hardware architecture High throughput join algorithm Low latency Physical output

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：