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

42nd ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS)

作者： Deng, Shiyuan Lu, Shangqi Tao, Yufei Chinese Univ Hong Kong Hong Kong Peoples R China

ISBN: (纸本)9798400701276

We present a dynamic index structure for join sampling. Built for an (equi-) join Q - let IN be the total number of tuples in the input relations of Q - the structure uses (O) over tilde( IN) space, supports a tuple update of any relation in (O) over tilde (1) time, and returns a uniform sample from the join result in (O) over tilde (IN rho* /max{1, OUT}) time with high probability (w.h.p.), where OUT and rho* are the join's output size and fractional edge covering number, respectively;notation (O) over tilde(.) hides a factor polylogarithmic to IN. We further show how our result justifies the (O) over tilde (IN rho*) running time of existing worst-case optimal join algorithms (for full result reporting) even when OUT << IN rho*. Specifically, unless the combinatorial K-clique hypothesis is false, no combinatorial algorithms (i.e., algorithms not relying on fast matrix multiplication) can compute the join result in O( IN rho*-epsilon) time w.h.p. even if OUT = IN epsilon, regardless of how small the constant epsilon > 0 is.

关键词： join algorithms Sampling Conjunctive Queries Lower Bounds

来源：评论

学校读者我要写书评

暂无评论

An analysis of two-way equi-join algorithms under MapReduce

引用

JOURNAL OF KING SAUD UNIVERSITY-COMPUTER AND INFORMATION SCIENCES 2022年第4期34卷 1074-1085页

作者： Al-Badarneh, Amer F. Rababa, Salahaldeen Atef Jordan Univ Sci & Technol Comp Informat Syst Dept POB 3030 Irbid 22110 Jordan

Large-scale datasets collected from heterogeneous sources often require a join operation to extract valuable information. MapReduce is an efficient programming model for large-scale data processing. However, it has some limitations in processing heterogeneous datasets. In this study, we review the state-of-the-art strategies for joining two datasets based on an equi-join condition and provide a detail implementation for each strategy. We also present an in-depth analysis of the join strategies and discuss their feasibilities and limitations to assist the reader in selecting the most efficient strategy. Concluding, we outline interesting directions for future join processing systems. (c) 2020 The Authors. Production and hosting by Elsevier B.V. on behalf of King Saud University. This is an open access article under the CC BY-NC-ND license (http://***/licenses/by-nc-nd/4.0/).

关键词： Big data join algorithms MapReduce Equi-join Hadoop

来源：评论

学校读者我要写书评

暂无评论

Optimizations for filter-based join algorithms in MapReduce

引用

JOURNAL OF INTELLIGENT & FUZZY SYSTEMS 2021年第5期40卷 8963-8980页

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

Large-scale datasets collected from heterogeneous sources often require a join operation to extract valuable information. MapReduce is an efficient programming model for processing large-scale data. However, it has some limitations in processing heterogeneous datasets. This is because of the large amount of redundant intermediate records that are transferred through the network. Several filtering techniques have been developed to improve the join performance, but they require multiple MapReduce jobs to process the input datasets. To address this issue, the adaptive filter-based join algorithms are presented in this paper. Specifically, three join algorithms are introduced to perform the processes of filters creation and redundant records elimination within a single MapReduce job. A cost analysis of the introduced join algorithms shows that the I/O cost is reduced compared to the state-of-the-art filter-based join algorithms. The performance of the join algorithms was evaluated in terms of the total execution time and the total amount of I/O data transferred. The experimental results show that the adaptive Bloom join, semi-adaptive intersection Bloom join, and adaptive intersection Bloom join decrease the total execution time by 30%, 25%, and 35%, respectively;and reduce the total amount of I/O data transferred by 18%, 25%, and 50%, respectively.

关键词： join algorithms big data management query optimization MapReduce

来源：评论

学校读者我要写书评

暂无评论

Worst-case Optimal join algorithms

引用

JOURNAL OF THE ACM 2018年第3期65卷 16-16页

作者： Ngo, Hung Q. Porat, Ely Re, Christopher Rudra, Atri Univ Buffalo SUNY Buffalo NY 14260 USA Bar Ilan Univ IL-5290002 Ramat Gan Israel Stanford Univ Stanford CA 94305 USA Univ Buffalo 338 Davis Hall Buffalo NY 14214 USA Gates Comp Sci Bldg 353 Serra Mall Stanford CA 94305 USA

Efficient join processing is one of the most fundamental and well-studied tasks in database research. In this work, we examine algorithms for natural join queries over many relations and describe a new algorithm to process these queries optimally in terms of worst-case data complexity. Our result builds on recent work by Atserias, Grohe, and Marx, who gave bounds on the size of a natural join query in terms of the sizes of the individual relations in the body of the query. These bounds, however, are not constructive: they rely on Shearer's entropy inequality, which is information-theoretic. Thus, the previous results leave open the question of whether there exist algorithms whose runtimes achieve these optimal bounds. An answer to this question may be interesting to database practice, as we show in this article that any project-join style plans, such as ones typically employed in a relational database management system, are asymptotically slower than the optimal for some queries. We present an algorithm whose runtime is worst-case optimal for all natural join queries. Our result may be of independent interest, as our algorithm also yields a constructive proof of the general fractional cover bound by Atserias, Grohe, and Marx without using Shearer's inequality. This bound implies two famous inequalities in geometry: the Loomis-Whitney inequality and its generalization, the Bollobas-Thomason inequality. Hence, our results algorithmically prove these inequalities as well. Finally, we discuss how our algorithm can be used to evaluate full conjunctive queries optimally, to compute a relaxed notion of joins and to optimally (in the worst-case) enumerate all induced copies of a fixed subgraph inside of a given large graph.

关键词： join algorithms fractional cover bound Loomis-Whitney inequality Bollobas-Thomason inequality

来源：评论

学校读者我要写书评

暂无评论

Peak power modeling for join algorithms in DBMS

引用

JOURNAL OF COMPUTER AND SYSTEM SCIENCES 2015年第3期81卷 599-614页

作者： Yang, Liang Huai Zhao, Yanzhu Fan, Yulei Zhu, Yihua Yu, Jian Zhejiang Univ Technol Sch Comp Sci & Technol Hangzhou Zhejiang Peoples R China Auckland Univ Technol Sch Comp & Math Sci Auckland New Zealand

Accurate peak power evaluation of query processing is fundamental to a power-aware DBMS running in large data centers. To estimate the peak power of the core operator join in query processing, the concept of CPU-boundedness was introduced, i.e., the ratio of CPU-intensive operations in unit time. The power prediction models were constructed with the piecewise and continuous fitting methods;and the multivariate model was further developed by incorporating both CPU-boundedness and CPU-frequency into the model via surface fitting. A non-runtime peak power estimation method is proposed for four most commonly used join algorithms in DBMS. To the best of our knowledge, our work is the first attempt towards modeling and estimating the peak power of query processing. Extensive experiments have demonstrated the effectiveness of our proposed methods with acceptable mean relative errors. (C) 2014 Elsevier Inc. All rights reserved.

关键词： Peak power CPU-boundedness join algorithms Power-aware DBMS Data center

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Optimal joins Using Compressed Quadtrees

引用

ACM TRANSACTIONS ON DATABASE SYSTEMS 2022年第2期47卷 8-8页

作者： Arroyuelo, Diego Navarro, Gonzalo Reutter, Juan L. Rojas-Ledesma, Javiel UTFSM & IMFD DIINF Santiago Chile Univ Chile DCC Santiago Chile IMFD Santiago Chile PUC & IMFD DCC Santiago Chile Univ Tecn Federico Santa Maria Dept Informat Vicuna Mackenna 3939 Santiago Chile Univ Chile Dept Comp Sci Beauchef 851 Santiago Chile Pontificia Univ Catolica Chile Dept Ciencia Computat Vicuna Mackenna 4860 Santiago 7820436 Chile

Worst-case optimal join algorithms have gained a lot of attention in the database literature. We now count several algorithms that are optimal in the worst case, and many of them have been implemented and validated in practice. However, the implementation of these algorithms often requires an enhanced indexing structure: to achieve optimality one either needs to build completely new indexes or must populate the database with several instantiations of indexes such as B+-trees. Either way, this means spending an extra amount of storage space that is typically one or two orders of magnitude more than what is required to store the raw data. We show that worst-case optimal algorithms can be obtained directly from a representation that regards the relations as point sets in variable-dimensional grids, without the need of any significant extra storage. Our representation is a compressed quadtree for the static indexes and a quadtree built on the fly that shares subtrees (which we dub a qdag) for intermediate results. We develop a compositional algorithm to process full join queries under this representation, which simulates navigation of the quadtree of the output, and show that the running time of this algorithm is worst-case optimal in data complexity. We implement our index and compare it experimentally with state-of-the-art alternatives. Our experiments show that our index uses even less space than what is needed to store the data in raw form (and replaces it) and one or two orders of magnitude less space than the other indexes. At the same time, our query algorithm is competitive in time, even sharply outperforming other indexes in various cases. Finally, we extend our framework to evaluate more expressive queries from relational algebra, including not only joins and intersections but also unions and negations. To obtain optimality on those more complex formulas, we introduce a lazy version of qdags we dub lqdags, which allow us navigate over the quadtree representing

关键词： join algorithms compact data structures Quadtrees AGM bound

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Optimal Data Placement for Data-Centric algorithms on NVM-Based Hybrid Memory 7

Optimal Data Placement for Data-Centric Algorithms on NVM-Ba...

引用

7th IEEE International Conference on Data Science and Advanced Analytics (DSAA)

作者： Luo, Yongping Jin, Peiquan Wan, Shouhong Univ Sci & Technol China Sch Comp Sci & Technol Hefei Peoples R China Chinese Acad Sci Key Lab Electromagnet Space Informat Hefei Peoples R China

ISBN: (纸本)9781728182063

Non-volatile memory (NVM) as a new kind of future memory has several special properties such as non-volatility, read/write asymmetry, and byte address-ability. This makes it difficult to directly replace DRAM with NVM in the current memory hierarchy. Thus, a practical way is to construct a hybrid memory composed of both NVM and DRAM. Such hybrid memory architecture introduces many new challenges for existing algorithms. In this paper, we focus on the data placement issue in NVM-based hybrid memory systems, i.e., how to place the data on DRAM and NVM for a data-centric algorithm so that it can achieve high performance on hybrid memory. Particularly, we propose an optimal data placement model (ODP) to properly store data structures on DRAM and NVM during the execution of an algorithm. We present the theoretical proof to ODP to ensure the correctness of the model. To demonstrate the efficiency of ODP, we apply the ODP to two kinds of data-centric algorithms, namely sorting and database join. For sorting algorithms, we implement four ODP-based sorting algorithms, including Insertion Sort, Selection Sort, Heapsort, and Merge Sort. For join algorithms, we implement four ODP-based join strategies, including Nested Loops join, Sort join, Hash join, and Virtual Partitioning join. We conduct comparative experiments to evaluate the performance of the sorting/join algorithms. The results show that the ODP-based sorting/join strategies are much faster than the classical sorting/join algorithms that are not NVM-aware. In addition, the ODP-based implementation can reduce more NVM writes, showing that it is more NVM-friendly.

关键词： Data placement model join algorithms Non-volatile memory Performance evaluation Sorting

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：