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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Efficiently discovering critical workflows in scientific explorations

引用

FUTURE GENERATION COMPUTER SYSTEMS-THE INTERNATIONAL JOURNAL OF ESCIENCE 2009年第5期25卷 577-585页

作者： Shao, Qihong Sun, Peng Chen, Yi Arizona State Univ Dept Comp Sci & Engn Tempe AZ 85281 USA

Existing workflow management systems assume that scientists have a well-specified workflow design before the execution. In reality, a lot of scientific discoveries are made as a result of a dynamic process, where scientists keep proposing new hypotheses and verifying them through multiple tries of various experiments before achieving successful experimental results. Consequently, not all the experiments in a workflow execution have necessarily contributed to the final result. In this paper, we investigate the problem of effectively reproducing the results of previous scientific workflow executions by discovering the critical experiments leading to the success and the logical constraints on their execution order. Relational schema and SQL queries have been designed for effectively recording the workflow execution log, efficiently identifying the critical experiments from the log, and recommending experiment reproduction strategies to users. Furthermore, we propose optimization techniques for evaluating such SQL queries according to the unique characteristics of the log data. Experimental evaluations demonstrate the performance speedup of our approach. (C) 2008 Elsevier B.V. All rights reserved.

关键词： Scientific workflow Log join algorithm Database system

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：