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

GPU-based efficient join algorithms on Hadoop

JOURNAL OF SUPERCOMPUTING 2021年第1期77卷 292-321页

作者： Wang, Hongzhi Li, Ning Wang, Zheng Li, Jianing Harbin Inst Technol POB 750 Harbin Peoples R China

The growing data have brought tremendous pressure for query processing and storage, so there are many studies that focus on using GPU to accelerate join operation, which is one of the most important operations in modern database systems. However, existing GPU acceleration join operation researches are not very suitable for the join operation on big data. Based on this, this paper speeds up nested loop join, hash join and theta join, combining Hadoop with GPU, which is also the first to use GPU to accelerate theta join. At the same time, after the data pre-filtering and pre-processing, using MapReduce and HDFS in Hadoop proposed in this paper, the larger data table can be handled, compared to existing GPU acceleration methods. Also with MapReduce in Hadoop, the algorithm proposed in this paper can estimate the number of results more accurately and allocate the appropriate storage space without unnecessary costs, making it more efficient. Experimental results show that comparing with GPU-based approach without Hadoop, our approach increases the speed by 1.5-2 times, and comparing with the Hadoop-based approaches without GPU, our approach increases the speed by 1.3-2 times.

关键词： GPU Hadoop join algorithm

来源：评论

学校读者我要写书评

暂无评论

Internal and external memory set containment join (Feb, 10.1007/s00778-020-00644-3, 2021)

引用

VLDB JOURNAL 2021年第5期30卷 907-907页

作者： Yang, Chengcheng Deng, Dong Shang, Shuo Zhu, Fan Liu, Li Shao, Ling Univ Elect Sci & Technol China Chengdu Peoples R China Rutgers State Univ New Brunswick NJ 08854 USA Incept Inst Artificial Intelligence Abu Dhabi U Arab Emirates

A set containment join operates on two set-valued attributes with a subset (\(\subseteq \)) relationship as the join condition. It has many real-world applications, such as in publish/subscribe services and inclusion dependency discovery. Existing solutions can be broadly classified into union-oriented and intersection-oriented methods. Based on several recent studies, union-oriented methods are not competitive as they involve an expensive subset enumeration step. Intersection-oriented methods build an inverted index on one attribute and perform inverted list intersection on another attribute. Existing intersection-oriented methods intersect inverted lists one-by-one. In contrast, in this paper, we propose to intersect all the inverted lists simultaneously while skipping many irrelevant entries in the lists. To share computation, we utilize the prefix tree structure and extend our novel list intersection method to operate on the prefix tree. To further improve the efficiency, we propose to partition the data and process each partition separately. Each partition will be associated with a much smaller inverted index, and the set containment join cost can be significantly reduced. Moreover, to support large-scale datasets that are beyond the available memory space, we develop a novel adaptive data partition method that is designed to fully leverage the available memory and achieve high I/O efficiency, and thereby exhibiting outstanding performance for external memory set containment join. We evaluate our methods using both real-world and synthetic datasets. Experimental results demonstrate that our method outperforms state-of-the-art methods by up to 10\(\times \) when the dataset is completely resided in memory. Furthermore, our approach achieves up to two orders of magnitude improvement on I/O efficiency compared with a baseline method when the dataset size exceeds the main memory space.

关键词： Set containment Containment join Query processing join algorithm Similarity join

来源：评论

学校读者我要写书评

暂无评论

join algorithms under Apache Spark: Revisited 19

Join Algorithms under Apache Spark: Revisited

引用

5th International Conference on Computer and Technology Applications (ICCTA)

作者： Al-Badarneh, Amer Jordan Univ Sci & Technol Comp Informat Syst Dept Irbid 22110 Jordan

ISBN: (纸本)9781450371810

Currently, we are dealing with large scale applications, which in turn generate massive amount of data and information. Large amount of data often requires processing algorithms using massive parallelism, where the main performance metrics is the communication cost. Apache Spark is highly scalable, fault-tolerance, and can be used across many computers. So join algorithm is one of the most widely used algorithms in database systems, but it is also a heavily time consuming operation. In this work, we will survey and criticize several implementations of Spark join algorithms and discuss their strengths and weaknesses, present a detailed comparison of these algorithms, and introduce optimization approaches to enhance and tune the performance of join algorithms.

关键词： Mapreduce join algorithm Apache Spark Hadoop

来源：评论

学校读者我要写书评

暂无评论

Load balancing in join algorithms for skewed data in MapReduce systems

引用

JOURNAL OF SUPERCOMPUTING 2019年第1期75卷 228-254页

作者： Gavagsaz, Elaheh Rezaee, Ali Javadi, Hamid Haj Seyyed Islamic Azad Univ Sci & Res Branch Dept Comp Engn Tehran Iran Shahed Univ Fac Math & Comp Sci Dept Appl Math Tehran Iran

join is an essential tool for data analysis which collected from different data sources. MapReduce has emerged as a prominent programming model for processing of massive data. However, traditional join algorithms based on MapReduce are not efficient when handling skewed data. The presence of data skew in input data leads to considerable load imbalance and performance degradation. This paper proposes a new skew-insensitive method, called fine-grained partitioning for skew data (FGSD) which can improve the load balancing for reduce tasks. The proposed method considers the properties of both input and output data through a proposed stream sampling algorithm. FGSD introduces a new approach for distribution of input data which leads to efficiently handling redistribution and join product skew. The experimental results confirm that our solution can not only achieve higher balancing performance, but also reduce the execution time of a job with varying degrees of the data skew. Furthermore, FGSD does not require any modification to the MapReduce environment and is applicable to complex join.

关键词： Load balancing join algorithm Data skew MapReduce Spark

来源：评论

学校读者我要写书评

暂无评论

Secure Yannakakis: join-Aggregate Queries over Private Data 21

Secure Yannakakis: Join-Aggregate Queries over Private Data

引用

ACM SIGMOD International Conference on Management of Data (SIGMOD)

作者： Wang, Yilei Yi, Ke Hong Kong Univ Sci & Technol Hong Kong Peoples R China

ISBN: (纸本)9781450383431

In this paper, we describe a secure version of the classical Yannakakis algorithm for computing free-connex join-aggregate queries. This protocol can be used in the secure two-party computation model, where the parties would like to evaluate a query without revealing their own data. Our protocol presents a dramatic improvement over the state-of-the-art protocol based on Yao's garbled circuit. In theory, its cost (both running time and communication) is linear in data size and polynomial in query size, whereas that of the garbled circuit is polynomial in data size and exponential in query size. This translates to a reduction in running time in practice from years to minutes, as tested on a number of TPC-H queries of varying complexity.

关键词： query processing join algorithm secure multi-party computation

来源：评论

学校读者我要写书评

暂无评论

Freshjoin: An Efficient and Adaptive algorithm for Set Containment join

引用

DATA SCIENCE AND ENGINEERING 2019年第4期4卷 293-308页

作者： Luo, Jizhou Zhang, Wei Shi, Shengfei Gao, Hong Li, Jianzhong Wu, Wei Jiang, Shouxu Harbin Inst Technol Sch Comp Sci & Technol Harbin Peoples R China

This paper revisits set containment join (SCJ) problem, which uses the subset relationship (i.e., subset of) as condition to join set-valued attributes of two relations and has many fundamental applications in commercial and scientific fields. Existing in-memory algorithms for SCJ are either signature-based or prefix-tree-based. The former incurs high CPU cost because of the enumeration of signatures, while the latter incurs high space cost because of the storage of prefix trees. This paper proposes a new adaptive parameter-free in-memory algorithm, named as frequency-hashjoin or Freshjoin in short, to evaluate SCJ efficiently. Freshjoin builds a flat index on-the-fly to record three kinds of signatures (i.e., two least frequent elements and a hash signature whose length is determined adaptively by the frequencies of elements in the universe set). The index consists of two sparse inverted indices and two arrays which record hash signatures of all sets in each relation. The index is well organized such that Freshjoin can avoid enumerating hash signatures. The rationality of this design is explained. And, the time and space cost of the proposed algorithm, which provide a rule to choose Freshjoin from existing algorithms, are analyzed. Experiments on 16 real-life datasets show that Freshjoin usually reduces more than 50% of space cost while remains as competitive as the state-of-the-art algorithms in running time.

关键词： Set containment join Frequency hash join algorithm

来源：评论

学校读者我要写书评

暂无评论

O2ijoin： An Efficient Index-Based algorithm for Overlap Interval join

引用

Journal of Computer Science & Technology 2018年第5期33卷 1023-1038页

作者： Ji-Zhou Luo Sheng-Fei Shi Guang Yang Hong-Zhi Wang Jian-Zhong Li School of Computer Science and Technology Harbin Institute of Technology Harbin 150001 China Guangdong Key Laboratory of Popular High Performance Computers Key Laboratory of Service Computing and Application Shenzhen 518000 China

Time intervals are often associated with tuples to represent their valid time in temporal relations, where overlap join is crucial for various kinds of queries. Many existing overlap join algorithms use indices based on tree structures such as quad-tree, B＋-tree and interval tree. These algorithms usually have high CPU cost since deep path traversals are unavoidable, which makes them not so competitive as data-partition or plane-sweep based algorithms. This paper proposes an efficient overlap join algorithm based on a new two-layer flat index named as Overlap Interval Inverted Index （i.e., O2i Index）. It uses an array to record the end points of intervals and approximates the nesting structures of intervals via two functions in the first layer, and the second layer uses inverted lists to trace all intervals satisfying the approximated nesting structures. With the help of the new index, the join algorithm only visits the must-be-scanned lists and skips all others. Analyses and experiments on both real and synthetic datasets show that the proposed algorithm is as competitive as the state-of-the-art algorithms.

关键词： overlap interval join temporal relation overlap inverted index join algorithm

来源：评论

学校读者我要写书评

暂无评论

Worst-Case Optimal join algorithms: Techniques, Results, and Open Problems 37

Worst-Case Optimal Join Algorithms: Techniques, Results, and...

引用

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

作者： Ngo, Hung Q. RelationalAI Inc Buffalo NY USA

ISBN: (纸本)9781450347068

Worst-case optimal join algorithms are the class of join algorithms whose runtime match the worst-case output size of a given join query. While the first provably worse-case optimal join algorithm was discovered relatively recently, the techniques and results surrounding these algorithms grow out of decades of research from a wide range of areas, intimately connecting graph theory, algorithms, information theory, constraint satisfaction, database theory, and geometric inequalities. These ideas are not just paperware: in addition to academic project implementations, two variations of such algorithms are the work-horse join algorithms of commercial database and data analytics engines. This paper aims to be a brief introduction to the design and analysis of worst-case optimal join algorithms. We discuss the key techniques for proving runtime and output size bounds. We particularly focus on the fascinating connection between join algorithms and information theoretic inequalities, and the idea of how one can turn a proof into an algorithm. Finally, we conclude with a representative list of fundamental open problems in this area.

关键词： Worst-case optimal join algorithm entropy polymatroid inequality

来源：评论

学校读者我要写书评

暂无评论

Dynamic asymmetric group key agreement protocol with traitor traceability

引用

IET INFORMATION SECURITY 2019年第6期13卷 703-710页

作者： Teng, Jikai Ma, Hongyang Qingdao Univ Technol Sch Sci Qingdao 266003 Shadong Peoples R China

In asymmetric group key agreement (ASGKA) protocols, a group of users establish a common encryption key which is publicly accessible and compute pairwise different decryption keys. It is left as an open problem to design an ASGKA protocol with traitor traceability in Eurocrypt 2009. A one-round dynamic authenticated ASGKA protocol with public traitor traceability is proposed in this study. It provides a black-box tracing algorithm. Ind-CPA security with key compromise impersonation resilience (KCIR) and forward secrecy of ASGKA protocols is formally defined. The proposed protocol is proved to be Ind-CPA secure with KCIR and forward secrecy under D k-HDHE assumption. It is also proved that the proposed protocol resists collusion attack. In Setup algorithm and join algorithm, one communication round is required. In Leave algorithm, no message is required to be transmitted. The proposed protocol adopts log N O(logN)-way asymmetric multilinear map to make the size of public key and the size of ciphertext both achieve O log N (logN), where N is the number of potential group members. This is the first ASGKA protocol with public traitor traceability which is more efficient than trivial construction of ASGKA protocols.

关键词： cryptographic protocols common encryption key dynamic authenticated ASGKA protocol public traitor traceability black-box tracing algorithm Ind-CPA security key compromise impersonation resilience protocol resists collusion attack public key dynamic asymmetric group key agreement protocol asymmetric group key agreement protocols pairwise different decryption key computation Eurocrypt 2009 one-round dynamic authenticated ASGKA protoco KCIR forward secrecy D k-HDHE assumption setup algorithm join algorithm leave algorithm

来源：评论

学校读者我要写书评

暂无评论

Handling data skew in joins based on cluster cost partitioning for MapReduce

引用

MULTIAGENT AND GRID SYSTEMS 2018年第1期14卷 103-123页

作者： Wang, Yang Zhong, Yong Ma, Qingshan Yang, Guanci Chinese Acad Sci Chengdu Inst Comp Applicat Chengdu Sichuan Peoples R China Univ Chinese Acad Sci Beijing Peoples R China Guizhou Univ Minist Educ Key Lab Adv Mfg Technol Guiyang 550025 Guizhou Peoples R China

Data skew in parallel joins results in poor load balancing which can lead to significantly varying execution times for the reducers in MapReduce. The performance of join operation is severely degraded in the presence of heavy skew in the datasets to be joined. Previous work mainly focuses on either input or output load imbalance among reducers, which is ineffective for load balancing. In this paper, we present a new data skew handling method based on Cluster Cost Partitioning (CCP) for optimizing parallel joins in MapReduce. A new cost model which considers the properties of both input and output is defined to estimate the cost of the parallel join. CCP employs clusters instead of join keys from input relations to create join matrix. Using the cost model, CCP identifies and splits heavy cells in the cluster join matrix. Then CCP assigns a set of non-heavy cells to reducers for join load-balancing. For different applications, the input and output weight values in the cost model could be dynamically adjusted to depict the join costs more precisely. The experimental results demonstrate that CCP achieves a more accurate load balancing result among reducers.

关键词： Data skew load balance join algorithm cluster cost partitioning MapReduce

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：