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

A Novel Key Point Based MLCS Algorithm for Big Sequences Mining

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2025年第1期37卷 15-28页

作者： Li, Yanni Liu, Bing Duan, Tihua Wang, Zhi Li, Hui Cui, Jiangtao Xidian Univ Sch Comp Sci & Technol Xian 710071 Peoples R China Univ Illinois Dept Comp Sci Chicago IL 60607 USA Shanghai Yushang Informat Technol Co Ltd Shanghai 201620 Peoples R China

Mining multiple longest common subsequences (MLCS) from a set of sequences of length three or more over a finite alphabet (a classical NP-hard problem) is an important task in many fields, e.g., bioinformatics, computational genomics, pattern recognition, information extraction, etc. Applications in these fields often involve generating very long sequences (length >= 10,000), referred to as big sequences. Despite efforts in improving the time and space complexities of MLCS mining algorithms, both existing exact and approximate algorithms face challenges in handling big sequences due to the overwhelming size of their problem-solving graph model MLCS-DAG (Directed Acyclic Graph), leading to the issue of memory explosion or extremely high time complexity. To bridge the gap, this paper first proposes a new identification and deletion strategy for different classes of non-critical points in the mining of MLCS, which are the points that do not contribute to their MLCSs mining in the MLCS-DAG. It then proposes a new MLCS problem-solving graph model, namely DAG(KP) (a new MLCS-DAG containing only Key Points). A novel parallel MLCS algorithm, called KP-MLCS (Key Point based MLCS), is also presented, which can mine and compress all MLCSs of big sequences effectively and efficiently. Extensive experiments on both synthetic and real-world biological sequences show that the proposed algorithm KP-MLCS drastically outperforms the existing state-of-the-art MLCS algorithms in terms of both efficiency and effectiveness.

关键词： Approximation algorithms parallel algorithms Problem-solving Finite element analysis Directed acyclic graph Data mining NP-hard problem Heuristic algorithms Face recognition MLCS (Multiple longest common subsequence) Explosions MLCS-DAG (Directedacyclic graph) DAG(KP) (a new MLCS-DAG containing only key points) non-critical points KP-MLCS (Key point based MLCS) non-critical points

来源：评论

学校读者我要写书评

暂无评论

Specular Path Generation and Near-Reflective Diffraction in Interactive Acoustical Simulations

引用

IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS 2024年第7期30卷 3609-3621页

作者： Pisha, Louis Yadegari, Shahrokh Univ Calif San Diego Sonic Arts Res & Dev Qualcomm Inst San Diego CA 92093 USA

Most systems for simulating sound propagation in a virtual environment for interactive applications use ray- or path-based models of sound. With these models, the "early" (low-order) specular reflection paths play a key role in defining the "sound" of the environment. However, the wave nature of sound, and the fact that smooth objects are approximated by triangle meshes, pose challenges for creating realistic approximations of the reflection results. Existing methods which produce accurate results are too slow to be used in most interactive applications with dynamic scenes. This paper presents a method for reflections modeling called spatially sampled near-reflective diffraction (SSNRD), based on an existing approximate diffraction model, Volumetric Diffraction and Transmission (VDaT). The SSNRD model addresses the challenges mentioned above, produces results accurate to within 1-2 dB on average compared to edge diffraction, and is fast enough to generate thousands of paths in a few milliseconds in large scenes. This method encompasses scene geometry processing, path trajectory generation, spatial sampling for diffraction modeling, and a small deep neural network (DNN) to produce the final response of each path. All steps of the method are GPU-accelerated, and NVIDIA RTX real-time ray tracing hardware is used for spatial computing tasks beyond just traditional ray tracing.

关键词： Diffraction Reflection Computational modeling Solid modeling Acoustics Real-time systems Graphics processing units graph and tree search strategies neural nets parallel algorithms raytracing virtual reality

来源：评论

学校读者我要写书评

暂无评论

parallel finite-difference algorithms for three-dimensional space-fractional diffusion equation with ψ-Caputo derivatives

引用

COMPUTATIONAL & APPLIED MATHEMATICS 2020年第3期39卷 1-20页

作者： Bohaienko, V. O. NAS Ukraine VM Glushkov Inst Cybernet Glushkov Ave 40 Kiev Ukraine

The paper deals with the issues of parallel computations' organization while solving three-dimensional space-fractional diffusion equation with the psi-Caputo derivatives using finite difference schemes. For an implicit scheme and locally one-dimensional splitting scheme, we present parallel algorithms for distributed memory systems that use one-dimensional block and red-black data partitioning. To reduce the order of algorithms' computational complexity, we use an approach based on the expansion of integral operator's kernel into series. We present the theoretical estimates of parallel algorithms' performance and the results of computational experiments conducted on a testing problem that has an analytical solution for the case of the Caputo-Katugampola derivative. The results of the experiments show close-to-linear parallelization efficiency of one-dimensional splitting scheme with block partitioning and inefficiency of red-black partitioning in this case. For the implicit scheme, the scalability of parallel algorithms is weak and the use of red-black partitioning is more efficient than the use of block partitioning when running on a small number of computational resources.

关键词： Diffusion Space-fractional differential equation parallel algorithms psi-Caputo derivative Finite-difference approximation Splitting schemes

来源：评论

学校读者我要写书评

暂无评论

Distributed Augmentation, Hypersweeps, and Branch Decomposition of Contour Trees for Scientific Exploration

引用

IEEE TRANSACTIONS ON VISUALIZATION AND COMPUTER GRAPHICS 2025年第1期31卷 152-162页

作者： Li, Mingzhe Carr, Hamish Rubel, Oliver Wang, Bei Weber, Gunther H. Univ Utah Salt Lake City UT 84112 USA Univ Leeds Leeds England Lawrence Berkeley Natl Lab Berkeley CA USA

Contour trees describe the topology of level sets in scalar fields and are widely used in topological data analysis and visualization. A main challenge of utilizing contour trees for large-scale scientific data is their computation at scale using high-performance computing. To address this challenge, recent work has introduced distributed hierarchical contour trees for distributed computation and storage of contour trees. However, effective use of these distributed structures in analysis and visualization requires subsequent computation of geometric properties and branch decomposition to support contour extraction and exploration. In this work, we introduce distributed algorithms for augmentation, hypersweeps, and branch decomposition that enable parallel computation of geometric properties, and support the use of distributed contour trees as query structures for scientific exploration. We evaluate the parallel performance of these algorithms and apply them to identify and extract important contours for scientific visualization.

关键词： branch decomposition Contour trees parallel algorithms computational topology computational topology topological data analysis topological data analysis computational topology topological data analysis

来源：评论

学校读者我要写书评

暂无评论

SLoB: Suboptimal Load Balancing Scheduling in Local Heterogeneous GPU Clusters for Large Language Model Inference

引用

IEEE TRANSACTIONS ON COMPUTATIONAL SOCIAL SYSTEMS 2024年第6期11卷 7941-7951页

作者： Jiang, Peiwen Wang, Haoxin Cai, Zinuo Gao, Lintao Zhang, Weishan Ma, Ruhui Zhou, Xiaokang Shanghai Jiao Tong Univ Sch Elect Informat & Elect Engn Shanghai 200240 Peoples R China Shanghai Aerosp Syst Engn Inst Shanghai 201111 Peoples R China China Univ Petr East China Qingdao Inst Software Coll Comp Sci & Technol Qingdao 266555 Peoples R China Kansai Univ Business Data Sci Osaka 5650823 Japan

Large language models (LLMs) are becoming powerful engines for social productivity in the manufacturing lifecycle. Existing application-level LLMs inference services focus on large datacenter and small edge intelligence (EI) scenarios, adopting iteration-level batch schedulers to solve resource utilization and inference speed problems. However, these services are incompatible with the scene of medium-sized local heterogeneous graphics processing unit (GPU) clusters with specific patterns, whose scale is between the two aforementioned scenarios. This type of scene proposes tradeoff problems for inference resource and speed, as well as user satisfaction problems for the semisparse frequency of queries with streaming responses. We propose suboptimal load balancing (SLoB), a distributed LLMs inference service scheduler in medium-sized local heterogeneous GPU clusters. SLoB leverages a multilevel adapter to accommodate LLMs usage patterns of scenes and balance resource utilization with inference efficiency. For semisparse problems, it adopts a mixed-priority pipeline scheduler with the least-padding principle to improve users' satisfaction, a metric considering the weights of different tokens in streaming responses. Based on the system prototype, our experiments under simulated workloads demonstrate that SLoB gains a maximum improvement of 29.4x under the satisfaction metric compared with the traditional run-to- completion scheduling solution while improving by up to 3.0x compared with the state-of-the-art (SOTA) solution Orca.

关键词： Task analysis Manufacturing Graphics processing units Adaptation models Job shop scheduling Transformers Pipelines Heterogeneous GPU clusters inference service large language models parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

A Novel Completion Method for Sparse Traffic Data Imputation

引用

IEEE INTELLIGENT TRANSPORTATION SYSTEMS MAGAZINE 2025年第3期17卷 96-108页

作者： Ouyang, Renqiu Hu, Yikun Wang, Haotian Hu, Rong Yang, Wangdong Li, Kenli Hunan Univ Changsha 410082 Peoples R China Hunan Univ Comp Sci & Technol Changsha 410082 Peoples R China

Traffic data imputation is essential in smart cities and the Internet of Things (IoT). Tensor completion is an efficient method for traffic data imputation. However, these methods overlook the integration of contextual and spatial information, which are important for traffic data imputation. Hence, this study proposes a novel tensor completion method leveraging contextual and spatial information for sparse traffic data imputation (STDI). Initially, we develop a model for STDI, treating traffic data as tensors and applying tensor completion for imputing missing values. Then, to account for contextual information, we compute the contextual scores of roads and reorganize the road indices according to the scores. Additionally, we utilize the Laplacian matrix to reveal spatial information and optimize the objective function to enhance imputation accuracy. Finally, we design a parallel algorithm for STDI on GPU for efficient computation. Extensive experiments demonstrate that the proposed method is superior to existing methods.

关键词： Tensors Roads Laplace equations Imputation Trajectory Data models Sparse matrices parallel algorithms Linear programming Internet of Things

来源：评论

学校读者我要写书评

暂无评论

Efficient Density-peaks Clustering algorithms on Static and Dynamic Data in Euclidean Space

引用

ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA 2024年第1期18卷 2-2页

作者： Amagata, Daichi Hara, Takahiro Osaka Univ Suita Osaka Japan

Clustering multi-dimensional points is a fundamental task in many fields, and density-based clustering supports many applications because it can discover clusters of arbitrary shapes. This article addresses the problem of Density-Peaks Clustering (DPC) in Euclidean space. DPC already has many applications, but its straightforward implementation incurs O(n(2)) time, where n is the number of points, thereby does not scale to large datasets. To enable DPC on large datasets, we first propose empirically efficient exact DPC algorithm, Ex-DPC. Although this algorithm is much faster than the straightforward implementation, it still suffers from O(n(2)) time theoretically. We hence propose a new exact algorithm, Ex-DPC++, that runs in o(n(2)) time. We accelerate their efficiencies by leveraging multi-threading. Moreover, real-world datasets may have arbitrary updates (point insertions and deletions). It is hence important to support efficient cluster updates. To this end, we propose D-DPC for fully dynamic DPC. We conduct extensive experiments using real datasets, and our experimental results demonstrate that our algorithms are efficient and scalable.

关键词： Density-peaks clustering parallel algorithms multi-dimensional points

来源：评论

学校读者我要写书评

暂无评论

Enhancing Scalability and Performance in Influence Maximization with Optimized parallel Processing

Enhancing Scalability and Performance in Influence Maximizat...

引用

2024 Workshops of the International Conference for High Performance Computing, Networking, Storage and Analysis, SC Workshops 2024

作者： Wu, Hanjiang Xu, Huan Park, Joongun Tithi, Jesmin Jahan Checconi, Fabio Wolfson-Pou, Jordi Petrini, Fabrizio Krishna, Tushar Georgia Institute of Technology United States Intel Corporation United States

ISBN: (纸本)9798350355543

Influence Maximization (IM) is vital in viral marketing and biological network analysis for identifying key in-fluencers. Given its NP-hard nature, approximate solutions are employed. This paper addresses scalability challenges in scale-out shared memory system by focusing on the state-of-the-art Influence Maximization via Martingales (IMM) benchmark. To enhance the work efficiency of the current IMM implementation, we propose EFFICIENTIMM with key strategies, including new parallelization scheme, NUMA-aware memory usage, dynamic load balancing and fine-grained adaptive data structures. Benchmarking on a 128-core CPU system with 8 NUMA nodes, EFFICI-ENTIMM demonstrated significant performance improvements, achieving an average 5.9x speedup over Ripples across 8 diverse SNAP datasets, when compared to the best execution times of the original Ripples framework. Additionally, on the Youtube graph, EFFICIENTIMM demonstrates a better memory access pattern with 357.4x reduction in L1+L2 cache misses as compared to Ripples. © 2024 IEEE.

关键词： data mining influence maximization parallel algorithms shared-memory social networks

来源：评论

学校读者我要写书评

暂无评论

Batch Learning SDDP for Long-Term Hydrothermal Planning

引用

IEEE TRANSACTIONS ON POWER SYSTEMS 2024年第1期39卷 614-627页

作者： Avila, Daniel Papavasiliou, Anthony Lohndorf, Nils Catholic Univ Louvain CORE B-1348 Louvain La Neuve Belgium Natl Tech Univ Athens Elect & Comp Engn Zografos 15780 Greece Univ Luxembourg L-4365 Esch Sur Alzette Luxembourg

We consider the stochastic dual dynamic programming (SDDP) algorithm - a widely employed algorithm applied to multistage stochastic programming - and propose a variant using experience replay - a batch learning technique from reinforcement learning. To connect SDDP with reinforcement learning, we cast SDDPas aQ-learning algorithm and describe its application in both risk-neutral and risk-averse settings. We demonstrate the superiority of the algorithm over conventional SDDP by benchmarking it against PSR's SDDP software using a large-scale instance of the long-term planning problem of inter-connected hydropower plants in Colombia. We find that SDDP with batch learning is able to produce tighter optimality gaps in a shorter amount of time than conventional SDDP. We also find that batch learning improves the parallel efficiency of SDDP backward passes.

关键词： Dynamic programming hydroelectric-thermal power generation parallel algorithms SDDP stochastic optimal control

来源：评论

学校读者我要写书评

暂无评论

Large-Scale K-Clustering

引用

ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA 2024年第9期18卷 1-23页

作者： Voevodski, Konstan tin Google Inc Mountain View CA 94043 USA

Large-scale learning algorithms are essential for modern data collections that may have billions of data points. Here, we study the design of parallel k-clustering algorithms, which include the k-median, k-medoids, and k-means clustering problems. We design efficient parallel algorithms for these problems and prove that they still compute constant-factor approximations to the optimal solution for stable clustering instances. In addition to our theoretic results, we present computational experiments that show that our k-median and k-means algorithms work well in practice-we are able to find better clusterings than state-of-the-art coreset constructions using samples of the same size.

关键词： parallel algorithms large scale learning unsupervised learning clustering k-median k-medoids k-means

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：