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

25th Annual Symposium on Computational Geometry

作者： Ishaque, Mashhood Speckmann, Bettina Toth, Csaba D. Tufts Univ Dept Comp Sci Medford MA 02155 USA

ISBN: (纸本)9781605585017

We present a data structure for ray shooting-and-insertion in the free space among disjoint polygonal obstacles with a total of n vertices in the plane, where each ray starts at the boundary of some obstacle. The portion of each query ray between the starting point and the first obstacle hit is inserted permanently as a new obstacle. Our data, structure uses O(n log n) space and preprocessing time, and it supports m successive ray shooting-and-insertion queries in O(n log(2) n + m log m) total time. We present two applications for our data structure: (1) Our data structure supports efficient implementation of auto-partitions in the plane i.e. binary space partitions where each partition is done along the supporting line of an input segment. If n input line segments are fragmented into m, pieces by an auto-partition, then it can now be implemented in O(n log(2) n + m log m) time. This improves the expected runtime of Patersen and Yao's classical randomized auto-partition algorithm for n disjoint line segments to O(n log(2) n). (2) If we are given disjoint polygonal obstacles with a total of n vertices in the plane, a permutation of the reflex vertices, and a half-line at each reflex vertex that partitions the reflex angle into two convex angles, then the folklore convex partitioning algorithm draws a ray emanating from each reflex vertex in the prescribed order in the given direction until it hits another obstacle, a previous ray, or infinity. The previously best implementation (with a semi-dynamic ay shooting data structure) requires O(n(3/2-epsilon/2)) time using O(n(1+epsilon)) space. Our data structure improves the runtime to O(n log(2) n).

关键词： Ray Shooting Segment Insertion dynamic data structure Convex Partition Binary Space Partition

来源：评论

学校读者我要写书评

暂无评论

PAMS: Pattern Aware Memory System for Embedded Systems

PAMS: Pattern Aware Memory System for Embedded Systems

引用

2014 International Conference on Reconfigurable Computing and FAGAs

作者： Hussain, Tassadaq Sonmez, Nehir Palomar, Oscar Unsal, Osman Cristal, Adrian Ayguade, Eduard Valero, Mateo Gursal, S. A. Barcelona Supercomp Ctr Comp Sci Barcelona Spain Unal Ctr Educ Res & Dev Barcelona Spain Univ Politecn Cataluna Dept Arquitectura Comp Barcelona Spain CSIC Artificial Intelligence Res Inst IIIA Barcelona Spain

ISBN: (纸本)9781479959440

In this paper, we propose a hardware mechanism for embedded multi-core memory system called Pattern Aware Memory System (PAMS). The PAMS supports static and dynamic data structures using descriptors and specialized memory and reduces area, cost, energy consumption and hit latency. When compared with a Baseline Memory System, the PAMS consumes between 3 and 9 times and 1.13 and 2.66 times less program memory for static and dynamic data structures respectively. The benchmarking applications (having static and dynamic data structures) results show that PAMS consumes 20% less hardware resources, 32% less on chip power and achieves a maximum speedup of 52x and 2.9x for static and dynamic data structures respectively. The results show that the PAMS multi-core system transfers data structures up to 4.65x faster than the MicroBlaze baseline system.

关键词： data structures embedded systems multiprocessing systems storage management MicroBlaze baseline system PAMS multicore system baseline memory system dynamic data structure embedded multicore memory system embedded system pattern aware memory system static data structure data structures dynamic scheduling Hardware Memory management Random access memory Registers Resource management data structures Embedded systems Store management Cache Memory System Multiprocessing systems random access machine Registers dynamic scheduling Computer hardware management of resources

来源：评论

学校读者我要写书评

暂无评论

A dynamic I/O-Efficient structure for One-Dimensional Top-k Range Reporting 14

A Dynamic I/O-Efficient Structure for One-Dimensional Top-k ...

引用

33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of database Systems

作者： Tao, Yufei CUHK Hong Kong Hong Kong Peoples R China

We present a structure in external memory for top-k range reporting, which uses linear space, answers a query in O(lg(B) n + k/B) I/Os, arid supports an update in O(lg(B) n) amortized I/Os, where n is the input size, ... 详细信息

ISBN: (纸本)9781450323758

关键词： Top-k range reporting dynamic data structure

来源：评论

学校读者我要写书评

暂无评论

Covering Users by a Connected Swarm Efficiently 1

引用

16th International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS)

作者： Danilchenko, Kiril Segal, Michael Nutov, Zeev Ben Gurion Univ Negev Sch Elect & Comp Engn Beer Sheva Israel Open Univ Israel Raanana Israel

ISBN: (数字)9783030624019

ISBN: (纸本)9783030624002;9783030624019

In this paper we study covering problems that arise in wireless networks with Unmanned Aerial Vehicles (UAVs) swarms. In the general setting we want to place a set of UAVs that should cover a given set of planar users under some constraints and we want to maintain the solution efficiently in a static and dynamic fashion. Specifically, for a set S of n non-negative weighted points in the plane, we consider a set P of m disks (or squares) of radius RCOV where the goal is to place (and maintain under dynamic updates) their location such that the sum of the weights of the points in S covered by disks from P is maximized. In the connected version, we also require that the graph imposed on P should be connected. Moreover, for the static connected version we improve the results from [1] and we obtain a constant factor approximation algorithm. In order to solve our problem under various requirements, we use a variety of techniques including dynamic grid, a reduction to Budgeted Subset Steiner Connected Dominating Set problem, tree partition, and others. We present several simple data structures that maintain an O(1)-approximate solution efficiently, under insertions and deletions of points to/from S where each update operation can be performed in logarithmic time.

关键词： Budgeted covering Approximation algorithm dynamic data structure Tree partition

来源：评论

学校读者我要写书评

暂无评论

Maintaining Densest Subsets Efficiently in Evolving Hypergraphs 17

Maintaining Densest Subsets Efficiently in Evolving Hypergra...

引用

ACM Conference on Information and Knowledge Management (CIKM)

作者： Hu, Shuguang Wu, Xiaowei Chan, T-H. Hubert Univ Hong Kong Pokfulam Rd Hong Kong Hong Kong Peoples R China

ISBN: (纸本)9781450349185

In this paper we study the densest subgraph problem, which plays a key role in many graph mining applications. The goal of the problem is to find a subset of nodes that induces a graph with maximum average degree. The problem has been extensively studied in the past few decades under a variety of different settings. Several exact and approximation algorithms were proposed. However, as normal graph can only model objects with pairwise relationships, the densest subgraph problem fails in identifying communities under relationships that involve more than 2 objects, e.g., in a network connecting authors by publications. We consider in this work the densest subgraph problem in hyper graphs, which generalizes the problem to a wider class of networks in which edges might have different cardinalities and contain more than 2 nodes. We present two exact algorithms and a near-linear time r-approximation algorithm for the problem, where r is the maximum cardinality of an edge in the hypergraph. We also consider the dynamic version of the problem, in which an adversary can insert or delete an edge from the hypergraph in each round and the goal is to maintain efficiently an approximation of the densest subgraph. We present two dynamic approximation algorithms in this paper with amortized poly(E= log n) update time, for any c > 0. For the case when there are only insertions, the approximation ratio we maintain is r(1 + c), while for the fully dynamic case, the ratio is r2 (1+ c). Extensive experiments are performed on large real datasets to validate the effectiveness and efficiency of our algorithms.

关键词： Densest Subgraph Graph Mining dynamic data structure

来源：评论

学校读者我要写书评

暂无评论

Fully dynamic Approximation of LIS in Polylogarithmic Time 2021

Fully Dynamic Approximation of LIS in Polylogarithmic Time

引用

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

作者： Gawrychowski, Pawel Janczewski, Wojciech Univ Wroclaw Wroclaw Poland

ISBN: (纸本)9781450380539

We revisit the problem of maintaining the longest increasing sub-sequence (LIS) of an array under (i) inserting an element, and (ii) deleting an element of an array. In a recent breakthrough, Mitzen-macher and Seddighin [STOC 2020] designed an algorithm that maintains an O((1/is an element of)(O(1/is an element of))-approximation of LIS under both operations with worst-case update time (O) over tilde (n(is an element of)), for any constant is an element of > 0 ((O) over tilde hides factors polynomial in log n, where n is the length of the input). We exponentially improve on their result by designing an algorithm that maintains an (1+is an element of)-approximation of LIS under both operations with worst-case update time (O) over tilde(is an element of(-5)). Instead of working with the grid packing technique introduced by Mitzenmacher and Seddighin, we take a different approach building on a new tool that might be of independent interest: LIS sparsification. A particularly interesting consequence of our result is an improved solution for the so-called Erdos-Szekeres partitioning, in which we seek a partition of a given permutation of {1, 2, ..., n} into O(root n) monotone subsequences. This problem has been repeatedly stated as one of the natural examples in which we see a large gap between the decision-tree complexity and algorithmic complexity. The result of Mitzenmacher and Seddighin implies an O(n(1+is an element of)) time solution for this problem, for any is an element of > 0. Our algorithm (in fact, its simpler decremental version) further improves this to (O) over tilde (n).

关键词： longest increasing subsequence dynamic data structure sparsification

来源：评论

学校读者我要写书评

暂无评论

Near-Optimal (1+ε)-Approximate Fully-dynamic All-Pairs Shortest Paths in Planar Graphs 65

Near-Optimal (1+ε)-Approximate Fully-Dynamic All-Pairs Shor...

引用

65th Symposium on Foundations of Computer Science

作者： Filtser, Arnold Patel, Neel Goranci, Gramoz Gutenberg, Maximilian Probst Bar Ilan Univ Comp Sci Dept Ramat Gan Israel Univ Southern Calif Dept Comp Sci Los Angeles CA 90007 USA Univ Vienna Fac Comp Sci Vienna Austria Swiss Fed Inst Technol Dept Comp Sci Zurich Switzerland

ISBN: (纸本)9798331516758;9798331516741

We study the fully-dynamic all-pair shortest paths (APSP) problem on planar graphs: given an n-vertex planar graph G = ( V, E) undergoing edge insertions and deletions, the goal is to efficiently process these updates and support distance and shortest path queries. We give a (1+.)-approximate dynamic algorithm that supports edge updates and distance queries in n(o(1)) time, for any 1/poly( log n) < epsilon < 1. Our result is a significant improvement over the best previously known bound of (V) over tilde (root n) on update and query time due to [Abraham, Chechik, and Gavoille, STOC '12], and bypasses a Omega(root n) conditional lowerbound on update and query time for exact fully dynamic planar APSP [Abboud and Dahlgaard, FOCS '16]. The main technical contribution behind our result is to dynamize the planar emulator construction due to [Chang, Krauthgamer, Tan, STOC '22].

关键词： Planar Graph Distance Oracles dynamic data structure Distance Emulator

来源：评论

学校读者我要写书评

暂无评论

Optimizing to Memory Application in Embedded Multimedia Device

Optimizing to Memory Application in Embedded Multimedia Devi...

引用

International Conference on Advanced Design and Manufacturing Engineering (ADME 2011)

作者： Wang, Xiaosheng Yu, Qian Shandong Womens Univ Informat & Technol Sch Jinan Peoples R China

ISBN: (纸本)9783037852132

The modern embedded multimedia electronic devices rely on dynamically-allocated data structures to store and process their data, as a result, the demand of its memory capacity and dynamic are increasing unceasingly. In order to better solve the memory application optimization in embedded device, this paper represents multimedia application's dynamic data structures optimization flow and improved or modified NSGA-II multi-objective evolutionary algorithm (MNSGA-II), and uses three objective functions: embedded device's memory accesses, memory use and energy consumption. The MNSGA-II algorithm adopts repeat crowded distance sorting tactics to improve NSGA-II based on keeping the advantage of the original NSGA-II for multi-objective optimization problem. The experiment results show that MNSGA-II has better performance of the convergence and the diversity of solutions than original NSGA-II, and the optimal dynamic data structure implementation is successful by performing our method for one real embedded multimedia device's memory application.

关键词： Embedded multimedia device Memory Application dynamic data structure Multi-objective optimization improved NSGA-II algorithm

来源：评论

学校读者我要写书评

暂无评论

Test Generation for Programs with Binary Tree structure as Input

引用

INTERNATIONAL JOURNAL OF SOFTWARE ENGINEERING AND KNOWLEDGE ENGINEERING 2015年第7期25卷 1129-1151页

作者： Zhao, Ruilian Li, Zheng Wang, Qian Beijing Univ Chem Technol Dept Comp Sci Beijing 100029 Peoples R China

Test data generation is a process of creating program inputs that satisfy specific testing criteria. Many works have been focused on test generation with respect to numeric and string data. dynamic data structures, such as trees and linked lists, have been widely used in modern programming, but on which there are few studies presented. In general, generating a dynamic data structure is associated with a proper shape and valid values generation. It would be difficult to generate such dynamic data structures, as both shapes and values are necessary to be valid simultaneously. This paper focuses on binary tree structures and proposes a novel test generation approach that combines search based testing with constraint solving techniques. The approach creates the shapes of binary tree structures by using GA, and generates the values in their data fields by using constraint solving techniques. The experimental results show that the presented approach is promising and effective. Moreover, the studies investigate factors affecting the performance of the approach, and arrive at a conclusion that the test generation cost is cubic growing as the number of pointer constraints increases.

关键词： Search-based software testing test data generation dynamic data structure binary tree constraint solving

来源：评论

学校读者我要写书评

暂无评论

Memento Filter: A Fast, dynamic, and Robust Range Filter

引用

Proceedings of the ACM on Management of data 2024年第6期2卷 1-27页

作者： Navid Eslami Niv Dayan University of Toronto Toronto Ontario CA

Range filters are probabilistic data structures that answer approximate range emptiness queries. They aid in avoiding processing empty range queries and have use cases in many application domains such as key-value stores and social web analytics. However, current range filters do not support dynamically changing and growing datasets. Moreover, several of these designs also exhibit impractically high false positive rates under correlated workloads, which are common in practice. These impediments restrict the applicability of range filters across a wide range of use *** introduce Memento filter, the first range filter to simultaneously offer dynamicity, fast operations, and a robust false positive rate for any workload. Memento filter partitions the key universe and clusters its keys according to this partitioning. For each cluster, it stores a fingerprint and a list of key suffixes contiguously. The encoding of these lists makes them amenable to existing dynamic filter structures. Due to the one-to-one mapping from keys to suffixes, Memento filter supports inserts and deletes and can even expand to accommodate a growing *** implement Memento filter on top of a Rank-and-Select Quotient filter and InfiniFilter and demonstrate that it achieves a competitive false positive rate and performance with the state of the art while also providing dynamicity. Due to its dynamicity, Memento filter is the first range filter applicable to B-Trees. We showcase this by integrating Memento filter into WiredTiger, a B-Tree-based key-value store, significantly boosting its performance for mixed workloads.

关键词： data growth dynamic data structure range filter scalability

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：