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

Efficient Partial Order Based Transaction Processing for Permissioned Blockchains

学校读者我要写书评

暂无评论

Efficient Partial Order Based Transaction Processing for Per...

International Conference on Data Engineering

作者： Shuai Zhao Zhiwei Zhang Junkai Wang Ye Yuan Meihui Zhang Guoren Wang Jiang Xiao Beijing Institute of Technology Beijing China Huazhong University of Science and Technology Wuhan China

ISBN: (数字)9798350317152

ISBN: (纸本)9798350317169

With the development of permissioned blockchains, transaction processing plays an increasingly crucial role in improving performance. The execution and consensus phases in existing transaction processing methods are based on total order. The consensus phase constructs a total order representing the execution order and submission order of different transactions. Then, in the execution phase, transactions are executed or validated sequentially based on this total order. However, while the total order guarantees consistency across nodes, it also restricts the execution order of any two transactions, even if there is no conflict between them. Additionally, existing methods process transactions based on block snapshots before the consensus phase, but these snapshots are only updated after reaching consensus. The stale data between these phases results in high transaction abort rates due to delays in updated visibility. Therefore, we propose a novel blockchain called Partial Order-Based Ledger (POBL). POBL constructs a partial order of transaction executions in the execution phase and then, in the consensus phase, builds a consistent submission order based on this execution partial order. Notably, POBL allows the visibility of transaction processing results in the execution phase even before committing its block. To ensure the correct execution, the consensus and execution phases need to consider the consistency of data and the dependencies between transactions. Therefore, we use a graph, PGraph, to capture the concurrent partial order in the execution phase. In the consensus phase, we propose a consensus algorithm to conduct the maximal common subgraph, CPGraph, based on the PGraphs of different nodes. We propose to validate blocks and transactions in parallel based on CPGraph, without being restricted by the order between blocks. We perform extensive experiments compared to state-of-the-art architectural systems, and our method significantly outperforms existing work.

关键词： Schedules consensus algorithm Throughput Data engineering Blockchains Delays Detection algorithms

VARIABLE PROJECTION algorithmS: THEORETICAL INSIGHTS AND A NOVEL APPROACH FOR PROBLEMS WITH LARGE RESIDUAL

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Chen, Guangyong Xue, Peng Gan, Min Guo, Wenzhong Chen, Jing Chen, C.L. Philip College of Computer and Data Science Fuzhou University China School of Science Jiangnan University China School of Computer Science and Engineering South China University of Technology China

This paper delves into an in-depth exploration of the Variable Projection (VP) algorithm, a powerful tool for solving separable nonlinear optimization problems across multiple domains, including system identification, image processing, and machine learning. We first establish a theoretical framework to examine the effect of the approximate treatment of the coupling relationship among parameters on the local convergence of the VP algorithm and theoretically prove that the Kaufman’s VP algorithm can achieve a similar convergence rate as the Golub & Pereyra’s form. These studies fill the gap in the existing convergence theory analysis, and provide a solid foundation for understanding the mechanism of VP algorithm and broadening its application horizons. Furthermore, inspired by these theoretical insights, we design a refined VP algorithm, termed VPLR, to address separable nonlinear optimization problems with large residual. This algorithm enhances convergence performance by addressing the coupling relationship between parameters in separable models and continually refining the approximated Hessian matrix to counteract the influence of large residual. The effectiveness of this refined algorithm is corroborated through numerical experiments. Copyright © 2024, The Authors. All rights reserved.

关键词： consensus algorithm

Real Time Continuous Image Stitching algorithm Based on SIFT

学校读者我要写书评

暂无评论

Real Time Continuous Image Stitching Algorithm Based on SIFT

Information and Communication Engineering (JCICE), International Joint Conference on

作者： Ruijun Yang Chu Zhang Yan Cheng School of Computer Science & Information Engineering Shanghai Institute of Technology Shanghai China School of Criminal Justice East China University of Political Science and Law Shanghai China

ISBN: (数字)9798350388725

ISBN: (纸本)9798350388732

Image stitching technology has application scenarios in many fields. At present, the existing algorithms usually use the method of acquisition first and then synthesis, which is still insufficient in real-time performance; in addition, under the premise of real-time acquisition, it is also insufficient to realize continuous image synthesis. To solve this problem, this algorithm uses the RGB module of the Intel Realsense D435 camera for image acquisition, first creates an original image for storing the final result, collects an image at an interval of 100ms each time, and performs 8*8 hashing of the two images before and after Compare the similarity of the value, take the image with a similarity less than 5/8 and keep it, then use the SIFT (Scale-invariant feature transform) scale-invariant feature transform feature detection algorithm to extract the image feature points from the collected image, and use the RANSAC to extract the feature points The (Random Sample consensus) algorithm screens effective points and calculates the homography transformation matrix at the same time. Finally, every two images collected are synthesized into one and covered in the corresponding position of the result image. Through experiments in this paper, the average time for single acquisition and synthesis is 70ms, achieving the real-time goal. The similarity between the experimental group and the control group can reach 70%, and the resolution is increased by 1.65 times, achieving the goal of continuous splicing.

关键词： Image resolution Image synthesis Splicing Feature detection Transforms consensus algorithm Feature extraction Cameras Real-time systems Image stitching

Finite Sample Complexity Analysis of Binary Segmentation

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Hocking, Toby Dylan

Binary segmentation is the classic greedy algorithm which recursively splits a sequential data set by optimizing some loss or likelihood function. Binary segmentation is widely used for changepoint detection in data sets measured over space or time, and as a sub-routine for decision tree learning. In theory it should be extremely fast for N data and K splits, O(NK) in the worst case, and O(N log K) in the best case. In this paper we describe new methods for analyzing the time and space complexity of binary segmentation for a given finite N, K, and minimum segment length parameter. First, we describe algorithms that can be used to compute the best and worst case number of splits the algorithm must consider. Second, we describe synthetic data that achieve the best and worst case and which can be used to test for correct implementation of the algorithm. Finally, we provide an empirical analysis of real data which suggests that binary segmentation is often close to optimal speed in practice. © 2024, CC BY.

关键词： consensus algorithm

Faster Combinatorial k-Clique algorithms

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Abboud, Amir Fischer, Nick Shechter, Yarin Weizmann Institute of Science Rehovot Israel

Detecting if a graph contains a k-Clique is one of the most fundamental problems in computer science. The asymptotically fastest algorithm runs in time O(nωk/3), where ω is the exponent of Boolean matrix multiplication. To date, this is the only technique capable of beating the trivial O(nk) bound by a polynomial factor. Due to this technique’s various limitations, much effort has gone into designing "combinatorial" algorithms that improve over exhaustive search via other techniques. The first contribution of this work is a faster combinatorial algorithm for k-Clique, improving Vassilevska’s bound of O(nk/logk−1 n) by two log factors. Technically, our main result is a new reduction from k-Clique to Triangle detection that exploits the same divide-and-conquer at the core of recent combinatorial algorithms by Chan (SODA’15) and Yu (ICALP’15). Our second contribution is exploiting combinatorial techniques to improve the state-of-the-art (even of non-combinatorial algorithms) for generalizations of the k-Clique problem. Specifically we introduce the first non-trivial clique listing algorithms: A general algorithm for detecting cliques in hypergraphs that also improves the state of the art for detection, and an additional algorithm for the specific case of triangle listing with improved bounds. © 2024, CC BY.

关键词： consensus algorithm

A Simple 4-Approximation algorithm for Maximum Agreement Forests on Multiple Unrooted Binary Trees

学校读者我要写书评

暂无评论

arXiv 2024年

作者： Dempsey, Jordan van Iersel, Leo Jones, Mark Zeh, Norbert Faculty of Computer Science Dalhousie University 6050 University Avenue HalifaxNSB3H 1W5 Canada Delft Institute of Applied Mathematics Delft University of Technology Mekelweg 4 Delft2628 CD Netherlands

We present a simple 4-approximation algorithm for computing a maximum agreement forest of multiple unrooted binary trees. This algorithm applies LP rounding to an extension of a recent ILP formulation of the maximum agreement forest problem on two trees by Van Wersch al. [13]. We achieve the same approximation ratio as the algorithm of Chen et al. [3] but our algorithm is extremely simple. We also prove that no algorithm based on the ILP formulation by Van Wersch et al. can achieve an approximation ratio of 4 − Ε, for any Ε > 0, even on two trees. To this end, we prove that the integrality gap of the ILP approaches 4 as the size of the two input trees grows. © 2024, CC BY.

关键词： consensus algorithm

Efficient Sampling of Temporal Networks with Preserved Causality Structure

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Stamm, Felix I. Naima, Mehdi Schaub, Michael T. RWTH Aachen University Germany Sorbonne Université CNRS LIP6 ParisF-75005 France

In this paper, we extend the classical Color Refinement algorithm for static networks to temporal (undirected and directed) networks. This enables us to design an algorithm to sample synthetic networks that preserves the d-hop neighborhood structure of a given temporal network. The higher d is chosen, the better the temporal neighborhood structure of the original network is preserved. Specifically, we provide efficient algorithms that preserve time-respecting ("causal") paths in the networks up to length d, and scale to real-world network sizes. We validate our approach theoretically (for Degree and Katz centrality) and experimentally (for edge persistence, causal triangles, and burstiness). An experimental comparison shows that our method retains these key temporal characteristics more effectively than existing randomization methods. © 2025, CC BY.

关键词： consensus algorithm

An Optimally Convergent Split Parallel algorithm for the Multiple-Network Poroelasticity Model

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Zhao, Jijing Chen, Huangxin Cai, Mingchao Sun, Shuyu School of Mathematical Sciences Tongji University Shanghai China School of Mathematical Sciences Fujian Provincial Key Laboratory on Mathematical Modeling and High Performance Scientific Computing Xiamen University Fujian Xiamen China Department of Mathematics Morgan State University BaltimoreMD21251 United States Shandong Qingdao China

This paper presents a novel split parallel algorithm for solving quasi-static multiple-network poroelasticity (MPET) equations. By introducing a total pressure variable, the MPET system can be reformulated into a coupled Stokes-parabolic system. To efficiently solve this system, we propose a split parallel approach. In the first time step, a monolithic solver is used to solve all variables simultaneously. For subsequent time steps, the system is split into a Stokes subproblem and a parabolic subproblem. These subproblems are then solved in parallel using a stabilization technique. This split parallel approach differs from sequential or iterative decoupling, significantly reducing computational time. The algorithm is proven to be unconditionally stable, optimally convergent, and robust across various parameter settings. These theoretical results are confirmed by numerical experiments. We also apply this parallel algorithm to simulate fluid-tissue interactions within the physiological environment of the human brain. Copyright © 2025, The Authors. All rights reserved.

关键词： consensus algorithm

MULTIDIMENSIONAL MOMENT PROBLEM AND STIELTJES TRANSFORM

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Kovalyov, Ivan Universität Osnabrück Albrechtstr. 28a Osnabrück49076 Germany

The truncated multidimensional moment problem is studied in terms of the Stieltjes transform as the interpolation problem. A step-by-step algorithm is constructed for the multidimensional moment problem and the set of... 详细信息

关键词： consensus algorithm