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

Fully-dynamic and Kinetic Conflict-Free Coloring of Intervals with Respect to Points

International Journal of Computational Geometry & Applications 2019年第1期29卷 49-72页

作者： Mark de Berg Tim Leijsen Aleksandar Markovic André van Renssen Marcel Roeloffzen Gerhard Woeginger Eindhoven University of Technology 5600 MB Eindhoven the Netherlands University of Sydney NSW 2006 Australia Eindhoven University of Technology 5600 MB Eindhoven The Netherlands RWTH Aachen University 52062 Aachen Germany

We introduce the fully-dynamic conflict-free coloring problem for a set S of intervals in ℝ 1 with respect to points, where the goal is to maintain a conflict-free coloring for S under insertions and deletions. A coloring is conflict-free if for each point p contained in some interval, p is contained in an interval whose color is not shared with any other interval containing p . We investigate trade-offs between the number of colors used and the number of intervals that are recolored upon insertion or deletion of an interval. Our results include: a lower bound on the number of recolorings as a function of the number of colors, which implies that with O ( 1 ) recolorings per update the worst-case number of colors is Ω ( log n / log log n ) , and that any strategy using O ( 1 / 𝜀 ) colors needs Ω ( 𝜀 n 𝜀 ) recolorings; a coloring strategy that uses O ( log n ) colors at the cost of O ( log n ) recolorings, and another strategy that uses O ( 1 / 𝜀 ) colors at the cost of O ( n 𝜀 / 𝜀 ) recolorings; stronger upper and lower bounds for special cases. We also consider the kinetic setting where the intervals move continuously (but there are no insertions or deletions); here we show how to maintain a coloring with only four colors at the cost of three recolorings per event and show this is tight.

关键词： Conflict-free coloring dynamic data structures kinetic data structures

来源：评论

学校读者我要写书评

暂无评论

A Fast Vertex-Swap Operator for the Prize-Collecting Steiner Tree Problem 18th

A Fast Vertex-Swap Operator for the Prize-Collecting Steiner...

引用

18th International Conference on Computational Science (ICCS)

作者： Ming, Yi-Fei Chen, Si-Bo Chen, Yong-Quan Fu, Zhang-Hua Chinese Univ Hong Kong Inst Robot & Intelligent Mfg Robot Lab Logist Serv Shenzhen 518172 Peoples R China

ISBN: (纸本)9783319937014;9783319937007

The prize-collecting Steiner tree problem (PCSTP) is one of the important topics in computational science and operations research. The vertex-swap operation, which involves removal and addition of a pair of vertices based on a given minimum spanning tree (MST), has been proven very effective for some particular PCSTP instances with uniform edge costs. This paper extends the vertex-swap operator to make it applicable for solving more general PCSTP instances with varied edge costs. Furthermore, we adopt multiple dynamic data structures, which guarantee that the total time complexity for evaluating all the O(n(2)) possible vertex-swap moves is bounded by O(n) . O(m . log n), where n and m denote the number of vertices and edges respectively (if we run Kruskal's algorithm with a Fibonacci heap from scratch after swapping any pair of vertices, the total time complexity would reach O(n(2)) . O(m+ n .log n)). We also prove that after applying the vertex-swap operation, the resulting solutions are necessarily MSTs (unless infeasible).

关键词： Computational complexity Network design Prize-collecting Steiner tree Vertex-swap operator dynamic data structures

来源：评论

学校读者我要写书评

暂无评论

Shape Abstractions with Support for Sharing and Disjunctions

Shape Abstractions with Support for Sharing and Disjunctions

引用

作者： Huisong Li Ecole Normale Superieure

学位级别：博士

Shape analyses rely on expressive families of logical properties to infer complex structural in- variants, such that memory safety, structure preservation and other memory properties of pro- grams dealing with dynamic data structures can be automatically verified. Many such analyses manipulate abstract memory states that consist of separating conjunctions of basic predicates describing atomic blocks or summary predicates that describe unbounded heap regions like lists or trees using inductive definitions. Moreover, they use finite disjunctions of abstract memory states in order to take into account dissimilar shapes. Although existing analyses enable local reasoning of memory regions, they do, however, have the following issues: (1) The summary predicates are not expressive enough to describe precisely all the dynamic data structures. In particular, a fairly large number of data structures with unbounded sharing, such as graphs, cannot be described inductively in a local manner; (2) operations that read or write into summaries rely on materialization of memory cells. The materialization operation in general creates new disjunctions, yet the size of disjunctions should be kept small for the sake of efficiency. However, local predicates are not enough to determine the right set of disjuncts that should be clumped together and to define precise abstract join and widen operations. In this thesis, we study separating conjunction-based shape predicates and the related abstract operations, in particular, abstract joining and widening operations that lead to critical modifi- cations of abstract states. We seek a lightweight way to enable some global reasoning in existing shape analyses such that shape predicates are more expressive for abstracting data structures with unbounded sharing and disjuncts can be clumped precisely and efficiently. We propose a shape abstraction based on set variables that when integrated with inductive definitions enables the specification and sha

关键词： Static analysis dynamic data structures separation logic disjunctions

来源：评论

学校读者我要写书评

暂无评论

Packed Compressed Sparse Row: A dynamic Graph Representation

Packed Compressed Sparse Row: A Dynamic Graph Representation

引用

IEEE High Performance Extreme Computing Conference (HPEC)

作者： Wheatman, Brian Xu, Helen MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA

ISBN: (纸本)9781538659892

Perhaps the most popular sparse graph storage format is Compressed Sparse Row (CSR). CSR excels at storing graphs compactly with minimal overhead, allowing for fast traversals, lookups, and basic graph computations such as PageRank. Since elements in CSR format are packed together, additions and deletions often require time linear in the size of the graph. We introduce a new dynamic sparse graph representation called Packed Compressed Sparse Row (PCSR), based on an array-based dynamic data structure called the Packed Memory Array. PCSR is similar to CSR, but leaves spaces between elements, allowing for asymptotically faster insertions and deletions in exchange for a constant factor slowdown in traversals and a constant factor increase in space overhead. Our contributions are twofold. We describe PCSR and review the theoretical guarantees for update, insert, and search for PCSR. We also implemented PCSR as well as other basic graph storage formats and report our findings on a variety of benchmarks. PCSR supports inserts orders of magnitude faster than CSR and is only a factor of two slower on graph traversals. Our results suggest that PCSR is a lightweight dynamic graph representation that supports fast inserts and competitive searches.

关键词： sparse graphs sparse matrices storage formats compressed sparse row packed memory array dynamic data structures

来源：评论

学校读者我要写书评

暂无评论

Model-driven runtime resource predictions for advanced mechatronic systems with dynamic data structures

Model-driven runtime resource predictions for advanced mecha...

引用

13th IEEE International Symposium on Object/Component/Service-Oriented Real-Time Distributed Computing (ISORC)

作者： Henkler, Stefan Oberthuer, Simon Giese, Holger Seibel, Andreas OFFIS Oldenburg EE Architecture Anal & Design Software Engn Grp D-26121 Oldeburg Germany Univ Paderborn Heinz Nixdorf Inst Syst Res Grp D-33098 Paderborn Germany Univ Potsdam Hasso Plattner Insitute Syst Anal & Modeling Grp D-14482 Potsdam Germany

ISBN: (纸本)9780769540375

The next generation of advanced mechatronic systems is expected to enhance their functionality and improve their performance by context-dependent behavior. Therefore, these systems require to represent information about their complex environment and changing sets of collaboration partners internally. This requirement is in contrast to the usually assumed static structures of embedded systems. In this paper, we present a model-driven approach which overcomes this situation by supporting dynamic data structures while still guaranteeing that valid worst-case execution times can be derived. It supports a flexible resource manager which avoids to operate with the prohibitive coarse worst-case boundaries but instead supports to run applications in different profiles which guarantee different resource requirements and put unused resources in a profile at other applications' disposal. By supporting the proper estimation of worst case execution time (WCET) and worst case number of iteration (WCNI) at runtime, we can further support to create new profiles, add or remove them at runtime in order to minimize the over-approximation of the resource consumption resulting from the dynamic data structures required for the outlined class of advanced systems.

关键词： Model-Driven Engineering Safety Critical Systems dynamic data structures Flexible Resource Manager Runtime WCET Analysis

来源：评论

学校读者我要写书评

暂无评论

TOWARDS AN OPTIMAL METHOD FOR dynamic PLANAR POINT LOCATION

引用

SIAM JOURNAL ON COMPUTING 2018年第6期47卷 2337-2361页

作者： Chan, Timothy M. Nekrich, Yakov Univ Illinois Dept Comp Sci Urbana IL 61801 USA Univ Waterloo Cheriton Sch Comp Sci Waterloo ON N2L 3G1 Canada

We describe a fully dynamic linear-space data structure for point location in connected planar subdivisions, or more generally vertical ray shooting among nonintersecting line segments, that supports queries in O(logn(log logn)(2)) time and updates in O(log n log log n) time. This is the first data structure that achieves close to logarithmic query and update time simultaneously, ignoring log log n factors. We further show how to reduce the query time to O(log n log log n) in the RAM model with randomization. Alternatively, the query time can be lowered to O(logn) if the update time is increased to O(log(l+epsilon) n) for any constant epsilon > 0, or vice versa.

关键词： point location dynamic data structures computational geometry

来源：评论

学校读者我要写书评

暂无评论

An efficient data structure for dynamic two-dimensional reconfiguration

引用

JOURNAL OF SYSTEMS ARCHITECTURE 2017年 75卷 15-25页

作者： Fekete, Sandor P. Reinhardt, Jan-Marc Scheffer, Christian TU Braunschweig Dept Comp Sci Algorithm Braunschweig Germany TU Braunschweig Dept Comp Sci Braunschweig Germany

In the presence of dynamic insertions and deletions into a partially reconfigurable FPGA, fragmentation is unavoidable. This poses the challenge of developing efficient approaches to dynamic defragmentation and reallocation. One key aspect is to develop efficient algorithms and data structures that exploit the two-dimensional geometry of a chip, instead of just one. We propose a new method for this task, based on the fractal structure of a quadtree, which allows dynamic segmentation of the chip area, along with dynamically adjusting the necessary communication infrastructure. We describe a number of algorithmic aspects, and present different solutions. We also provide a number of basic simulations that indicate that the theoretical worst-case bound may be pessimistic. (C) 2017 Elsevier B.V. All rights reserved.

关键词： FPGAs Partial reconfiguration Two-dimensional reallocation Defragmentation dynamic data structures Insertions and deletions

来源：评论

学校读者我要写书评

暂无评论

dynamic Planar Embeddings of dynamic Graphs

引用

THEORY OF COMPUTING SYSTEMS 2017年第4期61卷 1054-1083页

作者： Holm, Jacob Rotenberg, Eva Univ Copenhagen Dept Comp Sci Univ Pk 1 DK-2100 Copenhagen Denmark

We present an algorithm to support the dynamic embedding in the plane of a dynamic graph. An edge can be inserted across a face between two vertices on the face boundary (we call such a vertex pair linkable), and edges can be deleted. The planar embedding can also be changed locally by flipping components that are connected to the rest of the graph by at most two vertices. Given vertices u, v, linkable(u, v) decides whether u and v are linkable in the current embedding, and if so, returns a list of suggestions for the placement of (u, v) in the embedding. For non-linkable vertices u, v, we define a new query, one-flip-linkable(u, v) providing a suggestion for a flip that will make them linkable if one exists. We support all updates and queries in O(log(2) n) time. Our time bounds match those of Italiano et al. for a static (flipless) embedding of a dynamic graph. Our new algorithm is simpler, exploiting that the complement of a spanning tree of a connected plane graph is a spanning tree of the dual graph. The primal and dual trees are interpreted as having the same Euler tour, and a main idea of the new algorithm is an elegant interaction between top trees over the two trees via their common Euler tour.

关键词： data structures Planar graphs Graph algorithms Graph embeddings dynamic data structures Graph theory

来源：评论

学校读者我要写书评

暂无评论

Custom Multicache Architectures for Heap Manipulating Programs

引用

IEEE TRANSACTIONS ON COMPUTER-AIDED DESIGN OF INTEGRATED CIRCUITS AND SYSTEMS 2017年第5期36卷 761-774页

作者： Winterstein, Felix Fleming, Kermin E. Yang, Hsin-Jung Constantinides, George A. Imperial Coll London Dept Elect & Elect Engn London SW7 2BT England Intel Corp Software Serv Grp Hudson MA 01749 USA MIT Dept Elect Engn & Comp Sci Cambridge MA 02139 USA

Memory-intensive implementations often require access to an external, off-chip memory which can substantially slow down an field-programmable gate array accelerator due to memory bandwidth limitations. Buffering frequently reused data on chip is a common approach to address this problem and the optimization of the cache architecture introduces yet another complex design space. This paper presents a high-level synthesis (HLS) design aid that automatically generates parallel multicache systems which are tailored to the specific requirements of the application. Our program analysis identifies nonoverlap-ping memory regions, supported by private caches, and regions which are shared by parallel units after parallelization, which are supported by coherent caches and synchronization primitives. It also decides whether the parallelization is legal with respect to data dependencies. The novelty of this paper is the focus on programs using dynamically allocated, pointer-based data structures which, while common in software engineering, remain difficult to analyze and are beyond the scope of the overwhelming majority of HLS techniques to date. Second, we devise a high-level cache performance estimation to find a heterogeneous configuration of cache sizes that maximizes the performance of the multicache system subject to an on-chip memory resource constraint. We demonstrate our technique with three case studies of applications using dynamic data structures and use Xilinx Vivado HLS as an exemplary HLS tool. We show up to 15x speed-up after parallelization of the HLS implementations and the insertion of the application- specific distributed hybrid multicache architecture.

关键词： Caching schemes dynamic data structures field-programmable gate array (FPGA) high-level synthesis (HLS) memory system separation logic

来源：评论

学校读者我要写书评

暂无评论

Model-driven runtime resource predictions for advanced mechatronic systems with dynamic data structures

引用

COMPUTER SYSTEMS SCIENCE AND ENGINEERING 2011年第6期26卷 505-518页

关键词： Model-Driven Engineering Safety Critical Systems dynamic data structures Flexible Resource Manager Runtime WCET Analysis

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：