1,720,985 research outputs found
Scaling betweenness centrality using communication-efficient sparse matrix multiplication
No full textBetweenness centrality (BC) is a crucial graph problem that measures the significance of a vertex by the number of shortest paths
leading through it. We propose Maximal Frontier Betweenness Centrality (MFBC): a succinct BC algorithm based on novel sparse matrix multiplication routines that performs a factor of p 1/3 less communication on p processors than the best known alternatives, for
graphs withn vertices and average degree k = n/p 2/3. We formulate, implement, and prove the correctness of MFBC for weighted graphs by leveraging monoids instead of semirings, which enables a surprisingly succinct formulation. MFBC scales well for both extremely sparse and relatively dense graphs. It automatically searches a space of distributed data decompositions and sparse matrix multiplication algorithms for the most advantageous configuration. The MFBC implementation outperforms the well-known CombBLAS library by up to 8x and shows more robust performance. Our design methodology is readily extensible to other graph problems
Parallel Gauss-Newton method for CP decomposition
Full text linkIn this thesis, we formulate the Gauss-Newton algorithm to make it viable for running on distributed memory architectures and comparative to Alternating least squares algorithm for CP decomposition. Alternating least squares may exhibit slow or no convergence, especially when high accuracy is required. CP decomposition problem can be formulated as a non-linear least squares problem to apply iterative Newton-like methods. Direct solution of linear systems involving an approximated Hessian is an expensive approach, however, recent advancements have shown that use of an implicit representation of the linear system makes these methods competitive with alternating least squares in terms of speed. We provide a parallel implementation of a Gauss-Newton method for CP decomposition, which iteratively solves linear least squares problems at each Gauss-Newton step. In particular, we leverage a formulation that employs tensor contractions for implicit matrix-vector products within the conjugate gradient method. The use of tensor contractions enables us to employ the Cyclops library for distributed-memory tensor computations to parallelize the Gauss-Newton approach with a high-level Python implementation. In addition to that, we introduce a regularization scheme for the Gauss-Newton method which shows better convergence results across a variety of tensors. We study the convergence of variants of the Gauss-Newton method relative to Alternating least squares for finding exact CP decompositions as well as approximate decompositions of real-world tensors.Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2020-08-25 without embargo termsThe student, Navjot Singh, accepted the attached license on 2020-05-15 at 16:46.The student, Navjot Singh, submitted this Thesis for approval on 2020-05-15 at 16:46.This Thesis was approved for publication on 2020-05-15 at 16:54.DSpace SAF Submission Ingestion Package generated from Vireo submission #15413 on 2020-08-25 at 17:15:10Made available in DSpace on 2020-08-26T21:58:11Z (GMT). No. of bitstreams: 2
SINGH-THESIS-2020.pdf: 693088 bytes, checksum: cb5a4f67a28b2af4497e31dae9b31510 (MD5)
LICENSE.txt: 4209 bytes, checksum: ccac5fa6be0f108bec87e0dea75d1383 (MD5)
Previous issue date: 2020-05-1
Optimal round and sample-size complexity for partitioning in parallel sorting
Full text linkSubmission published under a 24 month embargo labeled 'Closed Access', the embargo will last until 2024-05-01The student, Wentao Yang, accepted the attached license on 2022-04-28 at 00:17.The student, Wentao Yang, submitted this Thesis for approval on 2022-04-28 at 00:26.This Thesis was approved for publication on 2022-04-28 at 09:16.DSpace SAF Submission Ingestion Package generated from Vireo submission #17684 on 2022-11-11 at 12:57:58State-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/parts, O(log∗ p) rounds with O(p/ log∗ p) samples per round suffice. We match that with a lower bound that shows any algorithm requires at least Ω(log∗ p) rounds with O(p) samples per round. Additionally, we prove the Ω(p log p) samples lower bound for one round, showing the optimality of sample sort in this case. To derive the lower bound, we propose a hard randomized input distribution and apply classical results from the distribution theory of runs
QR factorization over tunable processor grids
Full text linkThe increasing complexity of modern computer architectures has greatly influenced algorithm design. Algorithm performance on these architectures is now determined by the movement of data. Therefore,
modern algorithms should prioritize minimizing communication.
In this work, we present a new parallel QR factorization algorithm solved over a
tunable processor grid in a distributed memory environment. The processor grid can be
tuned between one and three dimensions, resulting in tradeoffs in the asymptotic costs of
synchronization, horizontal bandwidth,
flop count, and memory footprint. This parallel algorithm is
the first to efficiently extend the Cholesky-QR2 algorithm to matrices with an
arbitrary number of rows and columns. Along its critical path of execution on P processors, our tunable algorithm improves upon the horizontal bandwidth cost of the existing
Cholesky-QR2 algorithm by up to a factor of c^2 when solved over a c x d x c processor grid
subject to P = c^2 d and E[1,P^1/3].
The costs attained by our algorithm are asymptotically
equivalent to state-of-the-art QR factorization algorithms that have yet to
be implemented.
We argue that ours achieves better practicality and
flexibility while still attaining minimal communication.Open Restriction set for Item 102919 on 2017-08-21T15:06:31Z with date null by [email protected] by Janice Progen ([email protected]) on 2017-08-21T15:47:32Z
No. of bitstreams: 1
ECE499-Sp2017-hutter-Edward.pdf: 576828 bytes, checksum: e0a59801172ff301c573b0b7d55e5ecb (MD5)Approved for entry into archive by James Hutchinson ([email protected]) on 2017-08-22T14:10:23Z (GMT) No. of bitstreams: 1
ECE499-Sp2017-hutter-Edward.pdf: 576828 bytes, checksum: e0a59801172ff301c573b0b7d55e5ecb (MD5)Made available in DSpace on 2017-08-22T14:10:23Z (GMT). No. of bitstreams: 1
ECE499-Sp2017-hutter-Edward.pdf: 576828 bytes, checksum: e0a59801172ff301c573b0b7d55e5ecb (MD5)
Previous issue date: 2017-05Ope
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Variations on the Author
Full text link“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
Appropriate Similarity Measures for Author Cocitation Analysis
Full text linkWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
Dispelling the Myths Behind First-author Citation Counts
Full text linkWe conducted a full-scale evaluative citation analysis study of scholars in the XML research field to explore just how different from each other author rankings resulting from different citation counting methods actually are, and to demonstrate the capability of emerging data and tools on the Web in supporting more realistic citation counting methods. Our results contest some common arguments for the continued
use of first-author citation counts in the evaluation of scholars, such as high correlations between author rankings by first-author citation counts and other citation
counting methods, and high costs of using more realistic citation counting methods that are not well-supported by the ISI databases. It is argued that increasingly available digital full text research papers make it possible for citation analysis studies to go beyond what the ISI databases have directly supported and to employ more
sophisticated methods
- …
