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

Near-optimal communication-time tradeoff in fault-tolerant computation of aggregate functions

DISTRIBUTED COMPUTING 2016年第1期29卷 17-38页

作者： Zhao, Yuda Yu, Haifeng Chen, Binbin Natl Univ Singapore Sch Comp Comp 113 Comp Dr Singapore 117417 Singapore Adv Digital Sci Ctr 1 Fusionopolis Way08-10 Connexis North Tower Singapore 138632 Singapore

This paper considers the problem of computing general commutative and associative aggregate functions (such as Sum) over distributed inputs held by nodes in a distributed system, while tolerating failures. Specifically, there are N nodes in the system, and the topology among them is modeled as a general undirected graph. Whenever a node sends a message, the message is received by all of its neighbors in the graph. Each node has an input, and the goal is for a special root node (e.g., the base station in wireless sensor networks or the gateway node in wireless ad hoc networks) to learn a certain commutative and associate aggregate of all these inputs. All nodes in the system except the root node may experience crash failures, with the total number of edges incidental to failed nodes being upper bounded by f. The timing model is synchronous where protocols proceed in rounds. Within such a context, we focus on the following question: Under any given constraint on time complexity, what is the lowest communication complexity, in terms of the number of bits sent (i.e., locally broadcast) by each node, needed for computing general commutative and associate aggregate functions? This work, for the first time, reduces the gap between the upper bound and the lower bound for the above question from polynomial to polylog. To achieve this reduction, we present significant improvements over both the existing upper bounds and the existing lower bounds on the problem.

关键词： Communication complexity Time complexity Communication-time tradeoff Fault tolerance aggregate functions

来源：评论

学校读者我要写书评

暂无评论

Queries with aggregate functions over fuzzy RDF data

引用

JOURNAL OF SUPERCOMPUTING 2023年第13期79卷 14780-14807页

作者： Ma, Zongmin Zhang, Xiaowen Zhao, Yuhan Nanjing Univ Aeronaut & Astronaut Coll Comp Sci & Technol Nanjing 211106 Peoples R China Collaborat Innovat Ctr Novel Software Technol & In Nanjing 210000 Peoples R China

Since the World Wide Web Consortium (W3C) recommended the Resource Description Framework (RDF) data model, it has been widely adopted and applied in the era of Big Data and knowledge engineering. Now, large volumes of RDF data are produced and made available regularly. In real-world applications, information is often vague or ambiguous. Therefore, data may contain imperfect information, particularly in the context of open information extraction from the Web. The fuzzy RDF model has been proposed to handle uncertain semantics in RDF data. aggregate functions are a group of functions for statistics and group data calculation, which are essential for the analysis and processing of RDF data. In spite of the increased attention given to aggregate queries over RDF data, little has been done on aggregate queries over fuzzy RDF data. This paper proposes a more scalable and flexible aggregate query method for fuzzy RDF data. By introducing the concepts of upper and lower bounds and expectation in probability theory, we identify three variants of the aggregate functions in RDF query language over the fuzzy RDF model. The language has been implemented by transformation based on standard SPARQL language and evaluated with experiments. In addition, we examine how to handle multiple types of aggregate operations.

关键词： RDF Fuzzy sets Fuzzy RDF data Querying aggregate functions

来源：评论

学校读者我要写书评

暂无评论

Near-Optimal Communication-Time Tradeoff in Fault-Tolerant Computation of aggregate functions 14

Near-Optimal Communication-Time Tradeoff in Fault-Tolerant C...

引用

ACM Symposium on Principles of Distributed Computing (PODC)

作者： Zhao, Yuda Yu, Haifeng Chen, Binbin Natl Univ Singapore Singapore Singapore Adv Digital Sci Ctr Singapore Singapore

ISBN: (纸本)9781450329446

This paper considers the problem of computing general commutative and associative aggregate functions (such as SUM) over distributed inputs held by nodes in a distributed system, while tolerating failures. Specifically, there are N nodes in the system, and the topology among them is modeled as a general undirected graph. Whenever a node sends a message, the message is received by all of its neighbors in the graph. Each node has an input, and the goal is for a special root node (e.g., the base station in wireless sensor networks or the gateway node in wireless ad hoc networks) to learn a certain commutative and associate aggregate of all these inputs. All nodes in the system except the root node may experience crash failures, with the total number of edges incidental to failed nodes being upper bounded by f. The timing model is synchronous where protocols proceed in rounds. Within such a context, we focus on the following question: Under any given constraint on time complexity, what is the lowest communication complexity, in terms of the number of bits sent (i.e., locally broadcast) by each node, needed for computing general commutative and associate aggregate functions? This work, for the first time, reduces the gap between the upper bound and the lower bound for the above question from polynomial to polylog. To achieve this reduction, we present significant improvements over both the existing upper bounds and the existing lower bounds on the problem.

关键词： aggregate functions fault tolerance communication-time tradeoff time complexity communication complexity

来源：评论

学校读者我要写书评

暂无评论

Using aggregate functions within a distributed deductive database

Using aggregate functions within a distributed deductive dat...

引用

International Conference on Artificial Intelligence (ICAI 05)

作者： Maskarinec, M Neumann, K Western Illinois Univ Dept Comp Sci Macomb IL 61455 USA

ISBN: (纸本)1932415688

Deductive databases may operate in a distributed environment. One powerful extension to a traditional deductive database is the incorporation of aggregate functions. aggregate functions are readily available in relational databases, and their addition to a deductive database enhances its ability to deduce new information. This paper explains the algorithm used to accomplish processing of aggregate functions within a distributed deductive database.

关键词： intelligent database deductive database aggregate functions

来源：评论

学校读者我要写书评

暂无评论

Hierarchical Implementation of aggregate functions

Hierarchical Implementation of Aggregate Functions

引用

作者： Pablo Quevedo University of Kentucky

学位级别：硕士

Most systems in HPC make use of hierarchical designs that allow multiple levels of parallelism to be exploited by programmers. The use of multiple multi-core/multi- processor computers to form a computer cluster supports both fine-grain and large- grain parallel computation. aggregate function communications provide an easy- to-use and efficient set of mechanisms for communicating and coordinating between processing elements, but the model originally targeted only fine-grain parallel hard- ware. This work shows that a hierarchical implementation of aggregate functions is a viable alternative to MPI (the standard Message Passing Interface library) for programming clusters that provide both fine-grain and large-grain execution. Perfor- mance of a prototype implementation is evaluated and compared to that of MPI.

关键词： AFN aggregate functions parallel computation MPI OpenMP

来源：评论

学校读者我要写书评

暂无评论

Physics-Based aggregate-functions Approaches to Large Mom Problems

引用

APPLIED COMPUTATIONAL ELECTROMAGNETICS SOCIETY JOURNAL 2009年第2期24卷 143-160页

作者： Matekovits, Ladislau Vecchi, Giuseppe Vico, Felipe Politecn Torino Dept Elect Antennas & EMC Lab LACE I-10129 Turin Italy Univ Politcn Valencia iTEAM Valencia 46022 Spain

aggregate functions approaches construct efficient MoM basis functions by suitably grouping standard (e.g. Rao-Wilton-Glisson) functions. The application domains, objectives and related means of achieving them can be significantly different. In this paper we review some recent advances in aggregate-functions methods, putting them in a unifying perspective. We address matrix compression, multi-resolution sets, low- and high-frequency constructs. They can reduce the degrees of freedom of the problem so as to allow a direct, iteration-free solution, or can accelerate the convergence rate of iterative methods. We analyze compressive methods in more detail, providing general discussion and specific implementation examples.

关键词： Integral equation techniques Method of Moments Large structures aggregate functions

来源：评论

学校读者我要写书评

暂无评论

EFFICIENT NUMERICAL ANALYSIS OF LARGE PLANAR HIGH IMPEDANCE SURFACE BY THE SYNTHETIC FUNCTION EXPANSION TECHNIQUE

引用

MICROWAVE AND OPTICAL TECHNOLOGY LETTERS 2009年第11期51卷 2763-2769页

作者： Matekovits, Ladislau Vecchi, Giuseppe Bercigli, Mirko Bandinelli, Mauro Politecn Torino Antennas & EMC Lab LACE Dept Elect I-10129 Turin Italy IDS Ingn Sistemi SpA Computat Electromagnet Lab Pisa Italy

Application is presented of the Synthetic Function eXpansion (SFX) method to the accurate analysis of devices that incorporate microstrip-technology electromagnetic band-gap structures of large but finite size. The strong reduction of the dimension of the system matrix achieved emplolying the SFX technique reduces the solution time and the memory occupation, making it possible to analyze large structures on standard computational hardware. Experimental verification confirms the validity of the approach. (C) 2009 Wiley Periodicals, Inc. Microwave Opt Technol Lett 51: 2763-2769, 2009;Published online in Wiley InterScience (***). DOI 10.1002/mop.24729

关键词： electromagnetic band-gap structures high impedance surface integral equation technique aggregate functions large structures degrees of freedom

来源：评论

学校读者我要写书评

暂无评论

Extended aggregations for databases with referential integrity issues

引用

DATA & KNOWLEDGE ENGINEERING 2010年第1期69卷 73-95页

作者： Garcia-Garcia, Javier Ordonez, Carlos Univ Nacl Autonoma Mexico Fac Ciencias Mexico City 04510 CU Mexico Univ Houston Dept Comp Sci Houston TX 77204 USA

Querying inconsistent databases remains a broad and difficult problem. In this work, we study how to improve aggregations computed on databases with referential errors in the context of database integration, where each source database has different tables, columns with similar content across multiple databases. but different referential integrity constraints. Thus, a query in an integrated database may involve tables and columns with referential integrity errors. In a data warehouse, even though the ETL processes fix referential integrity errors, this is generally done by inserting "dummy" records into the dimension tables corresponding to such invalid foreign keys, thereby artificially enforcing referential integrity. When two tables are joined and aggregations are computed, rows with an invalid or null foreign key value are skipped, effectively eliminating potentially valuable information. With that motivation in mind, we extend SQL aggregate functions computed over tables with referential integrity issues to return complete answer sets in the sense that no row is excluded. We associate to each referenced key in the dimension table, a probability that invalid or null foreign keys refer to it. Our main idea is to compute aggregations over joined tables including rows with invalid or null references by distributing their contribution to aggregation totals, based on probabilities computed over correct foreign keys. Experiments with real and synthetic databases evaluate the usefulness, accuracy and performance of our extended aggregations. (C) 2009 Elsevier B.V. All rights reserved.

关键词： aggregate functions Data quality Inconsistent databases Imprecision SQL

来源：评论

学校读者我要写书评

暂无评论

Evaluating aggregate operations over imprecise data

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 1996年第2期8卷 273-284页

作者： Chen, ALP Chiu, JS Tseng, FSC YUAN ZE INST TECHNOL DEPT INFORMAT MANAGEMENT CHUNGLI 32026 TAIWAN

Imprecise data in databases were originally denoted as null values, which represent the meaning of ''values unknown at present.'' More generally, a partial value corresponds to a finite set of possible values for an attribute in which exactly one of the values is the ''true'' value. In this paper, we define a set of extended aggregate operations, namely sum, average, count, maximum, and minimum, which can be applied to an attribute containing partial values. Two types of aggregate operators are considered: scalar aggregates and aggregate functions. We study the properties of the aggregate operations and develop efficient algorithms for count, maximum and minimum. However, for sum and average, we point out that in general it takes exponential time complexity to do the computations.

关键词： relational databases null values partial values scalar aggregates aggregate functions graph theory

来源：评论

学校读者我要写书评

暂无评论

Resolvable Designs for Speeding Up Distributed Computing

引用

IEEE-ACM TRANSACTIONS ON NETWORKING 2020年第4期28卷 1657-1670页

作者： Konstantinidis, Konstantinos Ramamoorthy, Aditya Iowa State Univ Dept Elect & Comp Engn Ames IA 50011 USA

Distributed computing frameworks such as MapReduce are often used to process large computational jobs. They operate by partitioning each job into smaller tasks executed on different servers. The servers also need to exchange intermediate values to complete the computation. Experimental evidence suggests that this so-called Shuffle phase can be a significant part of the overall execution time for several classes of jobs. Prior work has demonstrated a natural tradeoff between computation and communication whereby running redundant copies of jobs can reduce the Shuffle traffic load, thereby leading to reduced overall execution times. For a single job, the main drawback of this approach is that it requires the original job to be split into a number of files that grows exponentially in the system parameters. When extended to multiple jobs (with specific function types), these techniques suffer from a limitation of a similar flavor, i.e., they require an exponentially large number of jobs to be executed. In practical scenarios, these requirements can significantly reduce the promised gains of the method. In this work, we show that a class of combinatorial structures called resolvable designs can be used to develop efficient coded distributed computing schemes for both the single and multiple job scenarios considered in prior work. We present both theoretical analysis and exhaustive experimental results (on Amazon EC2 clusters) that demonstrate the performance advantages of our method. For the single and multiple job cases, we obtain speed-ups of 4.69x (and 2.6x over prior work) and 4.31x over the baseline approach, respectively.

关键词： Servers Task analysis IEEE transactions Protocols Machine learning Redundancy MapReduce data-intensive computing coded multicasting communication load TeraSort aggregate functions distributed learning

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：