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

Distributed query evaluation on semistructured data

ACM TRANSACTIONS ON DATABASE SYSTEMS 2002年第1期27卷 1-62页

作者： Suciu, D Univ Washington Dept Comp Sci & Engn Seattle WA 98195 USA AT&T Corp Shannon Labs New York NY 10013 USA

Semistructured data is modeled as a rooted, labeled graph. The simplest kinds of queries on such data are those which traverse paths described by regular path expressions. More complex queries combine several regular path expressions, with complex data restructuring, and with sub-queries. This article addresses the problem of efficient query evaluation on distributed, semistructured databases. In our setting, the nodes of the database are distributed over a fixed number of sites, and the edges are classified into local (with both ends in the same site) and cross edges (with ends in two distinct sites). Efficient evaluation in this context means that the number of communication steps is fixed (independent on the data or the query), and that the total amount of data sent depends only on the number of cross links and of the size of the query's result. We give such algorithms in three different settings. First, for the simple case of queries consisting of a single regular expression;second, for all queries in a calculus for graphs based on structural recursion which in addition to regular path expressions can perform nontrivial restructuring of the graph;and third, for a class of queries we call select-where queries that combine pattern matching and regular path expressions with data restructuring and subqueries. This article also includes a discussion on how these methods can be used to derive efficient view maintenance algorithms.

关键词： algorithm languages theory distributed evaluation nested queries parallel complexity regular expressions semistructured data

来源：评论

学校读者我要写书评

暂无评论

Lower bounds for arithmetic networks .2. Sum of Betti numbers

引用

APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING 1996年第1期7卷 41-51页

作者： Montana, JL Morais, JE Pardo, LM UNIV CANTABRIA FAC CIENCIAS DEPT MATEMAT ESTADIST & COMPUTAC E-39071 SANTANDER SPAIN UNIV PUBL NAVARRA DEPT MATEMAT & INFORMAT E-31006 PAMPLONA NAVARRA SPAIN

We show lower bounds for the parallel complexity of membership problems in semialgebraic sets. Our lower bounds are obtained from the Euler characteristic and the sum of Betti numbers. We remark that these lower bound... 详细信息

关键词： parallel complexity algebraic complexity theory arithmetic networks semi-algebraic sets Borel-Moore homology

来源：评论

学校读者我要写书评

暂无评论

Bounded size dictionary compression:: SC^k-completeness and NC algorithms

引用

INFORMATION AND COMPUTATION 2003年第2期180卷 101-112页

作者： De Agostino, S Silvestri, R Armstrong Atlantic State Univ Dept Comp Sci Savannah GA 31419 USA Univ Roma La Sapienza Dipartimento Sci Informaz I-00135 Rome Italy

We study the parallel complexity of a bounded size dictionary version (LRU deletion heuristic) of the LZ2 compression algorithm. The unbounded version was shown to be P-complete. When the size of the dictionary is O(Iog(k)n), the problem of computing the LZ2 compression is shown to be hard for the class of problems solvable simultaneously in polynomial time and O(Iog(k) n) space (that is, SCk). We also introduce a variation of this heuristic that turns out to be an SCk-complete problem (the original heuristic belongs to SCk+1). In virtue of these results, we argue that there are no practical parallel algorithms for LZ2 compression with LRU deletion heuristic or any other heuristic deleting dictionary elements in a continuous way. For simpler heuristics (SWAP, RESTART, FREEZE), practical parallel algorithms are given. (C) 2002 Elsevier Science (USA). All rights reserved.

关键词： parallel complexity NC algorithms SCk-completeness data compression dictionary algorithms

来源：评论

学校读者我要写书评

暂无评论

FAST AND EFFICIENT parallel SOLUTION OF SPARSE LINEAR-SYSTEMS

引用

SIAM JOURNAL ON COMPUTING 1993年第6期22卷 1227-1250页

作者： PAN, V REIF, J SUNY ALBANY DEPT COMP SCI ALBANY NY 12222 USA DUKE UNIV DEPT COMP SCI DURHAM NC 27706 USA

This paper presents a parallel algorithm for the solution of a linear system Ax = b with a sparse n x rr symmetric positive definite matrix A, associated with the graph G(A) that has rr vertices and has an edge for each nonzero entry of A. If G(A) has an s(n)-separator family and a known s(n)-separator tree, then the algorithm requires only O(log(3) n) time and (\E\ + M(s(n)))/log n processors for the evaluation of the solution vector x = A (-1)b, where \E\ is the number of edges in G(A) and M(n) is the number of processors sufficient for multiplying two n x n rational matrices in time O(log n). Furthermore, for this computational cost the algorithm computes a recursive factorization of A such that the solution of any other linear system Ax = b' with the same matrix A requires only O(log(2)n) time and (\E\/logn) + s(n)(2) processors.

关键词： parallel ALGORITHMS SPARSE LINEAR SYSTEMS NESTED DISSECTION parallel complexity GRAPH SEPARATORS

来源：评论

学校读者我要写书评

暂无评论

REVERSAL complexity

引用

SIAM JOURNAL ON COMPUTING 1991年第4期20卷 622-638页

作者： CHEN, JE YAP, CK New York Univ New York NY United States

The importance of reversal complexity as a basic computational resource has only been recognized in recent years. It is intimately connected to parallel time complexity and circuit depth. In this paper, some basic techniques necessary for establishing analogues of well-known theorems on space and time complexity are developed. The main results are, for reversal-constructible functions s(n) greater-than-or-equal-to log n, DSPACE(s(n)) subset-or-is-equal-to DREVERSAL(s(n)), and a tape reduction theorem. As applications of the tape reduction theorem, a hierarchy theorem is proved and the existence of complete languages for reversal complexity is shown.

关键词： REVERSAL SPACE TAPE REDUCTION THEOREM REVERSAL HIERARCHIES COMPLETE LANGUAGES parallel complexity

来源：评论

学校读者我要写书评

暂无评论

Division in logspace-uniform NC

引用

RAIRO-INFORMATIQUE THEORIQUE ET APPLICATIONS-THEORETICAL INFORMATICS AND APPLICATIONS 2001年第3期35卷 259-275页

作者： Chiu, A Davida, G Litow, B Univ Wisconsin Dept EECS Milwaukee WI 53201 USA James Cook Univ N Queensland Sch Informat Technol Townsville Qld 4811 Australia

Beame, Cook and Hoover were the first to exhibit a log-depth, polynomial size circuit family for integer division. However, the family was not logspace-uniform. In this paper we describe log-depth, polynomial size, logspace-uniform, i.e., NC1 circuit family for integer division. In particular, by a well-known result this shows that division is in logspace. We also refine the method of the paper to show that division is in dlogtime-uniform NC1.

关键词： parallel complexity NC integer division uniformity

来源：评论

学校读者我要写书评

暂无评论

A NOTE ON STRATEGY ELIMINATION IN BIMATRIX GAMES

引用

OPERATIONS RESEARCH LETTERS 1988年第3期7卷 103-107页

作者： KNUTH, DE PAPADIMITRIOU, CH TSITSIKLIS, JN UNIV CALIF SAN DIEGO DEPT COMP SCI & ENGNSAN DIEGOCA 92103 MIT DEPT ELECT ENGN & COMP SCICAMBRIDGEMA 02139

In bimatrix games we study the process of successively eliminating strategies which are dominated by other pure strategies. We show how to perform this simplification in O( n 3 ) time, where n is the number of strateg... 详细信息

关键词： game theory strategy domination algorithms parallel complexity matrix multiplication P-completeness

来源：评论

学校读者我要写书评

暂无评论

TIME-parallel ITERATIVE SOLVERS FOR PARABOLIC EVOLUTION EQUATIONS

引用

SIAM JOURNAL ON SCIENTIFIC COMPUTING 2019年第1期41卷 C28-C51页

作者： Neumueller, Martin Smears, Iain Johannes Kepler Univ Linz Inst Computat Math A-4040 Linz Austria UCL Dept Math London WC1E 6BT England

We present original time-parallel algorithms for the solution of the implicit Euler discretization of general linear parabolic evolution equations with time-dependent self-adjoint spatial operators. Motivated by the inf-sup theory of parabolic problems, we show that the standard nonsymmetric time-global system can be equivalently reformulated as an original symmetric saddle-point system that remains inf-sup stable with respect to the same natural parabolic norms. We then propose and analyze an efficient and readily implementable parallel-in-time preconditioner to be used with an inexact Uzawa method. The proposed preconditioner is nonintrusive and easy to implement in practice. It also features the key theoretical advantage of robust spectral bounds, which lead to convergence rates that are independent of the number of time-steps, final time, and spatial mesh size. Finally, it has a theoretical parallel complexity that grows only logarithmically with respect to the number of time-steps. Numerical experiments with large-scale parallel computations show the effectiveness of the method, along with its good weak and strong scaling properties.

关键词： parabolic partial differential equations time-parallel methods analysis of iterative methods and preconditioners inf-sup stability parallel complexity weak and strong scaling

来源：评论

学校读者我要写书评

暂无评论

A NEW APPROACH TO STABLE MATCHING PROBLEMS

引用

SIAM JOURNAL ON COMPUTING 1994年第4期23卷 671-700页

作者： SUBRAMANIAN, A STANFORD UNIV DEPT COMP SCISTANFORDCA 94305

It is shown that Stable Matching problems are the same as problems about stable configurations of X-networks. Consequences include easy proofs of old theorems, a new simple algorithm for finding a stable matching, an understanding of the difference between Stable Marriage and Stable Roommates, NP-completeness of Three-party Stable Marriage, CC-completeness of several Stable Matching problems, and a fast parallel reduction from the Stable Marriage problem to the Assignment problem.

关键词： STABLE MATCHING STABLE MARRIAGE STABLE ROOMMATES STABLE CONFIGURATION CIRCUIT VALUE NETWORK STABILITY parallel complexity COMPARATOR CC SCATTER ASSIGNMENT PROBLEM WEIGHTED MATCHING

来源：评论

学校读者我要写书评

暂无评论

Sampling chaotic trajectories quickly in parallel

引用

JOURNAL OF STATISTICAL PHYSICS 2002年第3-4期109卷 863-873页

作者： Machta, J Univ Massachusetts Dept Phys Amherst MA 01003 USA

The parallel computational complexity of the quadratic map is studied. A parallel algorithm is described that generates typical pseudotrajectories of length t in a time that scales as log t and increases slowly in the accuracy demanded of the pseudotrajectory. Long pseudotrajectories are created in parallel by putting together many short pseudotrajectories;Monte Carlo procedures are used to eliminate the discontinuities between these short pseudotrajectories and then suitably randomize the resulting long pseudotrajectory. Numerical simulations are presented that show the scaling properties of the parallel algorithm. The existence of the fast parallel algorithm provides a way to formalize the intuitive notion that chaotic systems do not generate complex histories.

关键词： chaotic dynamics parallel complexity quadratic map path sampling

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：