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

persistent Predecessor Search and Orthogonal Point Location on the Word RAM

ACM TRANSACTIONS ON ALGORITHMS 2013年第3期9卷 22-22页

作者： Chan, Timothy M. Univ Waterloo Cheriton Sch Comp Sci Waterloo ON N2L 3G1 Canada

We answer a basic data structuring question (e.g., raised by Dietz and Raman [1991]): Can van Emde Boas trees be made persistent, without changing their asymptotic query/update time? We present a (partially) persistent data structure that supports predecessor search in a set of integers in {1,...,U} under an arbitrary sequence of n insertions and deletions, with O(log log U) expected query time and expected amortized update time, and O(n) space. The query bound is optimal in U for linear-space structures and improves previous near-O((log log U)(2)) methods. The same method solves a fundamental problem from computational geometry: point location in orthogonal planar subdivisions (where edges are vertical or horizontal). We obtain the first static data structure achieving O(log log U) worst-case query time and linear space. This result is again optimal in U for linear-space structures and improves the previous O((log log U)(2)) method by de Berg et al. [1995]. The same result also holds for higher-dimensional subdivisions that are orthogonal binary space partitions, and for certain nonorthogonal planar subdivisions such as triangulations without small angles. Many geometric applications follow, including improved query times for orthogonal range reporting for dimensions >= 3 on the RAM. Our key technique is an interesting new van-Emde-Boas-style recursion that alternates between two strategies, both quite simple.

关键词： Computational geometry point location persistent data structures word-RAM algorithms

来源：评论

学校读者我要写书评

暂无评论

Authenticated Dictionaries: Real-World Costs and Trade-Offs

引用

ACM TRANSACTIONS ON INFORMATION AND SYSTEM SECURITY 2011年第2期14卷 17-17页

作者： Crosby, Scott A. Wallach, Dan S. Rice Univ Houston TX 77251 USA

Authenticated dictionaries are a widely discussed paradigm to enable verifiable integrity for data storage on untrusted servers, such as today's widely used "cloud computing" resources, allowing a server to provide a "proof," typically in the form of a slice through a cryptographic data structure, that the results of any given query are the correct answer, including that the absence of a query result is correct. persistent authenticated dictionaries (PADs) further allow queries against older versions of the structure. This research presents implementations of a variety of different PAD algorithms, some based on Merkle tree-style data structures and others based on individually signed "tuple" statements (with and without RSA accumulators). We present system throughput benchmarks, indicating costs in terms of time, storage, and bandwidth as well as considering how much money would be required given standard cloud computing costs. We conclude that Merkle tree PADs are preferable in cases with frequent updates, while tuple-based PADs are preferable with higher query rates. For Merkle tree PADs, red-black trees outperform treaps and skiplists. Applying Sarnak-Tarjan's versioned node strategy, with a cache of old hashes at every node, to red-black trees yields the fastest Merkle tree PAD implementation, notably using half the memory of the more commonly used mutation-free path copying strategy. For tuple PADs, although we designed and implemented an algorithm using RSA accumulators that offers constant update size, constant storage per update, constant proof size, and sublinear computation per update, we found that RSA accumulators are so expensive that they are never worthwhile. We find that other optimizations in the literature for tuple PADs are more cost-effective.

关键词： Security Performance Authenticated dictionaries persistent data structures tamper evident data structures

来源：评论

学校读者我要写书评

暂无评论

An Abstract Machine for the Old Value Retrieval

An Abstract Machine for the Old Value Retrieval

引用

10th International Conference on Mathematics of Program Construction

作者： Kosiuczenko, Piotr WAT Inst Informat Syst Warsaw Poland

ISBN: (纸本)9783642133206

The evaluation of post-conditions requires the computation of old attribute values. Until recently, existing computation methods were not efficient in terms of time- and space-complexity. Moreover they were applicable only to a restricted form of post-conditions. Recently a new algorithm was proposed to overcome those deficiencies. In this paper, an abstract machine corresponding to this algorithm is defined. Its transitions simulate steps of object-oriented systems and preserve an invariant implying properties needed to compute old attribute values. The machine is based on a kind of structure called here sufficiently persistent, as opposed to persistent and partially persistent structures. A space-bound on the structure size is given. It is also demonstrated that methods which do not have post-conditions can be abstracted away.

关键词： persistent data structures old value retrieval @pre old

来源：评论

学校读者我要写书评

暂无评论

Simple confluently persistent catenable lists

引用

SIAM JOURNAL ON COMPUTING 2000年第3期30卷 965-977页

作者： Kaplan, H Okasaki, C Tarjan, RE Tel Aviv Univ Dept Comp Sci IL-69978 Tel Aviv Israel Columbia Univ Dept Comp Sci New York NY 10027 USA Carnegie Mellon Univ Pittsburgh PA 15213 USA Princeton Univ Dept Comp Sci Princeton NJ 08544 USA InterTrust Technol Corp Sunnyvale CA 94086 USA

We consider the problem of maintaining persistent lists subject to concatenation and to insertions and deletions at both ends. Updates to a persistent data structure are nondestructive each operation produces a new list incorporating the change, while keeping intact the list or lists to which it applies. Although general techniques exist for making data structures persistent, these techniques fail for structures that are subject to operations, such as catenation, that combine two or more versions. In this paper we develop a simple implementation of persistent double-ended queues (deques) with catenation that supports all deque operations in constant amortized time. Our implementation is functional if we allow memoization.

关键词： functional-programming data structures persistent data structures stack queue stack-ended queue (steque) double-ended queue (deque) memoization

来源：评论

学校读者我要写书评

暂无评论

Purely functional, real-time deques with catenation

引用

JOURNAL OF THE ACM 1999年第5期46卷 577-603页

作者： Kaplan, H Tarjan, RE Princeton Univ Dept Comp Sci Princeton NJ 08544 USA InterTrust Technol Sunnyvale CA USA AT&T Labs Res Florham Pk NJ USA

We describe an efficient, purely functional implementation of deques with catenation. In addition to being an intriguing;problem in its own right, finding a purely functional implementation of catenable deques is required to add certain sophisticated programming constructs to functional programming languages. Our solution has a worst-case running time of O(1) for each push, pop, inject, eject and catenation, The best previously known solution has an O(log* k) time bound for the krh deque operation. Our solution is not only faster but simpler. A key idea used in our result is an algorithmic technique related to the redundant digital representations used to avoid carry propagation in binary counting.

关键词： catenation data structures double-ended queue persistent data structures purely functional data structures purely functional queues queue stack

来源：评论

学校读者我要写书评

暂无评论

Queries on Voronoi diagrams of moving points

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 1996年第5期6卷 315-327页

作者： Devillers, O Golin, M Kedem, K Schirra, S INRIA F-06902 SOPHIA ANTIPOLISFRANCE HONG KONG UNIV SCI & TECHNOL KOWLOONHONG KONG BEN GURION UNIV NEGEV IL-84105 BEER SHEVAISRAEL MAX PLANCK INST INFORMAT D-66123 SAARBRUCKENGERMANY

Suppose we are given n moving postmen described by their motion equations p(i)(t)=s(i)+v(i)t, i=1,...,n, where s(i) is an element of R(2) is the position of the ith postman at time t=0, and v(i) is an element of R(2) is his velocity. The problem we address is how to preprocess the postmen data so as to be able to efficiently answer two types of nearest-neighbor queries. The first one asks ''who is the nearest postman at time t(q) to a dog located at point s(q). In the second type a query dog is located at point s(q) at time t(q), its speed is v(q) > \v(i)\ (for all i=1,..., n), and we want to know which postman the dog can catch first. The first type of query is relatively simple to address, the second type at first seems much more complicated. We show that the problems are very closely related, with efficient solutions to the first type of query leading to efficient solutions to the second. We then present two solutions to these problems, with tradeoff between preprocessing time and query time. Both solutions use deterministic data structures.

关键词： dynamic computational geometry Voronoi diagram post-office problem parametric search persistent data structures

来源：评论

学校读者我要写书评

暂无评论

The treatment of state in optimistic systems 95

The treatment of state in optimistic systems

引用

Proceedings of the ninth workshop on Parallel and distributed simulation

作者： David Bruce Defence Research Agency st. Andrews Road Malvern Worcestershire WR14 3PS United Kingdom

ISBN: (纸本)9780818671203

Optimistic computation methods typically save copies of objects' state information, so that they can recover from erroneous “over-optimistic” computations. Such state saving is generally time and space consuming, and can be rather complicated both to implement and to use.I show how the data structure community's theory of persistence can be used not only to analyse and explain the treatment of state in optimistic systems, but also as a simple yet general mechanism for performing the necessary state saving with minimal impact on application *** results based on a benchmark application and an existing optimistic simulator are presented, showing that providing support for fully general object states is a realistic and practical option. In addition, I show how some existing state saving techniques—including support for shared state—can be derived, and discuss a number of ways in which the model might be extended.

关键词： state saving optimistic methods parallel discrete event simulation persistent data structures

来源：评论

学校读者我要写书评

暂无评论

DESIGNING EFFICIENT GEOMETRIC SEARCH ALGORITHMS USING persistent BINARY-BINARY SEARCH-TREES

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 1994年第4期E77A卷 601-607页

作者： TAN, XH HIRATA, T INAGAKI, Y Tokai Univ Numazi-shi Japan

persistent data structures, introduced by Sarnak and Tarjan, have been found especially useful in designing geometric algorithms. In this paper, we present a persistent form of binary-binary search tree, and then apply this data structure to solve various geometric searching problems, such as, three dimensional ray-shooting, hidden surface removal, polygonal point enclosure searching and so on. In all applications, we are able to either improve existing bounds or establish new bounds.

关键词： COMPUTATIONAL GEOMETRY persistent data structures persistent BINARY-BINARY SEARCH TREES RAY-SHOOTING

来源：评论

学校读者我要写书评

暂无评论

EFFICIENTLY COMPUTING AND REPRESENTING ASPECT GRAPHS OF POLYHEDRAL OBJECTS

引用

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE 1991年第6期13卷 542-551页

作者： GIGUS, Z CANNY, J SEIDEL, R Dept. of Electr. Eng. & Comput. Sci. California Univ. Berkeley CA USA

We present an efficient algorithm and a new data structure for computing and representing the aspect graph of polyhedral objects under orthographic projection. The aspect graph is an approach to representing 3-D objects by a set of 2-D views, for the purpose of object recognition. In this approach, the viewpoint space is partitioned into regions such that in each region the qualitative structure of the line drawing does not change. The viewing data of an object is the partition of the viewpoint space together with a representative view in each region. The algorithm computes the viewing data for line drawings of polyhedral objects under orthographic projection. For an object of n vertices whose partition is of size m, the partition is constructed in O(n4 log n + m log m) time. After computing the partition, given a view of the object in one region, we use a novel data structure to construct the set of all views in O(C(T)) time and space, where C(T) is the sum of the number of changes between all pairs of neighboring views. A view of size s can be retrieved from this data structure in O(log C(T) + s) time.

关键词： ASPECT GRAPHS LINE DRAWING INTERPRETATION MODEL BASED VISION OBJECT RECOGNITION persistent data structures POLYHEDRAL OBJECTS

来源：评论

学校读者我要写书评

暂无评论

THE OBERON SYSTEM

引用

SOFTWARE-PRACTICE & EXPERIENCE 1989年第9期19卷 857-893页

作者： WIRTH, N GUTKNECHT, J Institut für Computersysteme Eidgenössische Technische Hochschule ETH-Zentrum CH-8092 Zürich Switzerland

In this paper we describe an operating system for a workstation designed and implemented by the authors within two and a half years. It includes memory management and module loader, a file system, a viewer system, editors for text and graphics, a compiler, a server interface and various tools. The primary motivation was to demonstrate the feasibility of a small, yet highly flexible and powerful, system, a system that is a (decimal) order of magnitude smaller than commonly used operating systems. This is possible due to regularity of concepts and concentration on the essential. The benefits are not only fewer resources needed, but elegance and generality of concepts resulting in transparency and convenience of use and increased reliability. A corner-stone of this approach is genuine extensibility, which is achieved by a new language, in particular by a facility called type extension. It allows for the integration of variables (objects) of a new, extended type in structures of elements of an existing base type.

关键词： Operating system Multi-tasking Storage management Viewer system Object-oriented programming persistent data structures

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：