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

A scalable algorithm for the decomposition of minimally rigid graph

MEASUREMENT & CONTROL 2020年第5-6期53卷 807-813页

作者： Zhu, Yadong Wang, Qin Li, Shengquan Yang, Yuequan Yangzhou Univ Yangzhou Jiangsu Peoples R China Yangzhou Polytech Univ Yangzhou Jiangsu Peoples R China

The rigid graph needs to be decomposed to solve the multi-equilibrium problem of the multi-agent formation control based on navigation function method. In this paper, a theorem and a scalable algorithm based on the Henneberg sequence of graphs are proposed for the decomposition of minimally rigid graph. The theorem demonstrates that if graphG(V,E) is a minimally rigid graph, then it can be decomposed asG=G(t)?G(c), whereG(t)is a spanning tree ofGandG(c)contains the remaining edges and their vertices. Moreover, the scalable algorithm is given to constructG(t)= (V-t,E-t) andG(c)= (V-c,E-c), and assign the edges inE(c)ton-- 2 distinct vertices in a scalable way via communication. Furthermore, a lemma is given to show when the number of vertices is less than eight, any edge can be chosen as the initialized edge, and the scalable algorithm mentioned above is always feasible. Finally, the effectiveness of the scalable algorithm is verified by numerical simulation.

关键词： Minimally rigid graph rigid formation control global stability graph decomposition scalable algorithm

来源：评论

学校读者我要写书评

暂无评论

Battlefield Optimization algorithm☆

引用

EXPERT SYSTEMS WITH APPLICATIONS 2025年 266卷

作者： Setiawan, Dadang Suyanto, Suyanto Erfianto, Bayu Gozali, Alfian Akbar Telkom Univ Sch Comp Bandung Indonesia Telkom Univ Ctr Excellence Artificial Intelligence Learning & Bandung Indonesia

This paper proposes anew metaheuristic optimization algorithm named Battlefield Optimization algorithm (BfOA). As the name implies, it is inspired by the simulation of a battlefield, where two opposing squads battle each other. The squad with the stronger position defends its position and the weaker squad attacks using Supit Urang formation (an Indonesian traditional battle formation). Each squad is led by a commander. The commander leads three types of soldiers (cavaliers, special forces, and builders). Before the battle started, in the first phase each squad employs airplanes to scan the best position to begin the battle. The airplanes' movements are highly explorative. In the second phase, the defending squad's movement is highly exploitative, while the attacking squad is in the mid-explorative movement. The proposed algorithm is examined using twentythree benchmark functions and compared with one classic and five newer algorithms. To further examine the capability of the algorithm, CEC 2021 Single Objective Bound Constrained Numerical Optimization benchmark functions are used. Then the algorithm is tested in a real-world engineering optimization problem by solving the Three-Bar Truss problem.

关键词： Battlefield Optimization algorithm Battle-inspired algorithm Metaheuristic optimization Swarm intelligence scalable algorithm Supit Urang formation

来源：评论

学校读者我要写书评

暂无评论

scalable SYMMETRIC TUCKER TENSOR DECOMPOSITION

引用

SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS 2024年第4期45卷 1746-1781页

作者： Jin, Ruhui Kileel, Joe Kolda, Tamara g. Ward, Rachel Univ Texas Austin Dept Math Austin TX 78712 USA MathSci Ai Dublin CA 94568 USA

We study the best low-rank Tucker decomposition of symmetric tensors. The motivating application is decomposing higher-order multivariate moments. Moment tensors have special structure and are important to various data science problems. We advocate for a projected graas computation schemes. Most importantly, we develop scalable adaptations of the basic PGD and HOEVD methods to decompose sample moment tensors. With the help of implicit and streaming techniques, we evade the overhead cost of building and storing the moment tensor. Such reductions make computing the Tucker decomposition realizable for large data instances in high dimensions. Numerical experiments demonstrate the efficiency of the algorithms and the applicability of moment tensor decompositions to real-world datasets. Finally we study the convergence on the Grassmannian manifold and prove that the update sequence derived by the PGD solver achieves first- and second-order criticality.

关键词： symmetric tensor Tucker decomposition scalable algorithm

来源：评论

学校读者我要写书评

暂无评论

GPUTucker: Large-Scale GPU-Based Tucker Decomposition Using Tensor Partitioning

引用

EXPERT SYSTEMS WITH APPLICATIONS 2024年第PartA期237卷

作者： Lee, Jihye Han, Donghyoung Kwon, Oh-Kyoung Chon, Kang-Wook Kim, Min-Soo Daegu Gyeongbuk Inst Sci & Technol DGIST Dept Elect Engn & Comp Sci 333 Techno Jjungang Daero Daegu 42988 South Korea GraphAI 157 Daehak Ro Daejeon 34138 South Korea Korea Inst Sci & Technol Informat KISTI Natl Inst Supercomp & Networking 245 Daehak Ro Daejeon 34141 South Korea Korea Univ Technol & Educ Sch Comp Sci & Engn 1600 Chungjeol Ro Cheonan Si 31253 Chungcheongnam South Korea Korea Adv Inst Sci & Technol KAIST Sch Comp 291 Daehak Ro Daejeon 34141 South Korea

Tucker decomposition is used extensively for modeling multi-dimensional data represented as tensors. Owing to the increasing magnitude of nonzero values in real-world tensors, a growing demand has emerged for expeditious and scalable Tucker decomposition techniques. Several graphics processing unit (GPU)-accelerated techniques have been proposed for Tucker decomposition to decrease the decomposition speed. However, these approaches often encounter difficulties in handling extensive tensors owing to their huge memory demands, which exceed the available capacity of GPU memory. This study presents an expandable GPU-based technique for Tucker decomposition called GPUTucker. The proposed method meticulously partitions sizable tensors into smaller sub-tensors, which are referred to as tensor blocks, and effectively implements the GPU-based data pipeline by handling these tensor blocks asynchronously. Extensive experiments demonstrate that GPUTucker outperforms state-of-the-art Tucker decomposition methods in terms of the decomposition speed and scalability.

关键词： Tensor decomposition Big data Graphics processing unit (GPU) scalable algorithm Memory-efficient method

来源：评论

学校读者我要写书评

暂无评论

scalable algorithms for signal reconstruction by leveraging similarity joins

引用

VLDB JOURNAL 2020年第2-3期29卷 681-707页

作者： Asudeh, Abolfazl Augustine, Jees Nazi, Azade Thirumuruganathan, Saravanan Zhang, Nan Das, Gautam Srivastava, Divesh Univ Illinois Chicago IL 60607 USA Univ Texas Arlington Arlington TX 76019 USA Google AI Mountain View CA USA HBKU QCRI Ar Rayyan Qatar Penn State Univ State Coll PA USA AT&T Labs Res Florham Pk NJ USA

Signal reconstruction problem (SRP) is an important optimization problem where the objective is to identify a solution to an underdetermined system of linear equations that is closest to a given prior. It has a substantial number of applications in diverse areas including network traffic engineering, medical image reconstruction, acoustics, astronomy and many more. Most common approaches for SRP do not scale to large problem sizes. In this paper, we propose multiple optimization steps, developing scalable algorithms for the problem. We first propose a dual formulation of the problem and develop the Direct algorithm that is significantly more efficient than the state of the art. Second, we show how adapting database techniques developed for scalable similarity joins provides a significant speedup over Direct, scaling our proposal up to large-scale settings. Third, we describe a number of practical techniques that allow our algorithm to scale to settings of size in the order of a million by a billion. We also adapt our proposal to identify the top-k components of the solved system of linear equations. Finally, we consider the dynamic setting where the inputs to the linear system change and propose efficient algorithms inspired by the database techniques of materialization and reuse. Extensive experiments on real-world and synthetic data confirm the efficiency, effectiveness and scalability of our proposal.

关键词： Signal reconstruction Traffic reconstruction Underdetermined systems scalable algorithm

来源：评论

学校读者我要写书评

暂无评论

A scalable Space-Time Domain Decomposition Approach for Solving Large Scale Nonlinear Regularized Inverse Ill Posed Problems in 4D Variational Data Assimilation

引用

JOURNAL OF SCIENTIFIC COMPUTING 2022年第2期91卷 1-31页

作者： D'Amore, Luisa Constantinescu, Emil Carracciuolo, Luisa Univ Naples Federico II Naples Italy Argonne Natl Lab Math & Comp Sci Div Lemont IL USA Ist & Polimeri Compositi & Biomat CNR IPCB CNR Naples Italy

We address the development of innovative algorithms designed to solve the strong-constraint Four Dimensional Variational Data Assimilation (4DVar DA) problems in large scale applications. We present a space-time decomposition approach which employs the whole domain decomposition, i.e. both along the spacial and temporal direction in the overlapping case, and the partitioning of both the solution and the operator. Starting from the global functional defined on the entire domain, we get to a sort of regularized local functionals on the set of sub domains providing the order reduction of both the predictive and the Data Assimilation models. The algorithm convergence is developed. Performance in terms of reduction of time complexity and algorithmic scalability is discussed on the Shallow Water Equations on the sphere. The number of state variables in the model, the number of observations in an assimilation cycle, as well as numerical parameters as the discretization step in time and in space domain are defined on the basis of discretization grid used by data available at repository Ocean Synthesis/Reanalysis Directory of Hamburg University.

关键词： Data assimilation Space and time decomposition scalable algorithm Inverse problems Nonlinear least squares problems

来源：评论

学校读者我要写书评

暂无评论

An Accurate and Efficient Large-Scale Regression Method Through Best Friend Clustering

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 2022年第11期33卷 3129-3140页

作者： Li, Kun Yuan, Liang Zhang, Yunquan Chen, Gongwei Chinese Acad Sci Inst Comp Technol State Key Lab Comp Architecture Beijing 100190 Peoples R China Univ Chinese Acad Sci UCAS Sch Comp Sci & Technol Beijing 100190 Peoples R China Chinese Acad Sci Inst Comp Technol Key Lab Intelligent Informat Proc Beijing 100190 Peoples R China

As the data size in Machine Learning fields grows exponentially, it is inevitable to accelerate the computation by utilizing the ever-growing large number of available cores provided by high-performance computing hardware. However, existing parallel methods for clustering or regression often suffer from problems of low accuracy, slow convergence, and complex hyperparameter-tuning. Furthermore, the parallel efficiency is usually difficult to improve while striking a balance between preserving model properties and partitioning computing workloads on distributed systems. In this article, we propose a novel and simple data structure capturing the most important information among data samples. It has several advantageous properties supporting a hierarchical clustering strategy that contains well-defined metrics for determining optimal hierarchy, balanced partition for maintaining the clustering property, and efficient parallelization for accelerating computation phases. Then we combine the clustering with regression techniques as a parallel library and utilize a hybrid structure of data and model parallelism to make predictions. Experiments illustrate that our library obtains remarkable performance on convergence, accuracy, and scalability.

关键词： Clustering algorithms Training Mathematical models Computational modeling Libraries Kernel Support vector machines Distributed machine learning scalable algorithm large-scale clustering parallel regression

来源：评论

学校读者我要写书评

暂无评论

SGMiner: A Fast and scalable GPU-Based Frequent Pattern Miner on SSDs

引用

IEEE ACCESS 2022年 10卷 62502-62519页

作者： Chon, Kang-Wook Yi, Eunjeong Kim, Min-Soo Korea Inst Sci & Technol Informat Div Natl Supercomp Daejeon South Korea Daegu Gyeongbuk Inst Sci & Technol Dept Informat & Commun Engn Daegu South Korea Korea Adv Inst Sci & Technol Sch Comp Daejeon South Korea

Frequent itemset mining is extensively employed as an essential data mining technique. Nevertheless, as the data size grows, the applicability of this method decreases owing to the relatively poor performance of the existing methods. Though numerous efficient sequential frequent itemset mining methods have been developed, the performance that can be achieved is clearly limited by the fact that they exploit only one thread. To overcome these limitations, a number of parallel methods using multi-core central processing units (CPUs), multiple machines or many-core graphic processing units (GPU) have been proposed. However, these methods are relatively slow in performance and have low scalability, mainly owing to large memory requirements for intermediate data, significant disk I/Os, and heavy computation. In this study, to resolve the aforementioned problems, we propose SGMiner, which is a new, fast, and scalable GPU-and disk-based method on a single machine equipped with multiple graphic processing units (GPUs) and multiple solid-state drives (SSDs) for extracting frequent patterns. It is based on an algorithm similar to the Apriori algorithm and neither has intermediate data nor large disk I/O overheads owing to its exploitation of SSDs. Moreover, we propose storing transaction databases, namely bitmap transaction chunks, in SSDs, streaming the chunks to GPU device memory via the main memory with reduced I/O overhead, and performing fast support counting with GPUs based on the chunks. In addition, when exploiting multiple GPUs and SSDs, it proposes a concept of replicating bitmap transaction chunks stored in SSDs to GPUs in a streaming fashion. This could allow an almost equal workload to be distributed evenly across multiple GPUs with reduced I/O overheads. The experiments we conducted demonstrate that SGMiner outperforms the existing methods in terms of scalability and performance with enhanced robustness.

关键词： Big data frequent pattern mining parallel algorithm GPUs scalable algorithm disk-based algorithm

来源：评论

学校读者我要写书评

暂无评论

Network-Flow-Based Efficient Vehicle Dispatch for City-Scale Ride-Hailing Systems

引用

IEEE TRANSACTIONS ON INTELLIGENT TRANSPORTATION SYSTEMS 2022年第6期23卷 5526-5538页

作者： Xu, Yuhang Wang, Wanyuan Xiong, Guangwei Liu, Xiang Wu, Weiwei Liu, Kai Southeast Univ Sch Comp Sci & Engn Nanjing 211189 Peoples R China Chongqing Univ Sch Comp Sci Chongqing 400030 Peoples R China

Ride-hailing systems (RHSs) provide passengers with convenient and flexible mobility services, have played an important role in modern urban transportation. With the limited vehicles, RHSs wish to optimize the dispatch of vehicles to requests with the objective of serving as many requests as possible. To address such a city-scale vehicle dispatch problem with thousands of vehicles and requests in each epoch, existing algorithms always take a tradeoff between effectiveness (i.e., real-time) and efficiency (i.e., service rate), such as ignoring future demands to guarantee real-time or solving a complex combinatorial optimization to improve service rate. To guarantee the service rate in a real-time fashion, this paper proposes two novel network flow-based vehicle dispatch algorithms. A network flow-based algorithm (NFBA) is provided to deal with offline scenarios. By constructing the vehicle-shareability network, a min-cost flow is built to find the optimal dispatch of vehicles to requests. To improve the request service rate in real-time, an efficient multi-sample multi-network flow-based algorithm (MNFBA) is proposed for the online scenarios. Each min-cost flow is utilized for a sample of future requests, and online vehicle dispatch policy is averaged over these flows. Extensive simulations based on real-world trip datasets in New York City are conducted. The experimental results show that compared to the benchmarks, our proposed algorithm can generate the dispatch of vehicles to requests within seconds, but can greatly increase the daily request service rate.

关键词： Real-time systems Optimization Vehicles Prediction algorithms Heuristic algorithms Dispatching Demand forecasting Urban computing ride-hailing systems network flow scalable algorithm

来源：评论

学校读者我要写书评

暂无评论

A scalable algorithm for Constructing Frequent Pattern Tree

引用

INTERNATIONAL JOURNAL OF INTELLIGENT INFORMATION TECHNOLOGIES 2014年第1期10卷 42-56页

作者： Abdullah, Zailani Herawan, Tutut Noraziah, A. Deris, Mustafa Univ Malaysia Dept Comp Sci Terengganu Malaysia Univ Ahmad Dahlan Dept Math Educ Yogyakarta Indonesia Univ Malaysia Comp Syst & Software Engn Kuantan Malaysia Univ Tun Hussein Onn Malaysia Comp Sci & Informat Technol Johor Baharu Malaysia

Frequent Pattern Tree (FP-Tree) is a compact data structure of representing frequent itemsets. The construction of FP-Tree is very important prior to frequent patterns mining. However, there have been too limited efforts specifically focused on constructing FP-Tree data structure beyond from its original database. In typical FP-Tree construction, besides the prior knowledge on support threshold, it also requires two database scans;first to build and sort the frequent patterns and second to build its prefix paths. Thus, twice database scanning is a key and major limitation in completing the construction of FP-Tree. Therefore, this paper suggests scalable Trie Transformation Technique algorithm (T3A) to convert our predefined tree data structure, Disorder Support Trie Itemset (DOSTrieIT) into FP-Tree. Experiment results through two UCI benchmark datasets show that the proposed T3A generates FP-Tree up to 3 magnitudes faster than that the benchmarked FP-Growth.

关键词： Association Rules Data Mining Frequent patterns Frequent Pattern Tree (FP-Tree) scalable algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：