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

15th International Conference on Graph Transformation (ICGT) Held as Part of Conference on Software Technologies - Applications and Foundations (STAF)

作者： Weber, Jens H. Univ Victoria Victoria BC Canada

ISBN: (纸本)9783031098437;9783031098420

Existing graph transformation (GT) tools treat graphs as ephemeral data structures, i.e., the successful application of a GT rule to a graph G rewrites that graph to produce a modified graph G'. The original graph G is lost during that update. In contrast to ephemeral data structures, persistent data structures preserve access to all previous versions when data is modified and fully persistent data structures even allow all previous versions to be modified. In earlier work, we introduced the Graph Rewriting and Persistence Engine Grape as a tool for specifying and executing transformations on large-scale graphs and integrated it with a computational notebook platform (GrapePress). While the term "persistence" has been in the tool's acronym from the start, it was chosen to indicate that graphs were maintained in a database with transactional support. Until now, Grape (and GrapePress) treated graphs as ephemeral data structures, i.e., previous graph versions were not retained upon modification. This paper presents a major revision of the tool (called GrapeVine) to support functional graph rewriting based on a fully persistent data structure.

关键词： Graph transformations Grape GrapeVine persistent data structures tools graph processes computational notebook tools

来源：评论

学校读者我要写书评

暂无评论

Cache-Line Transactions: Building Blocks for persistent Kernel data structures Enabled by AspectC plus 10

Cache-Line Transactions: Building Blocks for Persistent Kern...

引用

10th Workshop on Programming Languages and Operating Systems (PLOS)

作者： Koeppen, Marcel Traue, Jana Borchert, Christoph Nolte, Joerg Spinczyk, Olaf Osnabruck Univ Osnabruck Germany Brandenburg Tech Univ Cottbus Cottbus Germany

ISBN: (纸本)9781450370172

With the availability of systems that contain large amounts of byte-addressable non-volatile memory (NVRAM), there is a growing need for data structures that can be mapped into a process's address space and be used without data (de-)serialization. While NVRAM is able to retain memory contents during system failure and power loss, data consistency has to be preserved by using transactional operations for data manipulation. This paper describes a lightweight and efficient transaction mechanism for small data structures in memory-mapped NVRAM. The size per data structure is limited to half a cache-line, so that the approach cannot serve as a general purpose mechanism for arbitrary applications, but could be used within an operating system as a low-level building block for more complex data structures. By using aspect-oriented programming with AspectC++, the mechanism can be used in an almost transparent manner, which helps to avoid many possible sources for bugs.

关键词： Non-Volatile Memory persistent data structures Aspect-Oriented Programming

来源：评论

学校读者我要写书评

暂无评论

Almost linear time algorithms for minsum k-sink problems on dynamic flow path networks

引用

THEORETICAL COMPUTER SCIENCE 2021年 873卷 87-113页

作者： Higashikawa, Yuya Katoh, Naoki Teruyama, Junichi Watase, Koji Univ Hyogo Sch Social Informat Sci Kobe Hyogo Japan Kwansei Gakuin Univ Sch Sci & Technol Sanda Japan

We address the facility location problems on dynamic flow path networks. A dynamic flow path network consists of an undirected path with positive edge lengths, positive edge capacities, and positive vertex weights. A path can be considered as a road, an edge length as the distance along the road and a vertex weight as the number of people at the site. An edge capacity limits the number of people that can enter the edge per unit time. In the dynamic flow network, given particular points on edges or vertices, called sinks, all the people evacuate from the vertices to the sinks as quickly as possible. The problem is to find the location of sinks on a dynamic flow path network in such a way that the aggregate evacuation time (i.e., the sum of evacuation times for all the people) to sinks is minimized. We consider two models of the problem: the confluent flow model and the non-confluent flow model. In the former model, the way of evacuation is restricted so that all the people at a vertex have to evacuate to the same sink, and in the latter model, there is no such restriction. In this paper, for both the models, we develop algorithms which run in almost linear time regardless of the number of sinks. It should be stressed that for the confluent flow model, our algorithm improves upon the previous result by Benkoczi et al. [Theoretical Computer Science, 2020], and one for the non-confluent flow model is the first polynomial time algorithm. (C)) 2021 The Author(s). Published by Elsevier B.V.

关键词： Dynamic flow networks Facility location problems Minimum k-link path problem persistent data structures

来源：评论

学校读者我要写书评

暂无评论

Almost Optimal Exact Distance Oracles for Planar Graphs

引用

JOURNAL OF THE ACM 2023年第2期70卷 12-12页

作者： Charalampopoulos, Panagiotis Gawrychowski, Pawel Long, Yaowei Mozes, Shay Pettie, Seth Weimann, Oren Wulff-Nilsen, Christian Birkbeck Univ London Dept Comp Sci & Informat Syst Malet St London WC1E 7HX England Univ Wroclaw Inst Informatyki Ul Joliot Curie 15 PL-50383 Wroclaw Poland Tsinghua Univ Inst Interdisciplinary Informat Sci Beijing 100084 Peoples R China Reichman Univ Efi Arazi Sch Comp Sci IL-4610101 Herzliyya Israel Univ Michigan Comp Sci & Engn 2260 Hayward St Ann Arbor MI 48109 USA Univ Haifa City CampusHa Namal St 67 IL-3303221 Haifa Israel Univ Copenhagen BARC Dept Comp Sci Univ Pk 1 DK-2100 Copenhagen O Denmark

We consider the problem of preprocessing a weighted directed planar graph in order to quickly answer exact distance queries. The main tension in this problem is between space S and query time Q, and since the mid-1990s all results had polynomial time-space tradeoffs, e.g., Q = (Theta) over tilde (n/root S) or Q = (Theta) over tilde (n(5/2)/S-3/2). In this article we show that there is no polynomial tradeoff between time and space and that it is possible to simultaneously achieve almost optimal space n(1+o(1)) and almost optimal query time n(o(1)). More precisely, we achieve the following space-time tradeoffs: n(1+o(1)) space and log(2+o(1)) n query time, n log(2+o(1)) n space and n(o(1)) query time, n(4/3+o(1)) space and log(1+o(1)) n query time. We reduce a distance query to a variety of point location problems in additively weighted Voronoi diagrams and develop new algorithms for the point location problem itself using several partially persistent dynamic tree data structures.

关键词： Planar graphs Voronoi diagrams distance oracles persistent data structures

来源：评论

学校读者我要写书评

暂无评论

Cheating Like The Neighbors: Logarithmic Complexity For Fitness Evaluation In Genetic Algorithms

Cheating Like The Neighbors: Logarithmic Complexity For Fitn...

引用

IEEE Congress on Evolutionary Computation (IEEE CEC)

作者： Pitzer, Erik Affenzeller, Michael Univ Appl Sci Upper Austria Dept Software Engn Hagenberg Austria

ISBN: (纸本)9781728183923

While neighborhood-based algorithms can use incremental evaluation to obtain the fitness of a modified solution candidate, genetic crossover makes changes that are too big to easily allow reusing previous quality values. In this paper, we extend our previous work and evaluate the possibility of extending persistent data structures to carry residual fitness values that can be reused for later evaluation of derived solution candidates when applied to Multidimensional 0-1 Knapsack Problems. We show potential speedups especially on very large problem instances when compared to classic array-based implementations.

关键词： persistent data structures metaheuristics algorithms optimization genetic algorithms crossover

来源：评论

学校读者我要写书评

暂无评论

Fully persistent B-trees

引用

THEORETICAL COMPUTER SCIENCE 2020年 841卷 10-26页

作者： Brodal, Gerth Stolting Sioutas, Spyros Tsakalidis, Konstantinos Tsichlas, Kostas Aarhus Univ Dept Comp Sci Aarhus Denmark Univ Patras Comp Engn & Informat Dept Patras Greece Univ Liverpool Dept Comp Sci Liverpool Merseyside England

We present efficient fully persistent B-trees in the I/O model with block size B that support range searches on t reported elements at any accessed version of size n in O (log(B) n t/B) I/Os and updates at any accessed version in O (log(B) n + log(2) B) amortized I/Os, using O (m/B) disk blocks after m updates. This improves both the query and update I/O-efficiency of the previous fully persistent B-trees of Lanka and Mays (ACM SIGMOD ICMD 1991). To achieve the result, we introduce an implementation for ephemeral B-trees that supports searches and updates in O (log(B) n) I/Os, using O (n/B) blocks, where moreover every update makes a worst-case constant number of modifications to the structure. We make these B-trees fully persistent using an I/O-efficient method for full persistence, inspired by the node-splitting method of Driscoll et al. (JCSS 1989). Interesting in its own right, the method is generic enough to be applied to any external memory pointer-based data structure with maximum in-degree d(in) and out-degree O (B), where every node occupies a constant number of blocks on disk. For a user-specified parameter pi = Omega (d(in)), we achieve O (pi/B + log(2) pi) I/O-overhead per access to a field of an ephemeral block and amortized O (pi/B + log(2) pi + din/pi log(2) B) I/O-overhead and O (1/B) block space-overhead per modification to the ephemeral structure. Crown Copyright (C) 2020 Published by Elsevier B.V. All rights reserved.

关键词： persistent data structures External memory Range searching Big data Versioned data bases

来源：评论

学校读者我要写书评

暂无评论

To-Many or To-One? All-in-One! Efficient Purely Functional Multi-maps with Type-Heterogeneous Hash-Tries 2018

To-Many or To-One? All-in-One! Efficient Purely Functional M...

引用

39th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)

作者： Steindorfer, Michael J. Vinju, Jurgen J. Delft Univ Technol Delft Netherlands Ctr Wiskunde & Informat Amsterdam Netherlands TU Eindhoven Eindhoven Netherlands

ISBN: (纸本)9781450356985

An immutable multi-map is a many-to-many map data structure with expected fast insert and lookup operations. This data structure is used for applications processing graphs or many-to-many relations as applied in compilers, runtimes of programming languages, or in static analysis of object-oriented systems. Collection data structures are assumed to carefully balance execution time of operations with memory consumption characteristics and need to scale gracefully from a few elements to multiple gigabytes at least. When processing larger in-memory data sets the overhead of the data structure encoding itself becomes a memory usage bottleneck, dominating the overall performance. In this paper we propose AXIOM, a novel hash-trie data structure that allows for a highly efficient and type-safe multi-map encoding by distinguishing inlined values of singleton sets from nested sets of multi-mappings. AXIOM strictly generalizes over previous hash-trie data structures by supporting the processing of fine-grained type-heterogeneous content on the implementation level (while API and language support for type-heterogeneity are not scope of this paper). We detail the design and optimizations of AXIOM and further compare it against state-of-the-art immutable maps and multi-maps in Java, Scala and Clojure. We isolate key differences using microbenchmarks and validate the resulting conclusions on a case study in static analysis. AXIOM reduces the key-value storage overhead by 1.87 x;with specializing and inlining across collection boundaries it improves by 5.1 x.

关键词： data structures persistent data structures functional programming hashtable multi-map many-to-many relation graph optimization performance JVM

来源：评论

学校读者我要写书评

暂无评论

Recoverable Mutual Exclusion Under System-Wide Failures 18

Recoverable Mutual Exclusion Under System-Wide Failures

引用

37th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC)

作者： Golab, Wojciech Hendler, Danny Univ Waterloo Dept Elect & Comp Engn Waterloo ON Canada Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel

ISBN: (纸本)9781450357951

Recoverable mutual exclusion (RME) is a variation on the classic mutual exclusion (ME) problem that allows processes to crash and recover. The time complexity of RME algorithms is quantified in the same way as for ME, namely by counting remote memory references-expensive memory operations that traverse the processor-to-memory interconnect. Prior work has established that the RMR complexity of the RME problem for n processes is T(logn) for the class of algorithms that use read/write registers and single-word comparison primitives such as Compare-And-Swap (Golab and Ramaraju 2016), O(logn/log logn) for the class of algorithms that use read/write registers and additional single-word read-modify-primitives such as Fetch-And-Store (Golab and Hendler 2017), and T(1) for the class of algorithms that use read/write registers and specialized double-word read-modify-write primitives (Golab and Hendler 2017). These complexity bounds hold in a model of computation where processes may fail independently, and where a process that fails while accessing the mutex is required to recover eventually. This body of work leaves open two important questions: (i) what is the tight bound on the RMR complexity of RME for the class of algorithms that use read/write registers and commonly supported single-word read-modify-primitives;and (ii) how is the RMR complexity of RME affected by variations in the failure model? This paper answers both questions partially by showing that RME can be solved using O(1) RMRs per passage in the worst case in a model where failures are system-wide (i.e., all processes crash simultaneously), and processes receive additional information from the environment regarding the occurrence of the failure. The upper bound algorithm we present relies crucially on a novel RMR-efficient barrier that processes use to synchronize recovery actions after each failure. The barrier uses read/write registers and single-word Compare-And-Swap only. Additionally, we present a transfo

关键词： Mutual exclusion recovery fault tolerance concurrency shared memory multi-core algorithms non-volatile main memory persistent data structures

来源：评论

学校读者我要写书评

暂无评论

Recoverable Mutual Exclusion in Sub-logarithmic Time 17

Recoverable Mutual Exclusion in Sub-logarithmic Time

引用

36th ACM Symposium on Principles of Distributed Computing (PODC)

作者： Golab, Wojciech Hendler, Danny Univ Waterloo Dept Elect & Comp Engn Waterloo ON Canada Ben Gurion Univ Negev Dept Comp Sci Beer Sheva Israel

ISBN: (纸本)9781450349925

关键词： Mutual exclusion recovery fault tolerance concurrency shared memory multi-core algorithms non-volatile main memory persistent data structures

来源：评论

学校读者我要写书评

暂无评论

Functional data Stuctures and Algorithms

Functional Data Stuctures and Algorithms

引用

作者： Straka, Milan Charles University of Prague

Title: Functional data structures and Algorithms Author: Milan Straka Institute: Computer Science Institute of Charles University Supervisor of the doctoral thesis: doc. Mgr. Zdeněk Dvořák, Ph.D, Computer Science Institute of Charles University Abstract: Functional programming is a well established programming paradigm and is becoming increasingly popular, even in industrial and commercial appli- cations. data structures used in functional languages are principally persistent, that is, they preserve previous versions of themselves when modified. The goal of this work is to broaden the theory of persistent data structures and devise efficient implementations of data structures to be used in functional languages. Arrays are without any question the most frequently used data structure. Despite being conceptually very simple, no persistent array with constant time access operation exists. We describe a simplified implementation of a fully per- sistent array with asymptotically optimal amortized complexity Θ(log log n) and especially a nearly optimal worst-case implementation. Additionally, we show how to effectively perform a garbage collection on a persistent array. The most efficient data structures are not necessarily based on asymptotically best structures. On that account, we also focus on data structure...

关键词： persistent data structures persistent arrays worst-case algorithms purely functional data structures Haskell

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：