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

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

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

dynamic data structures for fat objects and their applications

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2000年第4期15卷 215-227页

作者： Efrat, A Katz, MJ Nielsen, F Sharir, M Ben Gurion Univ Negev Dept Math & Comp Sci IL-84105 Beer Sheva Israel Tel Aviv Univ Sch Math Sci IL-69978 Tel Aviv Israel SONY Comp Sci Labs Inc Tokyo Japan NYU Courant Inst Math Sci New York NY USA

We present several efficient dynamic data structures for point-enclosure queries, involving convex fat objects in R-2 or R-3. Our planar structures are actually fitted for a more general class of objects - (beta, delta)-covered objects which are not necessarily convex, see definition below. These structures are more efficient than alternative known structures, because they exploit the fatness of the objects. We then apply these structures to obtain efficient solutions to two problems: (i) finding a perfect containment matching between a set of points and a set of convex fat objects, and (ii) finding a piercing set for a collection of convex fat objects, whose size is optimal up to some constant factor. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： fat objects dynamic data structure point enclosure containment matching piercing set

来源：评论

学校读者我要写书评

暂无评论

Skip quadtrees: dynamic data structures for multidimensional point sets

引用

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS 2008年第1-2期18卷 131-160页

作者： Eppstein, David Goodrich, Michael T. Sun, Jonathan Z. Univ Calif Irvine Donald Bren Sch Informat & Comp Sci Dept Comp Sci Irvine CA 92697 USA Univ So Mississippi Sch Comp Hattiesburg MS 39406 USA

We present a new multi-dimensional data structure, which we call the skip quadtree ( for point data in R-2) or the skip octree (for point data in R., with constant d > 2). Our data structure combines the best features of two well-known data structures, in that it has the well-defined "box"-shaped regions of region quadtrees and the logarithmicheight search and update hierarchical structure of skip lists. Indeed, the bottom level of our structure is exactly a region quadtree (or octree for higher dimensional data). We describe efficient algorithms for inserting and deleting points in a skip quadtree, as well as fast methods for performing point location, approximate range, and approximate nearest neighbor queries.

关键词： skip quadtree quadtree octree dynamic data structure point location range nearest neighbor approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Implementing Adaptive and dynamic data structures using CUDA Parallelism

Implementing Adaptive and Dynamic Data Structures using CUDA...

引用

International Conference on Advances in Engineering and Technology Research (ICAETR),

作者： Sangale, Abhijit L. Devani, Urvesh Nikam, Valmik B. Meshram, B. B. Veermata Jijabai Technol Inst Dept Comp Engn & Informat Technol Mumbai Maharashtra India

ISBN: (纸本)9781479963935

dynamic data structures are the key to many highly efficient and optimized implementations. On CPU, dynamic data structures can grow and shrink at run time by allocating and deallocating memory from a place called heap and link those blocks using pointers. Adaptive data structure means changing the internal properties and structures of the data structure at run time according to requirement for various purposes, known as adaptive use of data structure. When we consider parallelism on GPUs using CUDA, there are many limitations on what can be used as data structure on GPU's global and shared memory. Generally simple arrays are handled on the GPU memory. Programmers need to find ways to present different data structures in terms of multiple arrays. In this paper, we have studied and implemented dynamic data structures & adaptive methodologies on GPU. We majorly explore the concept dynamic parallelism available in latest CUDA devices by implementing and analyzing quick sort and kernel call wise break down on latest NVIDIA's Kepler Architecture GPU. We also experimented with basic array operations on GPU by implementing minimum number finding. Implementation using CUDA results in very high performance gain.

关键词： Adaptive data structure dynamic data structure dynamic Parallelism CUDA GPU OpenCL

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Space efficient data structures for dynamic orthogonal range counting

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2014年第2期47卷 268-281页

作者： He, Meng Munro, J. Ian Dalhousie Univ Fac Comp Sci Halifax NS B3H 3J5 Canada Univ Waterloo Cheriton Sch Comp Sci Waterloo ON N2L 3G1 Canada

We present a linear-space data structure that maintains a dynamic set of n points with coordinates of real numbers in the plane to support orthogonal range counting in O((lg n/lg lg n)(2))worst-case time, and insertions and deletions in O((lg n/lg lg n)(2)) amortized time. This provides faster support for updates than previous results with the same bounds on space cost and query time. We also consider the same problem for points on a U x U grid, and design the first succinct data structure for a dynamic integer sequence, S, to support range counting queries defined as follows: Given a range, [i(1)..i(2)] of indices and a range, [v(1)..v(2)], of values, count the number of entries of that store integers from [v(1)..v(2)]. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Succinct data structure Geometric data structure dynamic data structure Orthogonal range counting dynamic orthogonal range counting

来源：评论

学校读者我要写书评

暂无评论

On-line maintenance of triconnected components with SPQR-trees

引用

ALGORITHMICA 1996年第4期15卷 302-318页

作者： DiBattista, G Tamassia, R UNIV ROMA LA SAPIENZA DIPARTIMENTO INFORMAT & SISTEMIST I-00185 ROME ITALY BROWN UNIV DEPT COMP SCI PROVIDENCE RI 02912 USA

We consider the problem of maintaining on-line the triconnected components of a graph G. Let n be the current number of vertices of G. We present an O (rt)-space data structure that supports insertions of vertices and edges, and queries of the type ''Are there three vertex-disjoint paths between vertices v(1) and v(2)?'' A sequence of k operations takes time O(k . alpha(k,n)) if G is biconnected (alpha(k,n) denotes the well-known Ackermann's function inverse), and time O(n log n + k) if G is not biconnected. Note that the bounds do not depend on the number of edges of G. We use the SPQR-tree, a versatile data structure that represents the decomposition of a biconnected graph with respect to its triconnected components, and the BC-tree, which represents the decomposition of a connected graph with respect to its biconnected components.

关键词： vertex connectivity dynamic algorithm dynamic data structure graph decomposition triconnected components network reliability

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Translating a regular grid over a point set

引用

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS 2003年第1-2期25卷 21-34页

作者： Bose, P van Kreveld, M Maheshwari, A Morin, P Morrison, J Carleton Univ Sch Comp Sci Ottawa ON K1S 5B6 Canada Univ Utrecht Dept Comp Sci NL-3508 TB Utrecht Netherlands

We consider the problem of translating a (finite or infinite) square grid G over a set S of n points in the plane in order to maximize some objective function. We say that a grid cell is k-occupied if it contains k or more points of S. The main set of problems we study have to do with translating an infinite grid so that the number of k-occupied cells is maximized or minimized. For these problems we obtain running times of the form O(kn polylog (n)). We also consider the problem of translating a finite size grid, with m cells, in order to maximize the number of k-occupied cells. Here we obtain a running time of the form O(knm polylog (nm)). In solving these problems, we design a data structure T that maintains in O(log n) time per operation, a function f : R --> R under the following query and update operations where [a, b) is a continuous interval in R: 1. INSERT(T, a, b, delta): Increase the value of f (x) by delta for all x is an element of [a, b). 2. DELETE(T, a, b, delta): Decrease the value of f (x) by delta for all x is an element of [a, b). 3. MAX-COVER(): Return max{f (x): x is an element of R}. 4. MAX-COVER-WITNESS(): Return a value x* such that f (x*) = max{f (x): x is an element of R}. 5. MAX-IN(a, b): Returns max{f (x): x is an element of [a, b)}. 6. MAX-WITNESS-IN(a, b): Returns a value x* such that f (x*) = max{f (x): x is an element of [a, b)}. as well as the min counter-parts of these queries. (C) 2002 Published by Elsevier Science B.V.

关键词： dynamic data structure binary tree intervals lazy update facility location maintenance of functions

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：