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

dynamic data structures for Timed Automata Acceptance

ALGORITHMICA 2022年第11期84卷 3223-3245页

作者： Grez, Alejandro Mazowiecki, Filip Pilipczuk, Michal Puppis, Gabriele Riveros, Cristian Pontificia Univ Catolica Chile Santiago Chile Millennium Inst Foundat Res Data Santiago Chile Univ Warsaw Warsaw Poland Univ Udine Udine Italy

We study a variant of the classical membership problem in automata theory, which consists of deciding whether a given input word is accepted by a given automaton. We do so through the lenses of parameterized dynamic data structures: we assume that the automaton is fixed and its size is the parameter, while the input word is revealed as in a stream, one symbol at a time following the natural order on positions. The goal is to design a dynamic data structure that can be efficiently updated upon revealing the next symbol, while maintaining the answer to the query on whether the word consisting of symbols revealed so far is accepted by the automaton. We provide complexity bounds for this dynamic acceptance problem for timed automata that process symbols interleaved with time spans. The main contribution is a dynamic data structure that maintains acceptance of a fixed one-clock timed automaton A with amortized update time 2(O(vertical bar A vertical bar)) per input symbol.

关键词： Timed automata data stream dynamic data structure

来源：评论

学校读者我要写书评

暂无评论

MetaFactory: A cloud-based framework to configure and generate dynamic data structures from the STEP-NC knowledge graph

引用

JOURNAL OF MANUFACTURING SYSTEMS 2025年 80卷 89-107页

作者： Xiao, Wenlei Qiu, Tianze Guo, Jiurong Zhao, Gang Beihang Univ Sch Mech Engn & Automat Beijing 100191 Peoples R China Beihang Univ Jiangxi Res Inst Nanchang 330200 Peoples R China Beihang Univ Jingdezhen Res Inst Jingdezhen 333000 Peoples R China AV Chengdu Aircraft Ind Grp Co Ltd Chengdu 610031 Peoples R China

In our previous studies, twin-oriented manufacturing has been identified as a crucial solution to address the manufacturing crisis. Within this context, the notion of "digital twin as a service" necessitates that various twin services share and communicate with each other in a standardized manner. STEP-NC offers a potentially unified model to facilitate data exchange, providing object-oriented and standardized data models fora comprehensive representation of manufacturing resources in the digital realm. However, the complexity of STEP-NC renders it too cumbersome for implementation in diverse cloud-based services or PC-based software. This complexity is a fundamental reason why STEP-NC has struggled to find application in commercial CNC systems despite years of research. To overcome this technical challenge, this paper introduces a novel concept termed "dynamic STEP-NC data structure", inspired by the dynamic language philosophy of dynamic programming language (such as Python). This approach allows different services and software packages to maintain their own data definitions while still aligning with the original STEP-NC definition. We have developed a framework called MetaFactory that supports the configuration of streamlined data structures and generates the corresponding program code required by various service developers. On this basis, we implemented automatic modeling for a STEP-NC object-oriented database. Using the data trimming and dimensionality reduction methods provided by MetaFactory, several prototype systems for different application scenarios have been developed.

关键词： Twin-oriented manufacturing STEP-NC dynamic data structure Object-oriented database Knowledge graph

来源：评论

学校读者我要写书评

暂无评论

Concolic Testing of Programs with Concurrent dynamic data structures

Concolic Testing of Programs with Concurrent Dynamic Data St...

引用

作者： Sun, Xiaofan University of California Riverside

学位级别：Ph.D., Doctor of Philosophy

Concolic execution combines concrete execution with symbolic execution to automatically generate test inputs that exercise different program paths and deliver high code coverage. However, when this technique is extended to multithreaded programs with concurrent dynamic data structures, the lack of support for exploring data shapes (the skeleton that consists of symbolic pointers in node-based linked data structures) and efficiently exploring thread interleavings makes it hard to expose concurrency bugs that manifest only when certain dynamic data structure shapes, program paths, and thread interleavings are exercised. This thesis presents techniques to effectively explore data shapes for concurrent dynamic data structures and optimize the exploration efficiency. The approach presented first generates a data shape for a chosen path. By capturing path constraints, we form a shape that satisfies path constraints and exercises the chosen path. In addition, by capturing pointer-pointee relationships, we find how to adjust the shape and find new shapes that also exercise the same path. Finally, using the shapes for individual paths, we find a consistent shape that causes multiple threads to simultaneously follow their chosen paths for exposing concurrency bugs. We generate shapes for each thread separately and provide an integration algorithm to merge the shapes into a consistent shape. This approach does not require the user to write code that constructs data structures to exercise desired paths by individual threads; rather, it automatically collects constraints to generate consistent shapes during the concolic execution. We also present a summarization-based technique to improve the efficiency of concolic testing further. Via unit testing of key functions that implement a concurrent data structure, function summaries are derived that capture data structure shapes that cause various function paths to be exercised. During the concolic testing of interprocedural paths, th

关键词： Concolic execution dynamic data structure Concurrency bugs Cloud9 Multithreaded programs

来源：评论

学校读者我要写书评

暂无评论

Listing the bonds of a graph in O(n)-delay

引用

DISCRETE APPLIED MATHEMATICS 2024年 348卷 105-121页

作者： Raffaele, Alice Rizzi, Romeo Uno, Takeaki Dept Mech Energy & Management Via Pietro Bucci-Cubo 46C I-87036 Arcavacata di Rende Italy Univ Verona Dept Comp Sci Str Le Grazie 15 I-37134 Verona Italy Natl Inst Informat 2-1-2 HitotsubashiChiyoda ku Tokyo 1018430 Japan

Given a connected graph G = (V, E), with n := |V| vertices and m := |E| edges, a cut can be represented as a bipartition {S, S} of the vertices or as the set of those edges in E having one endpoint in S and the other in S, denoted by 8G(S, S). A cut is minimal, or also called bond, if and only if the two induced subgraphs obtained by removing the edges in the cut are both connected. When the bond separates two given vertices s and t, we talk about s, t-bond. In this work, we consider the problems of listing all the bonds and listing all the s, t-bonds in a graph. These fundamental problems find application in many research areas, such as, beyond graph theory, network reliability, bioinformatics, and chemistry. The state-of-the-art algorithm exploits binary partition to output each s, t-bond in O(m) per bond, being thus classified as an O(m)-delay algorithm. Here we present two new algorithms to address these problems. The first one implements a slightly different branching strategy than the state of the art, though achieving the same complexity. Anyway, we can improve it by relying on dynamic data structures and amortized analysis, obtaining an algorithm that outputs a new bond in O similar to(n). By assuming only the two bond-shores are output for every bond, this is the first outputlinear algorithm listing bonds. In case we commit to explicitly providing the entire edge-set of every bond, the delay becomes O similar to(n) + |8G(S, S)|. (c) 2024 Elsevier B.V. All rights reserved.

关键词： Enumeration Graph theory Minimal cut Binary partition dynamic data structure Amortized analysis

来源：评论

学校读者我要写书评

暂无评论

DETERMINISTIC NEAR-OPTIMAL APPROXIMATION ALGORITHMS FOR dynamic SET COVER

引用

SIAM JOURNAL ON COMPUTING 2023年第5期52卷 1132-1192页

作者： Bhattacharya, Sayan Henzinger, Monika Nanongkai, Danupon Wu, Xiaowei Univ Warwick Coventry CV4 7AL England Inst Sci & Technol Austria ISTA A-1090 Vienna Austria Max Planck Inst Informat D-66123 Saarbrucken Germany Saarland Univ D-66123 Saarbrucken Germany Univ Macau Macau Peoples R China

In the dynamic minimum set cover problem, the challenge is to minimize the update time while guaranteeing a close-to-optimal min{O(log n), f\} approximation factor. (Throughout, n, m, f, and C are parameters denoting the maximum number of elements, the number of sets, the frequency, and the cost range.) In the high-frequency range, when f = \Omega (log n), this was achieved by a deterministic O(log n)-approximation algorithm with O(f log n) amortized update time by Gupta et al. [Online and dynamic algorithms for set cover, in Proceedings STOC 2017, ACM, pp. 537550]. In this paper we consider the low-frequency range, when f = O(log n), and obtain deterministic algorithms with a (1 + \epsilon )f-approximation ratio and the following guarantees on the update time. (1) O ((f /\epsilon ) \cdot log(Cn)) amortized update time: Prior to our work, the best approximation ratio guaranteed by deterministic algorithms was O(f2) of Bhattacharya, Henzinger, and Italiano [Design of dynamic algorithms via primal-dual method, in Proceedings ICALP 2015, Springer, pp. 206--218]. In contrast, the only result with O(f)-approximation was that of Abboud et al. [dynamic set cover: Improved algorithms and lower bounds, in Proceedings STOC 2019, ACM, pp. 114--125], who designed a randomized (1 + \epsilon )f-approximation algorithm with O((f2/\epsilon ) \cdot log n) amortized update time. (2) O \bigl(f2/\epsilon3 + (f/\epsilon2) \cdot log C\bigr) amortized update time: This result improves the above update time bound for most values off in the low-frequency range, i.e., f = o(log n). It is also the first result that is independent of m and n. It subsumes the constant amortized update time of Bhattacharya and Kulkarni [Deterministically maintaining a (2 + \epsilon )-approximate minimum vertex cover in O(1/\epsilon2) amortized update time, in Proceedings SODA 2019, SIAM, pp. 1872--1885] for unweighted dynamic vertex cover (i.e., when f = 2 and C = 1). (3) O((f/\epsilon3) \cdot log2(Cn)) worst-ca

关键词： set cover approximation algorithms dynamic data structure

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

dynamically Allocated Bloom Filter-Based PIT Architectures

引用

IEEE ACCESS 2022年 10卷 28165-28179页

作者： Jang, Saeyoung Byun, Hayoung Lim, Hyesook Ewha Womans Univ Dept Elect & Elect Engn Seoul 03760 South Korea Myongji Univ Dept Elect Engn Yongin 17058 South Korea

As a key component in implementing Named data Networking (NDN), Pending Interest Table (PIT) requires an efficient exact-matching algorithm for a scalable and fast PIT lookup. A Bloom filter (BF) is a memory-efficient data structure for performing exact matching operations. In this paper, three different BF-based PIT architectures are proposed: PIT using functional Bloom filters (FBF-PIT), PIT using counting Bloom filters with return values (rCBF-PIT), and a refined rCBF-PIT with signatures (R-rCBF-PIT). The proposed BF-based PITs incrementally allocate a new BF for storing multiple incoming faces of Interest packets with the same content name. For a data packet lookup, the proposed PIT architectures simultaneously access every BF structure to find matching faces and delete the faces (i.e., matching Interest packet information). The functional Bloom filter (FBF) used in an FBF-PIT is a key-value data structure that stores values only without keys. However, because the number of non-reusable conflict cells in the FBF increases as the number of stored packets increases in the FBF-PIT, the indeterminable rate increases. To decrease the indeterminable rate, we propose the rCBF-PIT, which uses counting Bloom filters with return values (rCBFs), allowing reusable conflict cells. False positives for Interest packets lead to incorrect deletions that can cause false negatives for incoming data packets. Because most of the false positives occur in the first BF structure, we finally propose the R-rCBF-PIT, in which the first rCBF is replaced with an rCBF with a signature field. The proposed PITs also provide an aging mechanism using a valid bit and a hit bit for entry expiration. Simulation results show that rCBF-PIT and R-rCBF-PIT both reduce the indeterminable rate by more than 81% compared with FBF-PIT. The results also show that R-rCBF-PIT resolves false negatives caused by incorrect deletions by including the signature fields in the first rCBF.

关键词： Faces Information filters Matched filters Programming Indexes Hash functions Filtering algorithms Bloom filter dynamic data structure named data networking pending Interest table

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：