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

37th IEEE International Parallel and Distributed Processing Symposium (IPDPS)

作者： Krishna, Sudhindra Gopal Narasimhan, Aditya Radhakrishnan, Sridhar Sekharan, Chandra N. Univ Oklahoma Sch Comp Sci Norman OK 73019 USA Texas A&M Corpus Christi Dept Comp Sci Corpus Christi TX USA

ISBN: (纸本)9798350311990

The growing popularity of social networks and the massive influx of users have made it challenging to store and process the network/graph data quickly before the properties of the graph change due to graph evolution. Storing graphs or networks that represent entities and their relationships (such as individuals and their friends/followers in a social network) becomes more difficult as the number of users increases, resulting in massive graphs that are challenging to store in standard structures like matrices or adjacency lists. Research in this field has focused on reducing the memory footprint of these large graphs and minimizing the extra memory required for processing. However, there is a trade-off between time and space, as rigorous redundancy removal to achieve a small memory footprint consumes time, and querying becomes more time-consuming when traversing compressed structures compared to matrices or adjacency lists. In this paper, we introduce a parallel technique for constructing graphs using compressed sparse rows (CSR), which offers a smaller memory footprint and allows for parallel querying algorithms, such as fetching neighbors or checking edge existence. We extend our work to include parallel time-evolving differential compression of CSR using the prefix sum approach. Additionally, we measure the speed-up gained by using multiprocessors to compress the graph data. To evaluate our techniques, we perform empirical analysis on massive anonymized graphs, including Live-Journal, Pokec, Orkut, and WebNotreDame, which are publicly available. Overall, our results demonstrate that our proposed methods achieve a smaller memory footprint and faster querying compared to traditional storage structures, with additional speedup gained (up to 83% for the biggest graph with 3.07M nodes and 117.18M edges) through the use of multiprocessors.

关键词： Massive Social Networks Compression graph algorithms Time-Evolving

来源：评论

学校读者我要写书评

暂无评论

Maximum Clique Enumeration on the GPU

Maximum Clique Enumeration on the GPU

引用

37th IEEE International Parallel and Distributed Processing Symposium (IPDPS)

作者： Geil, Afton Porumbescu, Serban D. Owens, John D. Univ Calif Davis Dept Elect & Comp Engr Davis CA 95616 USA

ISBN: (纸本)9798350311990

We present an iterative breadth-first approach to maximum clique enumeration on the GPU. The memory required to store all of the intermediate clique candidates poses a significant challenge. To mitigate this issue, we employ a variety of strategies to prune away non-maximum candidates and present a thorough examination of the performance and memory benefits of each of these options. We also explore a windowing strategy as a middle-ground between breadth-first and depth-first approaches, and investigate the resulting tradeoff between parallel efficiency and memory usage. Our results demonstrate that when we are able to manage the memory requirements, our approach achieves high throughput for large graphs indicating this approach is a good choice for GPU performance. We demonstrate an average speedup of 1.9x over previous parallel work, and obtain our best performance on graphs with low average degree.

关键词： parallel GPU maximum clique graph algorithms

来源：评论

学校读者我要写书评

暂无评论

NOBGP: A Novel Optimized Balanced graph Partitioning Algorithm 19th

NOBGP: A Novel Optimized Balanced Graph Partitioning Algorit...

引用

19th CCF Conference on Computer Supported Cooperative Work and Social Computing, ChineseCSCW 2024

作者： Chen, Jiebin Hu, Ziqiang Ye, Renjie Zhang, Qishan Guo, Kun College of Computer and Data Science Fuzhou University Fuzhou350108 China Engineering Research Center of Big Data Intelligence Ministry of Education Fuzhou350108 China Fujian Key Laboratory of Network Computing and Intelligent Information Processing Fuzhou University Fuzhou350108 China Xianda College of Economics and Humanities Shanghai International Studies University Shanghai China

ISBN: (纸本)9789819623723

Large-scale graphs have become prevalent with the advent of the big data era. Distributed graph computing systems are commonly used for processing and analyzing large-scale graphs, with graph partitioning being a key prerequisite for their efficient computation. graph partitioning aims to balance the load across partitions while minimizing the number of cut-edges. Moreover, it should achieve high efficiency and scalability. However, the existing popular graph partitioning algorithms do not fully take into account the internal topology of real-world graphs, which affects the final partition quality and convergence. Meanwhile, they easily fall into the local optimum due to partition load constraints. This paper introduces a Novel Optimized Balanced graph Partitioning algorithm (NOBGP). First, we propose an initialization strategy based on label propagation of core vertices to achieve initial partitions with good locality and accelerate convergence. Second, we optimize the label propagation process to ensure balanced partitions and propose a probability-based disruption strategy to avoid the local optimum. We implement NOBGP on the distributed graph computing framework graphX. Extensive experimental results on real-world graphs show that the proposed algorithm is scalable and performs better than the existing algorithms. We also run PageRank and Louvain applications using the graph partitioning results to demonstrate the efficiency of our algorithm. © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

A Spatio-temporal graph Network Allowing Incomplete Trajectory Input for Pedestrian Trajectory Prediction

arXiv

引用

arXiv 2025年

作者： Long, Juncen Bardaro, Gianluca Mentasti, Simone Matteucci, Matteo Politecnico di Milano Milan Italy

Pedestrian trajectory prediction is important in the research of mobile robot navigation in environments with pedestrians. Most pedestrian trajectory prediction algorithms require the input historical trajectories to be complete. If a pedestrian is unobservable in any frame in the past, then its historical trajectory become incomplete, the algorithm will not predict its future trajectory. To address this limitation, we propose the STGN-IT, a spatio-temporal graph network allowing incomplete trajectory input, which can predict the future trajectories of pedestrians with incomplete historical trajectories. STGN-IT uses the spatio-temporal graph with an additional encoding method to represent the historical trajectories and observation states of pedestrians. Moreover, STGN-IT introduces static obstacles in the environment that may affect the future trajectories as nodes to further improve the prediction accuracy. A clustering algorithm is also applied in the construction of spatio-temporal graphs. Experiments on public datasets show that STGN-IT outperforms state of the art algorithms on these metrics. © 2025, CC BY-NC-ND.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

ON THE METRIC DIMENSION OF THE CHARACTER DEGREE graph OF A SOLVABLE GROUP

arXiv

引用

arXiv 2024年

作者： Cameron, Peter J. Sivanesan, G. Selvaraj, C. Chelvam, T. Tamizh Laubacher, Jacob School of Mathematics and Statistics University of St Andrews North Haugh St Andrews FifeKY16 9SS United Kingdom Department of Mathematics Government College of Engineering Tamil Nadu Salem636011 India Department of Mathematics Periyar University Tamil Nadu Salem636011 India Department of Mathematics Manonmaniam Sundaranar University Tamil Nadu Tirunelveli627 012 India Department of Mathematics St. Norbert College De PereWI54115 United States

Let G be a finite solvable group and let ∆(G) be the character degree graph of G. In this paper, we obtain the metric dimension of certain character degree graphs. Specifically, we calculate the metric dimension for a regular character degree graph, a character degree graph with a diameter of 2 that is not a block, a character degree graph with a diameter of 3 that also has a cut vertex and a character degree graph with Fitting height 2. We also consider two related parameters, base size and adjacency dimension, and their relation to metric dimension for character degree graphs of solvable *** Codes 05C25 © 2024, CC BY.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

ReeFRAME: Reeb graph based Trajectory Analysis Framework to Capture Top-Down and Bottom-Up Patterns of Life

arXiv

引用

arXiv 2024年

作者： Gudavalli, Chandrakanth Zhang, Bowen Levenson, Connor Lore, Kin Gwn Manjunath, B.S. ECE Department University of California Santa Barbara United States RTX Technology Research Center Connecticut United States

In this paper, we present ReeFRAME, a scalable Reeb graph-based framework designed to analyze vast volumes of GPS-enabled human trajectory data generated at 1Hz frequency. ReeFRAME models Patterns-of-life (PoL) at both the population and individual levels, utilizing Multi-Agent Reeb graphs (MARGs) for population-level patterns and Temporal Reeb graphs (TERGs) for individual trajectories. The framework's linear algorithmic complexity relative to the number of time points ensures scalability for anomaly detection. We validate ReeFRAME on six large-scale anomaly detection datasets, simulating real-time patterns with up to 500,000 agents over two months. © 2024, CC BY.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Bayesian Optimisation of Functions on graphs 37

Bayesian Optimisation of Functions on Graphs

引用

37th Conference on Neural Information Processing Systems, NeurIPS 2023

作者： Wan, Xingchen Osselin, Pierre Kenlay, Henry Ru, Binxin Osborne, Michael A. Dong, Xiaowen Department of Engineering Science University of Oxford United Kingdom

ISBN: (纸本)9781713899921

The increasing availability of graph-structured data motivates the task of optimising over functions defined on the node set of graphs. Traditional graph search algorithms can be applied in this case, but they may be sample-inefficient and do not make use of information about the function values;on the other hand, Bayesian optimisation is a class of promising black-box solvers with superior sample efficiency, but it has scarcely been applied to such novel setups. To fill this gap, we propose a novel Bayesian optimisation framework that optimises over functions defined on generic, large-scale and potentially unknown graphs. Through the learning of suitable kernels on graphs, our framework has the advantage of adapting to the behaviour of the target function. The local modelling approach further guarantees the efficiency of our method. Extensive experiments on both synthetic and real-world graphs demonstrate the effectiveness of the proposed optimisation framework. © 2023 Neural information processing systems foundation. All rights reserved.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

graph Inference with Effective Resistance Queries

arXiv

引用

arXiv 2025年

作者： Bennett, Huck Black, Mitchell Nayyeri, Amir Warton, Evelyn University of Colorado Boulder United States University of California San Diego United States Oregon State University United States

The goal of graph inference is to design algorithms for learning properties of a hidden graph using queries to an oracle that returns information about the graph. graph reconstruction, verification, and property testing are all special cases of graph inference. In this work, we study graph inference using an oracle that returns the effective resistance (ER) distance between a given pair of vertices. Effective resistance is a natural notion of distance that arises from viewing graphs as electrical circuits, and has many applications. However, it has received little attention from a graph inference perspective. Indeed, although it is known that an n-vertex graph can be uniquely reconstructed by making all (n2) = Θ(n2) possible ER queries, very little else is known. We address this and show a number of fundamental results in this model, including: 1. O(n)-query algorithms for testing whether a graph is a tree;deciding whether two graphs are equal assuming one is a subgraph of the other;and testing whether a given vertex (or edge) is a cut vertex (or cut edge). 2. Property testing algorithms, including for testing whether a graph is vertex-biconnected and whether it is edge-biconnected. We also give a reduction that shows how to adapt property testing results from the well-studied bounded-degree model to our model with ER queries. This yields ER-query-based algorithms for testing k-connectivity, bipartiteness, planarity, and containment of a fixed subgraph. 3. graph reconstruction algorithms, including an algorithm for reconstructing a graph from a low-width tree decomposition;a Θ(k2)-query, polynomial-time algorithm for recovering the entire adjacency matrix A of the hidden graph, given A with k of its entries deleted;and a k-query, exponential-time algorithm for the same task. We additionally compare the relative power of ER queries and shortest path queries, which are closely related and better studied. Interestingly, we show that the two query models are incomparabl

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

On Optimizing Locality of graph Transposition on Modern Architectures

arXiv

引用

arXiv 2025年

作者： Esfahani, Mohsen Koohi Vandierendonck, Hans

This paper investigates the shared-memory graph Transposition (GT) problem, a fundamental graph algorithm that is widely used in graph analytics and scientific computing. Previous GT algorithms have significant memory requirements that are proportional to the number of vertices and threads which obstructs their use on large graphs. Moreover, atomic memory operations have become comparably fast on recent CPU architectures, which creates new opportunities for improving the performance of concurrent atomic accesses in GT. We design PoTra, a GT algorithm which leverages graph structure and processor and memory architecture to optimize locality and performance. PoTra limits the size of additional data structures close to CPU cache sizes and utilizes the skewed degree distribution of graph datasets to optimize locality and performance. We present the performance model of PoTra to explain the connection between cache and memory response times and graph locality. Our evaluation of PoTra on three CPU architectures and 20 real-world and synthetic graph datasets with up to 128 billion edges demonstrates that PoTra achieves up to 8.7 times speedup compared to previous works and if there is a performance loss it remains limited to 15.7%, on average. © 2025, CC BY.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

Distributed Pose graph Optimization using the Splitting Method based on the Alternating Direction Method of Multipliers

arXiv

引用

arXiv 2025年

作者： Ebrahimi, Zeinab Deghat, Mohammad Mechanical and Manufacturing Engineering University of New South Wales SydneyNSW2016 Australia

Distributed optimization aims to leverage the local computation and communication capabilities of each agent to achieve a desired global objective. This paper addresses the distributed pose graph optimization (PGO) problem under non-convex constraints, with the goal of approximating the rotation and translation of each pose given relevant noisy measurements. To achieve this goal, the splitting method based on the concepts of the alternating direction method of multipliers (ADMM) and Bregman iteration are applied to solve the rotation subproblems. The proposed approach enables the iterative resolution of constrained problems, achieved through solving unconstrained problems and orthogonality-constrained quadratic problems that have analytical solutions. The performance of the proposed algorithm is compared against two practical methods in pose graph optimization: the Distributed Gauss-Seidel (DGS) algorithm and the centralized pose graph optimizer with an optimality certificate (SE-Sync). The efficiency of the proposed method is verified through its application to several simulated and real-world pose graph datasets. Unlike the DGS method, our approach attempts to solve distributed PGO problems without relaxing the non-convex constraints. © 2025, CC BY.

关键词： graph algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：