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

53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC)

作者： Nekrich, Yakov Michigan Technol Univ Houghton MI 49931 USA

ISBN: (纸本)9781450380539

In this paper we describe a fully-dynamic data structure that supports point location queries in a connected planar subdivision with n edges. Our data structure uses O(n) space, answers queries in O(log n) time, and supports updates in O(log n) time. Our solution is based on a data structure for vertical ray shooting queries that supports queries and updates in O(log n) time.

关键词： computational geometry point location dynamic data structures

来源：评论

学校读者我要写书评

暂无评论

Maintaining the Union of Unit Discs under Insertions with Near-Optimal Overhead

引用

ACM TRANSACTIONS ON ALGORITHMS 2022年第3期18卷 26-26页

作者： Agarwal, Pankaj K. Cohen, Ravid Halperin, Dan Mulzer, Wolfgang Duke Univ Dept Comp Sci Box 90219 Durham NC 27708 USA Tel Aviv Univ Blavatnik Sch Comp Sci IL-6997801 Tel Aviv Israel Free Univ Berlin Inst Informat Takustr 9 D-14195 Berlin Germany

We present efficient dynamic data structures for maintaining the union of unit discs and the lower envelope of pseudo-lines in the plane. More precisely, we present three main results in this paper: (i) We present a linear-size data structure to maintain the union of a set of unit discs under insertions. It can insert a disc and update the union in O((k + 1) log(2) n) time, where n is the current number of unit discs and k is the combinatorial complexity of the structural change in the union due to the insertion of the new disc. It can also compute, within the same time bound, the area of the union after the insertion of each disc. (ii) We propose a linear-size data structure for maintaining the lower envelope of a set of x-monotone pseudo-lines. It can handle insertion/deletion of a pseudo-line in O(log(2) n) time;for a query point x(0) is an element of R, it can report, in O(logn) time, the point on the lower envelope with x-coordinate x(0);and for a query point q is an element of R-2, it can return all k pseudo-lines lying below q in time O(logn + k log(2) n). (iii) We present a linear-size data structure for storing a set of circular arcs of unit radius (not necessarily on the boundary of the union of the corresponding discs), so that for a query unit disc D, all input arcs intersecting D can be reported in O(n(1/2+e) + k) time, where k is the output size and e > 0 is an arbitrarily small constant. A unit-circle arc can be inserted or deleted in O(log(2) n) time.

关键词： Lower envelopes pseudo-lines unit discs intersection searching dynamic data structures tentative binary search

来源：评论

学校读者我要写书评

暂无评论

RESOLVING SINR QUERIES IN A dynamic SETTING

引用

SIAM JOURNAL ON COMPUTING 2020年第6期49卷 1271-1290页

作者： Aronov, Boris Bar-On, Gali Katz, Matthew J. NYU Tandon Sch Engn Dept Comp Sci & Engn Brooklyn NY 11201 USA Ben Gurion Univ Negev Dept Comp Sci IL-84105 Beer Sheva Israel

We consider a set of transmitters broadcasting simultaneously on the same frequency under the signal to interference plus noise ratio (SINR) model. Transmission power may vary from one transmitter to another, and a transmitter's signal strength at a given point is modeled by the transmitter's power divided by some constant power a of the distance it traveled. Roughly, a receiver at a given location can hear a specific transmitter only if the transmitter's signal is stronger by a specified ratio than the signals of all other transmitters combined. An SINR query is to determine whether a receiver at a given location can hear any transmitter, and if yes, which one. An approximate answer to an SINR query is such that one gets a definite YES or definite NO, when the ratio between the strongest signal and all other signals combined is well above or well below the reception threshold, while the answer in the intermediate range is allowed to be either YES or NO. We describe compact data structures that support approximate SINR queries in the plane in a dynamic context, i.e., where transmitters may be inserted and deleted over time. We distinguish between two main variants- uniform power and nonuniform power. In both variants the preprocessing time is O(n polylogn) and the amortized update time is O(polylogn), while the query time is O(polylogn) for uniform power, and randomized time O(-root n polylogn) with high probability for nonuniform power. Finally, we observe that in the static context the latter data structure can be implemented differently, so that the query time is also O(polylogn), thus significantly improving all previous results for this problem.

关键词： computational geometry wireless networks SINR dynamic data structures interference cancellation

来源：评论

学校读者我要写书评

暂无评论

dynamic index and LZ factorization in compressed space

引用

DISCRETE APPLIED MATHEMATICS 2020年 274卷 116-129页

作者： Nishimoto, Takaaki Tomohiro, I Inenaga, Shunsuke Bannai, Hideo Takeda, Masayuki RIKEN Ctr Adv Intelligence Project Tokyo Japan Kyushu Univ Dept Informat Fukuoka Japan Kyushu Inst Technol Fukuoka Japan

In this paper, we propose a new dynamic compressed index of O(w) space for a dynamic text T, where w = O(min(z log N lot M, N)) is the size of the signature encoding of T, z is the size of the Lempel Ziv77 (L277) factorization of T, N is the length of T, and M >= N is the maximum length of T. Our index supports searching for a pattern P in T in O(vertical bar P vertical bar f(A)+log w log vertical bar P vertical bar log* M(log N+log vertical bar P vertical bar log* M)+occ log N) time and insertion/deletion of a substring of lengthy in O((y + log N log* M) log w log N log* M) time, where occ is the number of occurrences of P in T and f(A) = O(min{log logM log log w/log log log M, root log w/log log w}).Also, we propose a new space-efficient 1277 factorization algorithm for a given text T, which runs in O(Nf(A) + z log w log(3) N(log* N)(2)) time with O(w) working space. (C) 2019 Elsevier B.V. All rights reserved.

关键词： dynamic texts 1277 factorization dynamic index Compressed data structures dynamic data structures

来源：评论

学校读者我要写书评

暂无评论

dynamic Geometric Set Cover and Hitting Set

引用

ACM TRANSACTIONS ON ALGORITHMS 2022年第4期18卷 40-40页

作者： Agarwal, Pankaj Chang, Hsien-Chih Suri, Subhash Xiao, Allen Xue, Jie Duke Univ Dept Comp Sci Durham NC 27708 USA Dartmouth Coll Dept Comp Sci Hanover NH 03755 USA Univ Calif Santa Barbara Dept Comp Sci Santa Barbara CA 93106 USA New York Universtiy Shanghai Shanghai 200122 Peoples R China

We investigate dynamic versions of geometric set cover and hitting set where points and ranges may be inserted or deleted, and we want to efficiently maintain an (approximately) optimal solution for the current problem instance. While their static versions have been extensively studied in the past, surprisingly little is known about dynamic geometric set cover and hitting set. For instance, even for the most basic case of one-dimensional interval set cover and hitting set, no nontrivial results were known. The main contribution of our article are two frameworks that lead to efficient data structures for dynamically maintaining set covers and hitting sets in R-1 and R-2. The first framework uses bootstrapping and gives a (1 + epsilon)-approximate data structure for dynamic interval set cover in R-1 with O(n(alpha)/epsilon) amortized update time for any constant alpha > 0;in R-2, this method gives O(1)-approximate data structures for unit-square set cover and hitting set with O(n(1/2+alpha)) amortized update time. The second framework uses local modification and leads to a (1 + epsilon)approximate data structure for dynamic interval hitting set in R-1 with (O) over tilde (1/epsilon) amortized update time;in R-2, it gives O(1)-approximate data structures for unit-square set cover and hitting set in the partially dynamic settings with (O) over tilde (1) amortized update time.

关键词： Geometric set cover geometric hitting set dynamic data structures

来源：评论

学校读者我要写书评

暂无评论

dynamic Space Efficient Hashing

引用

ALGORITHMICA 2019年第8期81卷 3162-3185页

作者： Maier, Tobias Sanders, Peter Walzer, Stefan Karlsruhe Inst Technol Karlsruhe Germany Tech Univ Ilmenau Ilmenau Germany

We consider space efficient hash tables that can grow and shrink dynamically and are always highly space efficient, i.e., their space consumption is always close to the lower bound even while growing and when taking into account storage that is only needed temporarily. None of the traditionally used hash tables have this property. We show how known approaches like linear probing and bucket cuckoo hashing can be adapted to this scenario by subdividing them into many subtables or using virtual memory overcommitting. However, these rather straightforward solutions suffer from slow amortized insertion times due to frequent reallocation in small increments. Our main result is dynamic Space Efficient Cuckoo Table (DySECT ) which avoids these problems. DySECT consists of many subtables which grow by doubling their size. The resulting inhomogeneity in subtable sizes is counterbalanced by the flexibility available in bucket cuckoo hashing where each element can go to several buckets each of which containing several cells. Experiments indicate that DySECT works well with loads up to 98%. With up to 1.9 times better performance than the next best solution. Additionally, we give a tight theoretical analysis for the possible load threshold of DySECT, i.e., a bound where with high probability the table can be filled up to that load but not above said load. This load also matches our experimental findings.

关键词： dynamic data structures Open addressing Closed hashing Cuckoo hashing Space efficiency

来源：评论

学校读者我要写书评

暂无评论

Algorithm-based fault recovery of adaptively refined parallel multilevel grids

引用

INTERNATIONAL JOURNAL OF HIGH PERFORMANCE COMPUTING APPLICATIONS 2019年第1期33卷 189-211页

作者： Stals, Linda Australian Natl Univ MSI John Dedman Bldg 27 Canberra ACT 2601 Australia

On future extreme scale computers, it is expected that faults will become an increasingly serious problem as the number of individual components grows and failures become more frequent. This is driving the interest in designing algorithms with built-in fault tolerance that can continue to operate and that can replace data even if part of the computation is lost in a failure. For fault-free computations, the use of adaptive refinement techniques in combination with finite element methods is well established. Furthermore, iterative solution techniques that incorporate information about the grid structure, such as the parallel geometric multigrid method, have been shown to be an efficient approach to solving various types of partial different equations. In this article, we present an advanced parallel adaptive multigrid method that uses dynamic data structures to store a nested sequence of meshes and the iteratively evolving solution. After a fail-stop fault, the data residing on the faulty processor will be lost. However, with suitably designed data structures, the neighbouring processors contain enough information so that a consistent mesh can be reconstructed in the faulty domain with the goal of resuming the computation without having to restart from scratch. This recovery is based on a set of carefully designed distributed algorithms that build on the existing parallel adaptive refinement routines, but which must be carefully augmented and extended.

关键词： Fault-tolerant algorithms adaptive finite elements multigrid dynamic data structures

来源：评论

学校读者我要写书评

暂无评论

dynamic conflict-free colorings in the plane

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2019年 78卷 61-73页

作者： de Berg, Mark Markovic, Aleksandar TU Eindhoven Eindhoven Netherlands

We study dynamic conflict-free colorings in the plane, where the goal is to maintain a conflict-free coloring (CF-coloring for short) under insertions and deletions. First we consider CF-colorings of a set S of unit squares with respect to points. Our method maintains a CF-coloring that uses O(log n) colors at any time, where n is the current number of squares in S, at the cost of only O(log n) recolorings per insertion or deletion of a square. We generalize the method to rectangles whose sides have lengths in the range [1, c], where c is a fixed constant. Here the number of colors used becomes O (log(2) n). The method also extends to arbitrary rectangles whose coordinates come from a fixed universe of size N, yielding O (log(2) N log(2) n) colors. The number of recolorings for both methods stays in O(logn). We then present a general framework to maintain a CF-coloring under insertions for sets of objects that admit a unimax coloring with a small number of colors in the static case. As an application we show how to maintain a CF-coloring with O (log(3) n) colors for disks (or other objects with linear union complexity) with respect to points at the cost of O (logn) recolorings per insertion. We extend the framework to the fully-dynamic case when the static unimax coloring admits weak deletions. As an application we show how to maintain a CF-coloring with O (root n log(2) n) colors for points with respect to rectangles, at the cost of O (logn) recolorings per insertion and O(1) recolorings per deletion. These are the first results on fully-dynamic CF-colorings in the plane, and the first results for semi-dynamic CF-colorings for non-congruent objects. (C) 2018 Published by Elsevier B.V.

关键词： Conflict-free colorings dynamic data structures

来源：评论

学校读者我要写书评

暂无评论

Concurrent Hash Tables: Fast and General(?)!

引用

ACM TRANSACTIONS ON PARALLEL COMPUTING 2019年第4期5卷 1–32页

作者： Maier, Tobias Sanders, Peter Dementiev, Roman Karlsruhe Inst Technol Kaiserstr 12 D-76131 Karlsruhe Germany Intel Deutschland GmbH Campeon 10-12 D-85579 Neubiberg Germany

Concurrent hash tables are one of the most important concurrent data structures, which are used in numerous applications. For some applications, it is common that hash table accesses dominate the execution time. To efficiently solve these problems in parallel, we need implementations that achieve speedups in highly concurrent scenarios. Unfortunately, currently available concurrent hashing libraries are far away from this requirement, in particular, when adaptively sized tables are necessary or contention on some elements occurs. Our starting point for better performing data structures is a fast and simple lock-free concurrent hash table based on linear probing that is, however, limited to word-sized key-value types and does not support dynamic size adaptation. We explain how to lift these limitations in a provably scalable way and demonstrate that dynamic growing has a performance overhead comparable to the same generalization in sequential hash tables. We perform extensive experiments comparing the performance of our implementations with six of the most widely used concurrent hash tables. Ours are considerably faster than the best algorithms with similar restrictions and an order of magnitude faster than the best more general tables. In some extreme cases, the difference even approaches four orders of magnitude. All our implementations discussed in this publication can be found on github [17].

关键词： Concurrency dynamic data structures experimental analysis hash table lock-freedom transactional memory

来源：评论

学校读者我要写书评

暂无评论

dynamic Path Queries in Linear Space

引用

ALGORITHMICA 2018年第12期80卷 3728-3765页

作者： He, Meng Munro, J. Ian Zhou, Gelin Dalhousie Univ Fac Comp Sci Halifax NS Canada Univ Waterloo David R Cheriton Sch Comp Sci Waterloo ON Canada

In the path reporting problem, we preprocess a tree on n nodes each of which is assigned a weight, such that given an arbitrary path and a weight range, we can report the nodes whose weights are within the range. We consider this problem in dynamic settings, and propose the first non-trivial linear-space solution that supports path reporting in O((lg n/lg lg n)(2) + occ lg n/lg lg n) time, where occ is the output size, and the insertion and deletion of a node of an arbitrary degree in O(lg(2+epsilon) n) amortized time, for any constant epsilon is an element of (0, 1). Obvious solutions based on directly dynamizing solutions to the static version of this problem all require Omega ((lg n/lg lg n)(2)) time for each node reported, and thus our query time is much faster. We also design data structures that support path counting and path reporting queries in O((lg n/lg lg n)(2)) time, and insertions and deletions in O((lg n/lg lg n)(2)) amortized time. This matches the best known results for dynamic two-dimensional range counting (He and Munro in Comput Geom 47(2): 268-281, 2014) and range selection (He et al., in: Proceedings of the 22nd international symposium on algorithms and computation, ISAAC, Yokohama, Japan, 2011), which can be viewed as special cases of path counting and path selection.

关键词： dynamic data structures Path queries Fractional cascading Directed topology trees

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：