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

Adaptive simplicial grids from cross-sections of monotone complexes

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS 2000年第3期10卷 267-284页

作者： Edelsbrunner, H Waupotitsch, R Univ Illinois Dept Comp Sci Urbana IL 61801 USA

We study the maintenance of a simplicial grid or complex under changing density requirements. The proposed method works in any fixed dimension and generates grids by projecting cross-sections of a monotone simplicial complex that lives in one dimension higher than the grid. The density of the grid is adapted by locally moving the cross-section up or down along the extra dimension.

关键词： geometric and topological algorithms dynamic data structures grid generation multi-grids simplicial complexes hierarchies directed acyclic graphs

来源：评论

学校读者我要写书评

暂无评论

Exploiting domain-specific properties: Compiling parallel dynamic neural network algorithms into efficient code

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1999年第11期10卷 1105-1117页

作者： Prechelt, L Univ Karlsruhe Fak Informat D-76128 Karlsruhe Germany

Domain-specific constraints can be exploited to implement compiler optimizations that are not otherwise feasible. Compilers for neural network learning algorithms can achieve near-optimal colocality of data and processes and near-optimal balancing of load over processors, even for dynamically irregular problems. This is impossible for general programs, but restricting programs to the neural algorithm domain allows for the exploitation of domain-specific properties. The operations performed by neural algorithms are broadcasts, reductions, and object-local operations only;the load distribution is regular with respect to the (perhaps irregular) network topology;changes of network topology occur only from time to time. A language, compilation techniques, and a compiler implementation on the MasPar MP-1 are described and quantitative results for the effects of various optimizations used in the compiler are shown. Conservative experiments with weight pruning algorithms yield performance improvements of 27 percent due to load balancing and 195 percent improvement is achieved due to data locality, both compared to unoptimized versions. Two other optimizations-connection allocation and selecting the number of replicates-speed programs up by about 50 percent and 100 percent, respectively. This work can be viewed as a case study in exploiting domain-specific information;some of the principles presented here may apply to other domains as well.

关键词： compiler optimizations high-level parallel language irregular problems dynamic data structures communication optimization

来源：评论

学校读者我要写书评

暂无评论

dynamic algorithms for geometric spanners of small diameter: Randomized solutions

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 1999年第2期13卷 91-107页

作者： Arya, S Mount, DM Smid, M Hong Kong Univ Sci & Technol Dept Comp Sci Kowloon Peoples R China Univ Maryland Dept Comp Sci College Pk MD 20742 USA Univ Maryland Inst Adv Comp Studies College Pk MD 20742 USA Univ Magdeburg Dept Comp Sci D-39106 Magdeburg Germany Max Planck Inst Informat Saarbrucken Germany

Let S be a set of n points in R-d and let t > 1 be a real number. A t-spanner for S is a directed graph having the points of S as its vertices, such that for any pair p and q of points there is a path from p to q of length at most t times the Euclidean distance between p and q. Such a path is called a t-spanner path. The spanner diameter of such a spanner is defined as the smallest integer D such that for any pair p and q of points there is a t-spanner path from p to q containing at most D edges. A randomized algorithm is given for constructing a t-spanner that, with high probability, contains O(n) edges and has spanner diameter O(log n). A data structure of size O(n log(d) n) is given that maintains this t-spanner in O(log(d) n log log n) expected amortized time per insertion and deletion, in the model of random updates, as introduced by Mulmuley. (C) 1999 Elsevier Science B.V. All rights reserved.

关键词： computational geometry proximity problems skip lists randomization dynamic data structures

来源：评论

学校读者我要写书评

暂无评论

Randomized data structures for the dynamic closest-pair problem

引用

SIAM JOURNAL ON COMPUTING 1998年第4期27卷 1036-1072页

作者： Golin, M Raman, R Schwarz, C Smid, M Hong Kong Univ Sci & Technol Kowloon Hong Kong Univ London Kings Coll Dept Comp Sci Algorithm Design Grp London WC2R 2LS England Int Comp Sci Inst Berkeley CA 94704 USA Max Planck Inst Informat D-66123 Saarbrucken Germany

We describe a new randomized data structure, the sparse partition, for solving the dynamic closest-pair problem. Using this data structure the closest pair of a set of n points in D-dimensional space, for any fixed D, can be found in constant time. If a frame containing all the points is known in advance, and if the floor function is available at unit cost, then the data structure supports insertions into and deletions from the set in expected O(log n) time and requires expected O(n) space. This method is more efficient than any deterministic algorithm for solving the problem in dimension D > 1. The data structure can be modified to run in O(log(2) n) expected time per update in the algebraic computation tree model. Even this version is more efficient than the best currently known deterministic algorithm for D > 2. Both results assume that the sequence of updates is not determined in any way by the random choices made by the algorithm.

关键词： computational geometry proximity dynamic data structures randomization

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for the temporal precedence problem

引用

INFORMATION PROCESSING LETTERS 1998年第2期68卷 71-78页

作者： Ranjan, D Pontelli, E Gupta, G New Mexico State Univ Dept Comp Sci Las Cruces NM 88003 USA

An study was carried out to evaluate the Temporal Prudence Problem, i.e., the problem of dynamically supporting the execution of the operations insert and precede, on a pointer machine. Various algorithms were derived to implement these operations. By using the derived algorithms, the worst-case time complexity of these operations was determined. An attempt was also made to prove the upper bound of O((lg lg n) super(2)) per operation for the problem. The results reveal that the square factor in this complexity formula arises from maintaining the non-constant number of fields for each record as a simple list of pointers.

关键词： algorithms dynamic data structures complexity pointer machines

来源：评论

学校读者我要写书评

暂无评论

dynamic trees and dynamic point location

引用

SIAM JOURNAL ON COMPUTING 1998年第2期28卷 612-636页

作者： Goodrich, MT Tamassia, R Johns Hopkins Univ Dept Comp Sci Baltimore MD 21218 USA Brown Univ Dept Comp Sci Providence RI 02912 USA

This paper describes new methods for maintaining a point-location data structure for a dynamically changing monotone subdivision. The main approach is based on the maintenance of two interlaced spanning trees, one for and one S for the graph-theoretic planar dual of. Queries are answered by using a centroid decomposition S of the dual tree to drive searches in the S primal tree. These trees are maintained via the link-cut trees structure of Sleator and Tarjan [J. Comput. System Sci., 26 (1983), pp. 362-381], leading to a scheme that achieves vertex insertion/deletion in O(log n) time, insertion/deletion of k-edge monotone chains in O(log n+k) time, and answers queries in O(log(2) n) time, with O(n) space, where n is the current size of subdivision S. The techniques described also allow for the dual operations expand and contract to be implemented in O(log n) time, leading to an improved method for spatial point location in a 3-dimensional convex subdivision. In addition, the interlaced-tree approach is applied to on-line point location (where one builds incrementally), improving the query bound to O(log n log log n) time and the update bounds to O(1) S amortized time in this case. This appears to be the first on-line method to achieve a polylogarithmic query time and constant update time.

关键词： computational geometry point location centroid decomposition dynamic data structures on-line algorithms

来源：评论

学校读者我要写书评

暂无评论

Efficient dynamic range searching using data replication

引用

INFORMATION PROCESSING LETTERS 1998年第2期68卷 97-105页

作者： Kanth, KVR Singh, A Univ Calif Santa Barbara Dept Comp Sci Santa Barbara CA 93106 USA

In this paper, we consider the problem of dynamic range searching in linear-space index structures. We propose a new dynamic structure that combines Bentley's multilevel range structure with Overmars' dynamization techniques. This structure achieves O(log n) time complexity for updates and O(n(epsilon)) time complexity for queries, for any epsilon > O. This result is an improvement over the static-to-dynamic transformations of Bentley's structure, which yield an update time of O(log(2) n) and a query time of O(n(epsilon)) for any epsilon > 0. (C) 1998 Published by Elsevier Science B.V.

关键词： range searching dynamic data structures computational geometry

来源：评论

学校读者我要写书评

暂无评论

Separator-based sparsification - II: Edge and vertex connectivity

引用

SIAM JOURNAL ON COMPUTING 1998年第1期28卷 341-381页

作者： Eppstein, D Galil, Z Italiano, GF Spencer, TH Univ Calif Irvine Dept Informat & Comp Sci Irvine CA 92697 USA Columbia Univ Dept Comp Sci New York NY 10027 USA Tel Aviv Univ Dept Comp Sci IL-69978 Tel Aviv Israel Univ Ca Foscari Dipartimento Matemat Applicata & Informat Venice Italy Univ Nebraska Dept Comp Sci Omaha NE 68182 USA

We consider the problem of maintaining a dynamic planar graph subject to edge insertions and edge deletions that preserve planarity but that can change the embedding. We describe algorithms and data structures for maintaining information about 2- and 3-vertex-connectivity, and 3- and 4-edge-connectivity in a planar graph in O(n(1/2)) amortized time per insertion, deletion, or connectivity query. All of the data structures handle insertions that keep the graph planar without regard to any particular embedding of the graph. Our algorithms are based on a new type of sparsification combined with several properties of separators in planar graphs.

关键词： analysis of algorithms dynamic data structures edge connectivity vertex connectivity planar graphs

来源：评论

学校读者我要写书评

暂无评论

Optimal on-line search and sublinear time update in string matching

引用

SIAM JOURNAL ON COMPUTING 1998年第3期27卷 713-736页

作者： Ferragina, P Grossi, R Univ Pisa Dipartimento Informat I-56125 Pisa Italy Univ Florence Dipartimento Sistemi & Informat I-50134 Florence Italy

This paper investigates the problem of searching on-line for the occurrences (occ) of an arbitrary pattern of length p in a text of length n subjected to some updates after its preprocessing. Each text update consists of inserting or deleting an arbitrary string of length y. We present the first dynamic algorithm that achieves optimal query time, i.e., Theta(p + occ), sublinear time per update, i.e., O(root n + y), and optimal space, i.e., Theta(n), in the worst case. As a result, our algorithm obtains the same query time and space usage of suffix trees [McCreight, J. Assoc. Comput. Mach., 23 (1976),pp. 262-272] while improving their O(n + y) update performance.

关键词： string matching suffix tree text indexing dynamic data structures

来源：评论

学校读者我要写书评

暂无评论

SUPPORTING dynamic data-structures ON DISTRIBUTED-MEMORY MACHINES

引用

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS 1995年第2期17卷 233-263页

作者： ROGERS, A CARLISLE, MC REPPY, JH HENDREN, LJ AT&T BELL LABS MURRAY HILLNJ 07974 MCGILL UNIV SCH COMP SCIMONTREALPQ H3A 2A7CANADA

Compiling for distributed-memory machines has been a very active research area in recent years. Much of this work has concentrated on programs that use arrays as their primary data structures. To date, little work has been done to address the problem of supporting programs that use pointer-based dynamic data structures. The techniques developed for supporting SPMD execution of array-based programs rely on the fact that arrays are statically defined and directly addressable. Recursive data structures do not have these properties, so new techniques must be developed. In this article, we describe an execution model for supporting programs that use pointer-based dynamic data structures. This model uses a simple mechanism for migrating a thread of control based on the layout of heap-allocated data and introduces parallelism using a technique based on futures and lazy task creation. We intend to exploit this execution model using compiler analyses and automatic parallelization techniques. We have implemented a prototype system, which we call Olden, that runs on the Intel iPSC/860 and the Thinking Machines CM-5. We discuss our implementation and report on experiments with five benchmarks.

关键词： LANGUAGES PERFORMANCE dynamic data structures

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：