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

55th Annual ACM Symposium on Theory of Computing (STOC) part of the ACM Federated Computing Research Conference (FCRC)

作者： Anari, Nima Huang, Yizhi Liu, Tianyn Vuong, Thuy-Duong Nu, Brian Yu, Katherine Stanford Univ Stanford CA 94305 USA Tsinghua Univ Beijing Peoples R China

ISBN: (纸本)9781450399135

We develop a framework for sampling from discrete distributions on the hypercube {+/-1}(n)= by sampling from continuous distributions supported on R= obtained by convolution with spherical Gaussians. We show that for well-studied families of discrete distributions , convolving with Gaussians yields well-conditioned log-concave distributions, as long as the variance of the Gaussian is above an $ (1)1 degrees threshold. We then reduce the task of sampling from mu to sampling from Gaussian-convolved distributions. Our reduction is based on a stochastic process widely studied under different names: backward diffusion in diffusion models, and stochastic localization. We discretize this process in a novel way that allows for high accuracy and parallelism. As our main application, we resolve open questions Anari, Hu, Saberi, and Schild raised on the parallel sampling of distributions that admit parallel counting. We show that determinantal point processes can be sampled via RNC algorithms, that is in time log (n)(O(1))= log (n)(O(1)) using = log (n)(O(1)) processors. For a wider class of distributions, we show our framework yields Quasi-RNC sampling, i.e., log (n)(O(1)) time using log (n)(O(1)) processors. This wider class includes non-symmetric determinantal point processes and random Eulerian tours in digraphs, the latter nearly resolving another open question raised by prior work. Of potentially independent interest, we introduce and study a notion of smoothness for discrete distributions that we call transport stability, which we use to control the propagation of error in our framework. Additionally, we connect transport stability to constructions of optimally mixing local random walks and concentration inequalities.

关键词： sampling counting stochastic localization transport stability parallel algorithms determinantal point processes Eulerian tours

来源：评论

学校读者我要写书评

暂无评论

Minimizing spread of misinformation in social networks: a network topology based approach

引用

SOCIAL NETWORK ANALYSIS AND MINING 2025年第1期15卷 1-21页

作者： Ghoshal, Arnab Kumar Das, Nabanita Das, Soham Dhar, Subhankar Asutosh Coll Comp Sci Kolkata India BP Poddar Inst Management & Technol Comp Sci & Engn Kolkata India Microsoft Corp Redmond WA USA San Jose State Univ Sch Informat Syst & Technol San Jose CA USA

In the emerging landscape of online social networks (OSNs), the rapid dissemination of misinformation poses a significant challenge to the integrity of information shared among users. Hence, misinformation containment problem in OSNs has drawn significant attention nowadays. In this paper, given a fixed budget, the problem is formulated as minimizing misinformation spread (MMS) problem, which is shown to be an NP-hard problem. With the objective to combat the misinformation in real time, this paper explores a new direction to leverage the network topology to minimize the search space drastically. Based on the community structure of the OSN along with the trust relationship among nodes, a novel linear-time seed node selection algorithm is proposed here that is independent of the positions of the misinformed nodes. Once the set of seed nodes is selected, it can combat any situation of misinformation spread in the OSN, provided the community structure of the network does not change significantly. To the best of our knowledge, this work is the first where trust relationship among users is considered along with the community structure of the network, to control the spread of misinformation in real time. To analyze the diffusion dynamics pertaining to both true information and misinformation, competitive linear threshold model (LTM) with provision for belief switching is followed to provide a more realistic and comprehensive understanding of information diffusion dynamics. Extensive experimental studies on large scale OSNs demonstrate that in comparison to earlier works, the proposed technique obtains 47-74% improvements in performance parameters. Not only that, its parallel implementations also achieve around 51x\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$51\times$$\end{document} speedup

关键词： Online social networks (OSNs) Trust relationships Competitive linear threshold model Community structure Misinformation minimization parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Scalable Fine-Grained parallel Cycle Enumeration algorithms

arXiv

引用

arXiv 2022年

作者： Blanuša, Jovan Ienne, Paolo Atasu, Kubilay IBM Research Europe Zurich Switzerland School of Computer and Communication Sciences LausanneCH-1015 Switzerland School of Computer and Communication Sciences Switzerland

Enumerating simple cycles has important applications in computational biology, network science, and financial crime analysis. In this work, we focus on parallelising the state-of-the-art simple cycle enumeration algorithms by Johnson and Read-Tarjan along with their applications to temporal graphs. To our knowledge, we are the first ones to parallelise these two algorithms in a fine-grained manner. We are also the first to demonstrate experimentally a linear performance scaling. Such a scaling is made possible by our decomposition of long sequential searches into fine-grained tasks, which are then dynamically scheduled across CPU cores, enabling an optimal load balancing. Furthermore, we show that coarse-grained parallel versions of the Johnson and the Read-Tarjan algorithms that exploit edge- or vertex-level parallelism are not scalable. On a cluster of four multi-core CPUs with 256 physical cores, our fine-grained parallel algorithms are, on average, an order of magnitude faster than their coarse-grained parallel counterparts. The performance gap between the fine-grained and the coarse-grained parallel algorithms widens as we use more CPU cores. When using all 256 CPU cores, our parallel algorithms enumerate temporal cycles, on average, 260× faster than the serial algorithm of Kumar and Calders. Copyright © 2022, The Authors. All rights reserved.

关键词： parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Nearly Work-Efficient parallel DFS in Undirected Graphs 23

Nearly Work-Efficient Parallel DFS in Undirected Graphs

引用

35th ACM Symposium on parallelism in algorithms and Architectures (SPAA)

作者： Ghaffari, Mohsen Grunau, Christoph Qu, Jiahao MIT Cambridge MA 02139 USA Swiss Fed Inst Technol Zurich Switzerland

ISBN: (纸本)9781450395458

We present the first parallel depth-first search algorithm for undirected graphs that has near-linear work and sublinear depth. Concretely, in any n-node m-edge undirected graph, our algorithm computes a DFS in O(root n) depth and using (O) over tilde (m + n) work. All prior work either required Omega(n) depth, and thus were essentially sequential, or needed a high poly(n) work and thus were far from being work-efficient.

关键词： parallel algorithms depth-first search work-efficient

来源：评论

学校读者我要写书评

暂无评论

Invited Paper: On the Cost-Optimal parallel Solution of the Majority Problem

Invited Paper: On the Cost-Optimal Parallel Solution of the ...

引用

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

作者： Wu, Jie Temple Univ Ctr Networked Comp Philadelphia PA 19122 USA

ISBN: (纸本)9798350311990

The majority problem can be stated as follows: there is a collection of n bank cards that belong to different bank accounts. The only way to "read" these cards is through one or more two-input "equivalence testers". Each tester accepts two cards and outputs "yes" if two input cards correspond to the same bank account or "no" if they do not. The objective of the majority problem is to design a solution that uses the minimum number of tests to determine if more than n/2 cards belong to the same bank account and then find these cards. We first review two sequential solutions, including the Boyer-Moore optimal linear solution (i.e., with a time complexity of O(n)). Then, we introduce an optimal elimination solution together with a special structure to support a cost-optimal parallel solution that solves the problem in O(log n) using O(n/ log n) processors (i.e., testers). That is, this solution matches the optimal sequential solution with O(n) operations.

关键词： Cost-optimal solutions data structure parallel algorithms speedup

来源：评论

学校读者我要写书评

暂无评论

An Efficient parallel Sketch-based Algorithm for Mapping Long Reads to Contigs

An Efficient Parallel Sketch-based Algorithm for Mapping Lon...

引用

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

作者： Rahman, Tazin Bhowmik, Oieswarya Kalyanaraman, Ananth Washington State Univ Pullman WA 99164 USA

ISBN: (纸本)9798350311990

Long read technologies are continuing to evolve at a rapid pace, with the latest of the high fidelity technologies delivering reads over 10Kbp with high accuracy (99.9%). However, there also exist partially constructed assemblies using short read data. Hybrid assembly workflows provide a way to combine the information in both these data sources and generate highly improved and near complete assemblies and genomic scaffolds. In this paper, we address the problem of mapping long reads to contigs (representing prior constructed partial assemblies). This is a many-to-many comparison application. However, brute force comparisons of all pairs is not practical. Therefore, in this paper, we present a parallel, alignment-free sketching-based algorithm that efficiently maps long reads to contigs. More specifically, our approach uses a minimizer-based Jaccard estimator (or JEM), a variant of the classical MinHashing technique, as its sketch. Experimental evaluation shows that our parallel algorithm is highly effective in producing a high quality mapping while improving significantly the time to solution compared to state-of-the-art mapping tools. For instance, for a large genome Betta splendens (approximate to 350Mbp genome) with 429K HiFi long reads and 98K contigs, our JEM approach produces a mapping with 99.31% precision and 96.18% recall, while yielding 7.13x speedup over a state-of-the-art mapper (Mashmap).

关键词： hybrid assembly long read mapping sketching MinHashing parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

parallel Breadth-First Search and Exact Shortest Paths and Stronger Notions for Approximate Distances 2023

Parallel Breadth-First Search and Exact Shortest Paths and S...

引用

55th Annual ACM Symposium on Theory of Computing (STOC) part of the ACM Federated Computing Research Conference (FCRC)

作者： Rozhon, Vaclav Haeupler, Bernhard Martinsson, Anders Grunau, Christoph Zuzic, Goran Swiss Fed Inst Technol Zurich Switzerland CMU Pittsburgh PA 15213 USA

ISBN: (纸本)9781450399135

This paper introduces stronger notions for approximate single-source shortest-path distances and gives simple reductions to compute them from weaker standard notions of approximate distances. Strongly-approximate distances isolate, capture, and address the well-known barriers for using approximate distances algorithmically and their reductions directly address these barriers in a clean and modular manner. The reductions are model-independent and require only log(O(1)) black-box approximate distance computations. They apply equally to parallel, distributed, and semi-streaming settings. Strongly (1 +epsilon)-approximate distances are equivalent to exact distances in a (1 + epsilon)-perturbed graph and approximately satisfy the subtractive triangle inequality. In directed graphs, this is sufficient to reduce even exact distance computation to arbitrary (1 + epsilon)-approximate ones. Overall, this paper simplifies, unifies, and cleans up problemspecific ad-hoc solutions developed in many prior works, e.g., for ball-growing routines in undirected graphs and for computing exact distances in directed graphs. Several algorithmic results for parallel and distributed algorithms - some known, some new - are directly implied by our reductions. Applications of particular interest include the first work-efficient sublinear-depth parallel algorithm for breadth-first search and computing exact single-source shortest paths - both major open problems in parallel computing. Given a source vertex in a directed graph with polynomiallybounded nonnegative integer lengths the algorithm computes an exact shortest path tree in.. log(O(1)) work and n(1/2+o(1)) depth. Previously, no parallel algorithm improving the trivial linear depths of Dijkstra's algorithm without significantly increasing the work was known, even for the case of undirected and unit-length graphs, i.e., for computing a breadth-first-search tree. This result was independently obtained by Fineman and Cao.

关键词： parallel algorithms distributed algorithms bfs shortest path exact distances approximate distances

来源：评论

学校读者我要写书评

暂无评论

Optimal Round and Sample-Size Complexity for Partitioning in parallel Sorting 23

Optimal Round and Sample-Size Complexity for Partitioning in...

引用

35th ACM Symposium on parallelism in algorithms and Architectures (SPAA)

作者： Yang, Wentao Harsh, Vipul Solomonik, Edgar Univ Illinois Dept Comp Sci Urbana IL 61801 USA

ISBN: (纸本)9781450395458

State-of-the-art parallel sorting algorithms for distributed-memory architectures are based on computing a balanced partitioning via sampling and histogramming. By finding samples that partition the sorted keys into evenly-sized chunks, these algorithms minimize the number of communication rounds required. Histogramming (computing positions of samples) guides sampling, enabling a decrease in the overall number of samples collected. We derive lower and upper bounds on the number of sampling/histogramming rounds required to compute a balanced partitioning. We improve on prior results to demonstrate that when using p processors, O(log* p) rounds with O(p/log* p) samples per round suffice. We match that with a lower bound that shows that any algorithm with O(p) samples per round requires at least Omega(log* p) rounds. Additionally, we prove the Omega(p log p) samples lower bound for one round, thus proving that existing one round algorithms: sample sort, AMS sort [2] and HSS [16] have optimal sample size complexity. To derive the lower bound, we propose a hard randomized input distribution and apply classical results from the distribution theory of runs.

关键词： parallel algorithms parallel sorting communication cost communication lower bounds

来源：评论

学校读者我要写书评

暂无评论

A Simple and Efficient parallel Laplacian Solver 23

A Simple and Efficient Parallel Laplacian Solver

引用

35th ACM Symposium on parallelism in algorithms and Architectures (SPAA)

作者： Sachdeva, Sushant Zhao, Yibin Univ Toronto Toronto ON Canada

ISBN: (纸本)9781450395458

A symmetric matrix is called a Laplacian if it has nonpositive off-diagonal entries and zero row sums. Since the seminal work of Spielman and Teng (2004) on solving Laplacian linear systems in nearly linear time, several algorithms have been designed for the task. Yet, the work of Kyng and Sachdeva (2016) remains the simplest and most practical sequential solver. They presented a solver purely based on random sampling and without graph-theoretic constructions such as low-stretch trees and sparsifiers. In this work, we extend the result of Kyng and Sachdeva to a simple parallel Laplacian solver with O(m log(3) n log log n) or O((m + n log(5) n) log n log log n) work and O(log(2) n log log n) depth using the ideas of block Cholesky factorization from Kyng et al. (2016). Compared to the best known parallel Laplacian solvers that achieve polylogarithmic depth due to Lee et al. (2015), our solver achieves both better depth and, for dense graphs, better work.

关键词： Laplacian Linear Systems parallel algorithms Linear System Solvers

来源：评论

学校读者我要写书评

暂无评论

Quadratic Speedups in parallel Sampling from Determinantal Distributions 23

Quadratic Speedups in Parallel Sampling from Determinantal D...

引用

35th ACM Symposium on parallelism in algorithms and Architectures (SPAA)

作者： Anari, Nima Burgess, Callum Tian, Kevin Thuy-Duong Vuong Stanford Univ Stanford CA 94305 USA Microsoft Res Redmond WA USA

ISBN: (纸本)9781450395458

We study the problem of parallelizing sampling from distributions related to determinants: symmetric, nonsymmetric, and partitionconstrained determinantal point processes, as well as planar perfect matchings. For these distributions, the partition function, a.k.a. the count, can be obtained via matrix determinants, a highly parallelizable computation;Csanky proved it is in NC. However, parallel counting does not automatically translate to parallel sampling, as classic reductions between the two are inherently sequential. We show that a nearly quadratic parallel speedup over sequential sampling can be achieved for all the aforementioned distributions. If the distribution is supported on subsets of size k of a ground set, we show how to approximately produce a sample in (O) over tilde (k(1/2+c)) time with polynomially many processors for any constant c > 0. In the two special cases of symmetric determinantal point processes and planar perfect matchings, our bound improves to (O) over tilde(root k) and we show how to sample exactly in these cases. As our main technical contribution, we fully characterize the limits of batching for the steps of sampling-to-counting reductions. We observe that only O(1) steps can be batched together if we strive for exact sampling, even in the case of nonsymmetric determinantal point processes. However, we show that for approximate sampling, (O) over tilde (k(1/2-c)) steps can be batched together, for any entropically independent distribution, which includes all mentioned classes of determinantal point processes. Entropic independence and related notions have been the source of breakthroughs in Markov chain analysis in recent years, so we expect our framework to prove useful for distributions beyond those studied in this work.

关键词： sampling counting rejection sampling parallel algorithms determinantal point process planar perfect matchings

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：