David A. Bader
David A. Bader
Home
People
Posts
Projects
Books
Publications
Talks
Contact
CV
Light
Dark
Automatic
1
Fast Triangle Counting (Graph Challenge Innovation Award)
Listing and counting triangles in graphs is a key algorithmic kernel for network analyses including community detection, clustering …
David Bader
PDF
Cite
Triangle Counting Through Cover-Edges (Graph Challenge Student Innovation Award)
Counting and finding triangles in graphs is often used in real-world analytics to characterize cohesiveness and identify communities in …
David Bader
,
Fuhuan Li
,
Anya Ganeshan
,
Ahmet Gundogdu
,
Jason Lew
,
Oliver Alvarado Rodriguez
,
Zhihui Du
PDF
Cite
Property Graphs in Arachne
Analyzing large-scale graphs poses challenges due to their increasing size and the demand for interactive and user-friendly analytics …
Oliver Alvarado Rodriguez
,
Fernando Vera Buschmann
,
Zhihui Du
,
David Bader
PDF
Cite
Parallel Longest Common SubSequence Analysis In Chapel
One of the most critical problems in the field of string algorithms is the longest common subsequence problem (LCS). The problem is …
Soroush Vahidi
,
Baruch Schieber
,
Zhihui Du
,
David Bader
PDF
Cite
Parallel Triangles and Squares Count for Multigraphs Using Vertex Covers
Triangles and squares count are widely-used graph analytic metrics providing insights into the connectivity of a graph. While the …
Luca Cappelletti
,
Tommaso Fontana
,
Oded Green
,
David Bader
PDF
Cite
DOI
Minimum-Mapping based Connected Components Algorithm
Finding connected components is a fundamental problem in graph analysis. We develop a novel minimum- mapping based Contour algorithm to …
Zhihui Du
,
Oliver Alvarado Rodriguez
,
Fuhuan Li
,
Mohammad Dindoost"
,
David Bader
PDF
Cite
Billion-scale Detection of Isomorphic Nodes
This paper presents an algorithm for detecting attributed high-degree node isomorphism. High-degree isomorphic nodes seldom happen by …
Luca Cappelletti
,
Tommaso Fontana
,
Justin Reese
,
David Bader
PDF
Cite
DOI
High-Performance Truss Analysis in Arkouda
In graph analytics, the Truss is a cohesive subgraph based on the number of triangles supporting each edge. It is widely used for …
Zhihui Du
,
Joseph Patchett
,
Oliver Alvarado Rodriguez
,
Fuhuan Li
,
David Bader
PDF
Cite
DOI
Parallel Suffix Sorting for Large String Analytics
The suffix array is a fundamental data structure to support string analysis efficiently. It took about 26 years for the sequential …
Zhihui Du
,
Sen Zhang
,
David Bader
PDF
Cite
DOI
Triangle Centrality in Arkouda
There are a wide number of graph centrality metrics. Further, the performance of each can vary widely depending on the type of …
Joseph Patchett
,
Zhihui Du
,
Fuhuan Li
,
David Bader
PDF
Cite
Arachne: An Arkouda Package for Large-Scale Graph Analytics
Due to the emergence of massive real-world graphs, whose sizes may extend to terabytes, new tools must be developed to enable data …
Oliver Alvarado Rodriguez
,
Zhihui Du
,
Joseph Patchett
,
Fuhuan Li
,
David Bader
PDF
Cite
DOI
Truss Analytics Algorithms and Integration in Arkouda
The K-Truss of a graph is a cohesive subgraph that has been widely used for community detection in applications such as social networks …
Zhihui Du
,
Joseph Patchett
,
Oliver Alvarado Rodriguez
,
David Bader
PDF
Cite
Anti-Section Transitive Closure
The transitive closure of a graph is a new graph where every vertex is directly connected to all vertices to which it had a path in the …
Oded Green
,
Zhihui Du
,
Sanyamee Patel
,
Zehui Xie
,
Hang Liu
,
David Bader
PDF
Cite
DOI
Large Scale String Analytics In Arkouda
Large scale data sets from the web, social networks, and bioinformatics are widely available and can often be represented by strings …
Zhihui Du
,
Oliver Alvarado Rodriguez
,
David Bader
PDF
Cite
DOI
Enabling Exploratory Large Scale Graph Analytics through Arkouda
Exploratory graph analytics helps maximize the informational value from a graph. However, the increasing graph size makes it impossible …
Zhihui Du
,
Oliver Alvarado Rodriguez
,
David Bader
PDF
Cite
DOI
A GraphBLAS implementation of Triangle Centrality
Identifying key members in large social network graphs is an important graph analytic. Recently, a new centrality measure called …
Fuhuan Li
,
David Bader
PDF
Cite
DOI
K-Truss Implementation in Arkouda (Extended Abstract)
K-Truss Implementation in Arkouda, a data science framework for graph analytics. Arkouda is an open source framework.
Joseph Patchett
,
Zhihui Du
,
David Bader
PDF
Cite
Exploratory Large Scale Graph Analytics in Arkouda
Exploratory graph analytics helps maximize the informational value for a graph. However, the increasing graph size makes it impossible …
Zhihui Du
,
Oliver Alvarado Rodriguez
,
David A. Bader
,
Michael Merrill
,
William Reus
PDF
Cite
LAGraph: Linear Algebra, Network Analysis Libraries, and the Study of Graph Algorithms
Graph algorithms can be expressed in terms of linear algebra. GraphBLAS is a library of low-level building blocks for such algorithms …
Gábor Szárnyas
,
David A. Bader
,
Timothy A. Davis
,
James Kitchen
,
Timothy G. Mattson
,
Scott McMillan
,
Erik Welch
PDF
Cite
DOI
An Efficient LP Rounding Scheme for Replica Placement
Large fault-tolerant network systems with high Quality of Service (QoS) guarantee are critical in many real world applications and …
Zhihui Du
,
Sen Zhang
,
David Bader
,
Jingkun Hu
PDF
Cite
DOI
GPU Accelerated Anomaly Detection of Large Scale Light Curves
Identifying anomalies in millions of stars in real time is a great challenge. In this paper, we develop a matched filtering based …
Austin Chase Minor
,
Zhihui Du
,
Yankui Sun
,
David Bader
,
Chao Wu
,
Jianyan Wei
PDF
Cite
DOI
Using RAPIDS AI to Accelerate Graph Data Science Workflows
This Scale free networks are abundant in many natural, social, and engineering phenomena for which there exists a substantial corpus of …
Todd Hricik
,
David Bader
,
Oded Green
PDF
Cite
DOI
Accelerating and Expanding End-to-End Data Science Workflows with DL/ML Interoperability Using RAPIDS
The lines between data science (DS), machine learning (ML), deep learning (DL), and data mining continue to be blurred and removed. …
Bartley Richardson
,
Bradley Rees
,
Tom Drabas
,
Even Oldridge
,
David Bader
,
Rachel Allen
PDF
Cite
DOI
Performance Impact of Memory Channels on Sparse and Irregular Algorithms
Graph processing is typically considered to be a memory-bound rather than compute-bound problem. One common line of thought is that …
Oded Green
,
James Fox
,
Jeff Young
,
David Bader
PDF
Cite
DOI
Skip the Intersection: Quickly Counting Common Neighbors on Shared-Memory Systems
Counting common neighbors between all vertex pairs in a graph is a fundamental operation, with uses in similarity measures, link …
Kasimir Gabert
,
James Fox
,
Oded Green
,
Xiaojing An
,
David A. Bader
PDF
Cite
DOI
A New Algorithmic Model for Graph Analysis of Streaming Data
The constant and massive influx of new data into analysis systems needs to be addressed without assuming we can pause the onslaught. …
Chunxing Yin
,
Jason Riedy
,
David A. Bader
PDF
Cite
Fast and Adaptive List Intersections on the GPU
List intersections are ubiquitous and can be found in a wide range of applications, including triangle counting and finding the maximal …
James Fox
,
Oded Green
,
Kasimir Gabert
,
Xiaojing An
,
David A. Bader
PDF
Cite
DOI
Hornet: An Efficient Data Structure for Dynamic Sparse Graphs and Matrices on GPUs
Sparse data computations are ubiquitous in science and engineering. Unlike their dense data counterparts, sparse data computations have …
Federico Busato
,
Oded Green
,
Nicola Bombieri
,
David A. Bader
PDF
Cite
DOI
Introduction to HiCOMB 2018
Presents the introductory welcome message from the conference proceedings. May include the conference officers’ congratulations …
Srinivas Aluru
,
David A. Bader
,
Paul Medvedev
PDF
Cite
DOI
Logarithmic Radix Binning and Vectorized Triangle Counting
Triangle counting is a building block for numerous graph applications and given the fact that graphs continue to grow in size, its …
Oded Green
,
James Fox
,
Alex Watkins
,
Alok Tripathy
,
Kasimir Gabert
,
Euna Kim
,
Xiaojing An
,
Kumar Aatish
,
David A. Bader
PDF
Cite
DOI
Massive-scale Streaming Analytics: Models, Parallelism, & Real-world Applications
Emerging real-world graph problems include: detecting and preventing disease in human populations; revealing community structure in …
David A. Bader
PDF
Cite
DOI
Ranking in Dynamic Graphs Using Exponential Centrality
Many large datasets from several fields of research such as biology or society can be represented as graphs. Additionally in many real …
Eisha Nathan
,
James Fairbanks
,
David Bader
PDF
Cite
DOI
Scalable Katz Ranking Computation in Large Static and Dynamic Graphs
Network analysis defines a number of centrality measures to identify the most central nodes in a network. Fast computation of those …
Alexander van der Grinten
,
Elisabetta Bergamini
,
Oded Green
,
David A. Bader
,
Henning Meyerhenke
PDF
Cite
DOI
A Dynamic Algorithm for Updating Katz Centrality in Graphs
Many large datasets from a variety of fields of research can be represented as graphs. A common query is to identify the most …
Eisha Nathan
,
David A. Bader
PDF
Cite
DOI
Approximating Personalized Katz Centrality in Dynamic Graphs
Dynamic graphs can capture changing relationships in many real datasets that evolve over time. One of the most basic questions about …
Eisha Nathan
,
David A. Bader
PDF
Cite
DOI
Design and implementation of parallel PageRank on multicore platforms
PageRank is a fundamental graph algorithm to evaluate the importance of vertices in a graph. In this paper, we present an efficient …
Shijie Zhou
,
Kartik Lakhotia
,
Shreyas G. Singapura
,
Hanqing Zeng
,
Rajgopal Kannan
,
Viktor K. Prasanna
,
James Fox
,
Euna Kim
,
Oded Green
,
David A. Bader
PDF
Cite
DOI
Exact and Parallel Triangle Counting in Dynamic Graphs
Triangle counting is an important building block for finding key players in a graph. It is an integral part of the popular clustering …
Devavret Makkar
,
David A. Bader
,
Oded Green
PDF
Cite
DOI
Introduction to EMBRACE Workshop
Presents the introductory welcome message from the conference proceedings. May include the conference officers’ congratulations …
David A. Bader
PDF
Cite
DOI
Quickly finding a truss in a haystack
The k-truss of a graph is a subgraph such that each edge is tightly connected to the remaining elements in the k-truss. The k-truss of …
Oded Green
,
James Fox
,
Euna Kim
,
Federico Busato
,
Nicola Bombieri
,
Kartik Lakhotia
,
Shijie Zhou
,
Shreyas G. Singapura
,
Hanqing Zeng
,
Rajgopal Kannan
,
Viktor K. Prasanna
,
David A. Bader
PDF
Cite
DOI
Streaming Graph Sampling with Size Restrictions
Many graph datasets originating from online social network, financial or biological sources are too large to store or analyze. The …
Anita Zakrzewska
,
David A. Bader
PDF
Cite
DOI
When Good Enough Is Better: Energy-Aware Scheduling for Multicore Servers
Power is a primary concern for mobile, cloud, and high-performance computing applications. Approximate computing refers to running …
Xinning Hui
,
Zhihui Du
,
Jason Liu
,
Hongyang Sun
,
Yuxiong He
,
David A. Bader
PDF
Cite
DOI
A local measure of community change in dynamic graphs
In this work we present a new local, vertex-level measure of community change. Our measure detects vertices that change community …
Anita Zakrzewska
,
Eisha Nathan
,
James P. Fairbanks
,
David A. Bader
PDF
Cite
DOI
A Memory and Time Scalable Parallelization of the Reptile Error-Correction Code
This paper details a distributed memory implementation of Reptile, a scalable and accurate spectrum based error-correction method. …
Vipin Sachdeva
,
Srinivas Aluru
,
David A. Bader
PDF
Cite
DOI
Aging data in dynamic graphs: A comparative study
Dynamic graphs are used to represent changing relational data. In order to create a dynamic graph representing relationships or …
Anita Zakrzewska
,
David A. Bader
PDF
Cite
DOI
cuSTINGER: Supporting dynamic graph algorithms for GPUs
cuSTINGER, a new graph data structure targeting NVIDIA GPUs is designed for streaming graphs that evolve over time. cuSTINGER enables …
Oded Green
,
David A. Bader
PDF
Cite
DOI
GABB 2016 Keynote
Emerging real-world graph problems include: detecting community structure in large social networks; improving the resilience of the …
David A. Bader
PDF
Cite
DOI
HiCOMB Introduction and Committees
Provides a listing of current committee members and society officers.
Srinivas Aluru
,
David A. Bader
,
Ananth Kalyanaraman
,
Jaroslaw Zola
PDF
Cite
DOI
Mathematical foundations of the GraphBLAS
The GraphBLAS standard (GraphBlas.org) is being developed to bring the potential of matrix-based graph algorithms to the broadest …
Jeremy Kepner
,
Peter Aaltonen
,
David A. Bader
,
Aydin Buluç
,
Franz Franchetti
,
John R. Gilbert
,
Dylan Hutchison
,
Manoj Kumar
,
Andrew Lumsdaine
,
Henning Meyerhenke
,
Scott McMillan
,
Carl Yang
,
John D. Owens
,
Marcin Zalewski
,
Timothy G. Mattson
,
José E. Moreira
PDF
Cite
DOI
New stopping criteria for spectral partitioning
Spectral partitioning (clustering) algorithms use eigenvectors to solve network analysis problems. The relationship between numerical …
James P. Fairbanks
,
Anita Zakrzewska
,
David A. Bader
PDF
Cite
DOI
Semantic database applications at the Samtavro Cemetery, Georgia
In 2013 a paper was offered to the CAA concerning archaeological legacy data and semantic database applications, with some preliminary …
David Bader
,
Aleksandra Michalewicz
,
Oded Green
,
Jessie Birkett-Rees
,
Jason Riedy
,
James Fairbanks
,
Anita Zakrzewska
PDF
Cite
A Dynamic Algorithm for Local Community Detection in Graphs
A variety of massive datasets, such as social networks and biological data, are represented as graphs that reveal underlying …
Anita Zakrzewska
,
David A. Bader
PDF
Cite
DOI
A fast, energy-efficient abstraction for simultaneous breadth-first searches
Optimized GPU kernels are sufficiently complicated to write that they often are specialized to input data, target architectures, or …
Adam McLaughlin
,
E. Jason Riedy
,
David A. Bader
PDF
Cite
DOI
A Methodology for Co-Location Aware Application Performance Modeling in Multicore Computing
As multicore processor architectures are now prevalent in server nodes of parallel and distributed computing systems, it has become …
Daniel Dauwe
,
Eric Jonardi
,
Ryan Friese
,
Sudeep Pasricha
,
Anthony A. Maciejewski
,
David A. Bader
,
Howard Jay Siegel
PDF
Cite
DOI
Fast Execution of Simultaneous Breadth-First Searches on Sparse Graphs
The construction of efficient parallel graph algorithms is important for quickly solving problems in areas such as urban planning, …
Adam McLaughlin
,
David A. Bader
PDF
Cite
DOI
Fast Incremental Community Detection on Dynamic Graphs
Community detection, or graph clustering, is the problem of finding dense groups in a graph. This is important for a variety of …
Anita Zakrzewska
,
David A. Bader
PDF
Cite
DOI
HiCOMB Introduction and Committees
Provides a listing of current committee members and society officers. The conference also offers a note of thanks and lists its …
Sanguthevar Rajasekaran
,
Srinivas Aluru
,
David A. Bader
PDF
Cite
DOI
Parallel Methods for Verifying the Consistency of Weakly-Ordered Architectures
Contemporary microprocessors use relaxed memory consistency models to allow for aggressive optimizations in hardware. This enhancement …
Adam McLaughlin
,
Duane Merrill
,
Michael Garland
,
David A. Bader
PDF
Cite
DOI
ParLearning Keynotes
Keynote Abstracts
David A. Bader
,
Yihua Huang
,
Ananth Kalyanaraman
PDF
Cite
DOI
A Lin-Kernighan Heuristic for the DCJ Median Problem of Genomes with Unequal Contents
In this paper, we designed a distance metric as DCJ-Indel-Exemplar distance to estimate the dissimilarity between two genomes with …
Zhaoming Yin
,
Jijun Tang
,
Stephen W. Schaeffer
,
David A. Bader
PDF
Cite
DOI
A performance evaluation of open source graph databases
With the proliferation of large, irregular, and sparse relational datasets, new storage and analysis platforms have arisen to fill gaps …
Robert Campbell McColl
,
David Ediger
,
Jason Poovey
,
Dan Campbell
,
David A. Bader
PDF
Cite
DOI
Designing a Heuristic Cross-Architecture Combination for Breadth-First Search
Breadth-First Search (BFS) is widely used in real-world applications including computational biology, social networks, and electronic …
Yang You
,
David A. Bader
,
Maryam Mehri Dehnavi
PDF
Cite
DOI
GABB Introduction
The Basic Linear Algebra Subprograms (BLAS), introduced over 30 years ago, had a transformative effect on linear algebra. By building …
Tim Mattson
,
David A. Bader
,
Aydin Buluç
,
John R. Gilbert
,
Joseph Gonzalez
,
Jeremy Kepner
PDF
Cite
DOI
HiCOMB Introduction and Committees
Provides a listing of current committee members and society officers.
Alba Cristina Magalhaes
,
Alves de Melo
,
Srinivas Aluru
,
David A. Bader
PDF
Cite
DOI
Load balanced clustering coefficients
Clustering coefficients is a building block in network sciences that offers insights on how tightly bound vertices are in a network. …
Oded Green
,
Lluís-Miquel Munguía
,
David A. Bader
PDF
Cite
DOI
Optimizing energy consumption and parallel performance for static and dynamic betweenness centrality using GPUs
Applications of high-performance graph analysis range from computational biology to network security and even transportation. These …
Adam McLaughlin
,
E. Jason Riedy
,
David A. Bader
PDF
Cite
DOI
Revisiting Edge and Node Parallelism for Dynamic GPU Graph Analytics
Betweenness Centrality is a widely used graph analytic that has applications such as finding influential people in social networks, …
Adam McLaughlin
,
David A. Bader
PDF
Cite
DOI
Scalable and High Performance Betweenness Centrality on the GPU (Best Student Paper Finalist)
Graphs that model social networks, numerical simulations, and the structure of the Internet are enormous and cannot be manually …
Adam McLaughlin
,
David A. Bader
PDF
Cite
DOI
A new parallel algorithm for connected components in dynamic graphs
Social networks, communication networks, business intelligence databases, and large scientific data sources now contain hundreds of …
Robert McColl
,
Oded Green
,
David A. Bader
PDF
Cite
DOI
A statistical framework for streaming graph analysis
In this paper we propose a new methodology for gaining insight into the temporal aspects of social networks. In order to develop …
James P. Fairbanks
,
David Ediger
,
Robert McColl
,
David A. Bader
,
Eric Gilbert
PDF
Cite
DOI
Designing Hybrid Architectures for Massive-Scale Graph Analysis
Turning large volumes of data into actionable knowledge is a top challenge in high performance computing. Our previous work in this …
David Ediger
,
David A. Bader
PDF
Cite
DOI
Detecting insider threats in a real corporate database of computer usage activity
This paper reports on methods and results of an applied research project by a team consisting of SAIC and four universities to develop, …
Ted E. Senator
,
Henry G. Goldberg
,
Alex Memory
,
William T. Young
,
Brad Rees
,
Robert Pierce
,
Daniel Huang
,
Matthew Reardon
,
David A. Bader
,
Edmond Chow
,
Irfan A. Essa
,
Joshua Jones
,
Vinay Bettadapura
,
Duen Horng Chau
,
Oded Green
,
Oguz Kaya
,
Anita Zakrzewska
,
Erica Briscoe
,
Rudolph L. Mappus IV
,
Robert McColl
,
Lora Weiss
,
Thomas G. Dietterich
,
Alan Fern
,
Weng-Keen Wong
,
Shubhomoy Das
,
Andrew Emmott
,
Jed Irvine
,
Jay Yoon Lee
,
Danai Koutra
,
Christos Faloutsos
,
Daniel D. Corkill
,
Lisa Friedland
,
Amanda Gentzel
,
David D. Jensen
PDF
Cite
DOI
Energy-Efficient Scheduling for Best-Effort Interactive Services to Achieve High Response Quality
High response quality is critical for many best-effort interactive services, and at the same time, reducing energy consumption can …
Zhihui Du
,
Hongyang Sun
,
Yuxiong He
,
Yu He
,
David A. Bader
,
Huazhe Zhang
PDF
Cite
DOI
Faster Clustering Coefficient Using Vertex Covers
Clustering coefficients, also called triangle counting, is a widely-used graph analytic for measuring the closeness in which vertices …
Oded Green
,
David A. Bader
PDF
Cite
DOI
HiCOMB Introduction
Presents the introductory welcome message from the conference proceedings.
Jaroslaw Zola
,
David A. Bader
,
Srinivas Aluru
PDF
Cite
DOI
Investigating Graph Algorithms in the BSP Model on the Cray XMT
Implementing parallel graph algorithms in large, shared memory machines, such as the Cray XMT, can be challenging for programmers. …
David Ediger
,
David A. Bader
PDF
Cite
DOI
Measuring the Sensitivity of Graph Metrics to Missing Data
The increasing energy consumption of high performance computing has resulted in rising operational and environmental costs. Therefore, …
Anita Zakrzewska
,
David A. Bader
PDF
Cite
DOI
Multithreaded Community Monitoring for Massive Streaming Graph Data
Analyzing static snapshots of massive, graph-structured data cannot keep pace with the growth of social networks, financial …
E. Jason Riedy
,
David A. Bader
PDF
Cite
DOI
Standards for graph algorithm primitives
It is our view that the state of the art in constructing a large collection of graph algorithms in terms of linear algebraic operations …
Tim Mattson
,
David A. Bader
,
Jonathan W. Berry
,
Aydin Buluç
,
Jack J. Dongarra
,
Christos Faloutsos
,
John Feo
,
John R. Gilbert
,
Joseph Gonzalez
,
Bruce Hendrickson
,
Jeremy Kepner
,
Charles E. Leiserson
,
Andrew Lumsdaine
,
David A. Padua
,
Stephen Poole
,
Steven P. Reinhardt
,
Mike Stonebraker
,
Steve Wallach
,
Andrew Yoo
PDF
Cite
DOI
A Fast Algorithm for Streaming Betweenness Centrality
Analysis of social networks is challenging due to the rapid changes of its members and their relationships. For many cases it …
Oded Green
,
Robert McColl
,
David A. Bader
PDF
Cite
DOI
Analysis of streaming social networks and graphs on multicore architectures
Analyzing static snapshots of massive, graph-structured data cannot keep pace with the growth of social networks, financial …
E. Jason Riedy
,
Henning Meyerhenke
,
David A. Bader
,
David Ediger
,
Timothy G. Mattson
PDF
Cite
DOI
Enhancing Cache Coherent Architectures with access patterns for embedded manycore systems
One of the key challenges in advanced micro-architecture is to provide high performance hardware-components that work as application …
Jussara Marandola
,
Stéphane Louise
,
Loïc Cudennec
,
Jean-Thomas Acquaviva
,
David A. Bader
PDF
Cite
DOI
GPU Merge Path: A GPU Merging Algorithm
Graphics Processing Units (GPUs) have become ideal candidates for the development of fine-grain parallel algorithms as the number of …
Oded Green
,
Robert McColl
,
David A. Bader
PDF
Cite
DOI
HCW 2012 Keynote Talk: Analyzing massive data using heterogeneous computing
David A. Bader
PDF
Cite
DOI
HiCOMB Introduction
Presents the introductory welcome message from the conference proceedings.
Mark J. Clement
,
Quinn Snell
,
Srinivas Aluru
,
David A. Bader
PDF
Cite
DOI
Scalable Multi-threaded Community Detection in Social Networks
The volume of existing graph-structured data requires improved parallel tools and algorithms. Finding communities, smaller sub graphs …
E. Jason Riedy
,
David A. Bader
,
Henning Meyerhenke
PDF
Cite
DOI
STINGER: High performance data structure for streaming graphs (Best Paper Award)
The current research focus on “big data” problems highlights the scale and complexity of analytics required and the high rate at which …
David Ediger
,
Robert McColl
,
E. Jason Riedy
,
David A. Bader
PDF
Cite
DOI
Task-based parallel breadth-first search in heterogeneous environments
Breadth-first search (BFS) is an essential graph traversal strategy widely used in many computing applications. Because of its …
Lluís-Miquel Munguía
,
David A. Bader
,
Eduard Ayguadé
PDF
Cite
DOI
A Waterfall Model to Achieve Energy Efficient Tasks Mapping for Large Scale GPU Clusters
High energy consumption has become a critical problem for supercomputer systems. GPU clusters are becoming an increasingly popular …
Wenjie Liu
,
Zhihui Du
,
Yu Xiao
,
David A. Bader
,
Chen Xu
PDF
Cite
DOI
HiCOMB Introduction
Presents the introductory welcome message from the conference proceedings.
Ananth Kalyanaraman
,
Srinivas Aluru
,
David A. Bader
PDF
Cite
DOI
Parallel Community Detection for Massive Graphs
Tackling the current volume of graph-structured data requires parallel tools. We extend our work on analyzing such massive graph data …
E. Jason Riedy
,
Henning Meyerhenke
,
David Ediger
,
David A. Bader
PDF
Cite
DOI
Semantic Databases and Supercomputers
D. Mizell
,
D. A. Bader
,
E. L. Goodman
,
D. J. Haglin
Cite
Tracking Structure of Streaming Social Networks
Current online social networks are massive and still growing. For example, Face book has over 500 million active users sharing over 30 …
David Ediger
,
E. Jason Riedy
,
David A. Bader
,
Henning Meyerhenke
PDF
Cite
DOI
Modularity and Graph Algorithms
A number of graph partitioning algorithms are based on the concept of modularity. In particular Clauset, Newman and Moore (CNM) have …
David A. Bader
,
Joe McCloskey
PDF
Cite
Analyzing Massive Social Networks Using Multicore and Multithreaded Architectures
Emerging real-world graph problems include detecting community structure in large social networks, improving the resilience of the …
David Bader
PDF
Cite
DOI
Evaluating Cell/B.E software cache for ClustalW
This paper evaluates the performance of the bioinformatics application ClustalW developed on Cell Broadband Engine(TM) (Cell/B.E.) …
Vipin Sachdeva
,
Michael Kistler
,
David A. Bader
PDF
Cite
DOI
GPUMemSort: A High Performance Graphic Co-processors Sorting Algorithm for Large Scale In-Memory Data
Yin Ye
,
Zhihui Du
,
David Bader
PDF
Cite
HiCOMB 2010: Message from the workshop chairs
Welcome to the 9th International Workshop on High Performance Computational Biology (HiCOMB). Computational Biology and related …
George Karypis
,
Srinivas Aluru
,
David A. Bader
PDF
Cite
DOI
Large scale complex network analysis using the hybrid combination of a MapReduce cluster and a highly multithreaded system
Complex networks capture interactions among entities in various application areas in a graph representation. Analyzing large scale …
Seunghwa Kang
,
David A. Bader
PDF
Cite
DOI
Massive Social Network Analysis: Mining Twitter for Social Good
Social networks produce an enormous quantity of data. Facebook consists of over 400 million active users sharing over 5 billion pieces …
David Ediger
,
Karl Jiang
,
E. Jason Riedy
,
David A. Bader
,
Courtney Corley
,
Robert M. Farber
,
William N. Reynolds
PDF
Cite
DOI
Massive streaming data analytics: A case study with clustering coefficients
We present a new approach for parallel massive graph analysis of streaming, temporal data with a dynamic and extensible representation. …
David Ediger
,
Karl Jiang
,
E. Jason Riedy
,
David A. Bader
PDF
Cite
DOI
Message from general chair
Welcome to Atlanta, Georgia and to the 24th International Parallel and Distributed Processing Symposium. It has been my honor to spend …
David A. Bader
PDF
Cite
DOI
On accelerating iterative algorithms with CUDA: A case study on Conditional Random Fields training algorithm for biological sequence alignment
The accuracy of Conditional Random Fields (CRF) is achieved at the cost of huge amount of computation to train model. In this paper we …
Zhuhui Du
,
Zhaoming Yin
,
Wenjie Liu
,
David Bader
PDF
Cite
DOI
Scalable Graph Exploration on Multicore Processors
Many important problems in computational sciences, social network analysis, security, and business analytics, are data-intensive and …
Virat Agarwal
,
Fabrizio Petrini
,
Davide Pasetto
,
David A. Bader
PDF
Cite
DOI
A faster parallel algorithm and efficient multithreaded implementations for evaluating betweenness centrality on massive datasets
We present a new lock-free parallel algorithm for computing betweenness centrality of massive complex networks that achieves better …
Kamesh Madduri
,
David Ediger
,
Karl Jiang
,
David A. Bader
,
Daniel G. Chavarría-Miranda
PDF
Cite
DOI
A Partition-Merge Based Cache-Conscious Parallel Sorting Algorithm for CMP with Shared Cache
To explore chip-level parallelism, the PSC (Parallel Shared Cache) model is provided in this paper to describe high performance shared …
Song Hao
,
Zhihui Du
,
David A. Bader
,
Yin Ye
PDF
Cite
DOI
An efficient transactional memory algorithm for computing minimum spanning forest of sparse graphs
Due to power wall, memory wall, and ILP wall, we are facing the end of ever increasing single-threaded performance. For this reason, …
Seunghwa Kang
,
David A. Bader
PDF
Cite
DOI
Compact graph representations and parallel connectivity algorithms for massive dynamic network analysis
Graph-theoretic abstractions are extensively used to analyze massive data sets. Temporal data streams from socio-economic interactions, …
Kamesh Madduri
,
David A. Bader
PDF
Cite
DOI
Faster FAST: Multicore Acceleration of Streaming Financial Data (Best Paper Award)
Virat Agarwal
,
David A. Bader
,
Lin Dan
,
Lurng-Kuo Liu
,
Davide Pasetto
,
Michael Perrone
,
Fabrizio Petrini
PDF
Cite
DOI
Generalizing k-Betweenness Centrality Using Short Paths and a Parallel Multithreaded Implementation
We present a new parallel algorithm that extends and generalizes the traditional graph analysis metric of betweenness centrality to …
Karl Jiang
,
David Ediger
,
David A. Bader
PDF
Cite
DOI
GTfold: a scalable multicore code for RNA secondary structure prediction
The prediction of the correct secondary structures of large RNAs is one of the unsolved challenges of computational molecular biology. …
Amrita Mathuriya
,
David A. Bader
,
Christine E. Heitsch
,
Stephen C. Harvey
PDF
Cite
DOI
Simulating Individual-Based Models of Epidemics in Hierarchical Networks
Current mathematical modeling methods for the spreading of infectious diseases are too simplified and do not scale well. We present the …
Rick Quax
,
David A. Bader
,
Peter M. A. Sloot
PDF
Cite
DOI
Understanding the design trade-offs among current multicore systems for numerical computations
In this paper, we empirically evaluate fundamental design trade-offs among the most recent multicore processors and accelerator …
Seunghwa Kang
,
David A. Bader
,
Richard W. Vuduc
PDF
Cite
DOI
A Prediction Based CMP Cache Migration Policy
The large L2 cache’s access latency, which is mainly caused by wire delay, is a critical problem to improve the performance of …
Song Hao
,
Zhihui Du
,
David A. Bader
,
Man Wang
PDF
Cite
DOI
DOSA: design optimizer for scientific applications
In this paper we briefly introduce our new framework, called “design optimizer for scientific applications” (DOSA) which …
David A. Bader
,
Viktor K. Prasanna
PDF
Cite
DOI
Financial modeling on the Cell Broadband Engine
High performance computing is critical for financial markets where analysts seek to accelerate complex optimizations such as pricing …
Virat Agarwal
,
Lurng-Kuo Liu
,
David A. Bader
PDF
Cite
DOI
High performance MPEG-2 software decoder on the Cell Broadband Engine
The Sony-Toshiba-IBM Cell Broadband Engine is a heterogeneous multicore architecture that consists of a traditional microprocessor …
David A. Bader
,
Sulabh Patel
PDF
Cite
DOI
On the Design of Fast Pseudo-Random Number Generators for the Cell Broadband Engine and an Application to Risk Analysis
Numerical simulations in computational physics, biology, and finance, often require the use of high quality and efficient parallel …
David A. Bader
,
Aparna Chandramowlishwaran
,
Virat Agarwal
PDF
Cite
DOI
Optimizing JPEG2000 Still Image Encoding on the Cell Broadband Engine
JPEG2000 is the latest still image coding standard from the JPEG committee, which adopts new algorithms such as embedded block coding …
Seunghwa Kang
,
David A. Bader
PDF
Cite
DOI
Petascale Computing for Large-Scale Graph Problems
Graph theoretic problems are representative of fundamental kernels in traditional and emerging computational sciences such as …
David A. Bader
PDF
Cite
DOI
SNAP, Small-world Network Analysis and Partitioning: An open-source parallel graph framework for the exploration of large-scale networks
We present SNAP (small-world network analysis and partitioning), an open-source graph framework for exploratory study and partitioning …
David A. Bader
,
Kamesh Madduri
PDF
Cite
DOI
Lecture on Progress toward Petascale Applications in Bioinformatics and Computational Biology
Over the past several years there have been repeated analyses of the potential value of petascale bioinformatics and computational …
C. A. Stewart
,
M. Lingwall
,
D. Bader
PDF
Cite
DOI
A Graph-Theoretic Analysis of the Human Protein-Interaction Network Using Multicore Parallel Algorithms
Protein-interaction network (PIN) analysis provides valuable insight into an organism’s functional organization and evolutionary …
David A. Bader
,
Kamesh Madduri
PDF
Cite
DOI
Advanced Shortest Paths Algorithms on a Massively-Multithreaded Architecture
We present a study of multithreaded implementations of Thorup’s algorithm for solving the single source shortest path (SSSP) …
Joseph R. Crobak
,
Jonathan W. Berry
,
Kamesh Madduri
,
David A. Bader
PDF
Cite
DOI
An Experimental Study of A Parallel Shortest Path Algorithm for Solving Large-Scale Graph Instances
We present an experimental study of the single source shortest path problem with non-negative edge weights (NSSP) on large-scale graphs …
Kamesh Madduri
,
David A. Bader
,
Jonathan W. Berry
,
Joseph R. Crobak
PDF
Cite
DOI
Approximating Betweenness Centrality
Betweenness is a centrality measure based on shortest paths, widely used in complex network analysis. It is computationally-expensive …
David A. Bader
,
Shiva Kintali
,
Kamesh Madduri
,
Milena Mihail
PDF
Cite
DOI
DOSA: Design Optimizer for Scientific Applications
In this work, we propose an application composition system (ACS) that allows design-time exploration and automatic run-time …
David A. Bader
,
Viktor K. Prasanna
PDF
Cite
DOI
FFTC: Fastest Fourier Transform for the IBM Cell Broadband Engine
The Fast Fourier Transform (FFT) is of primary importance and a fundamental kernel in many computationally intensive scientific …
David A. Bader
,
Virat Agarwal
PDF
Cite
DOI
High-Performance Combinatorial Techniques for Analyzing Massive Dynamic Interaction Networks
Graph-theoretic abstractions are extensively used to analyze massive data sets. Temporal data streams from socio-economic interactions, …
David A. Bader
,
K. Madduri
PDF
Cite
On the Design and Analysis of Irregular Algorithms on the Cell Processor: A Case Study of List Ranking
The Sony-Toshiba-IBM Cell Broadband Engine is a heterogeneous multicore architecture that consists of a traditional microprocessor …
David A. Bader
,
Virat Agarwal
,
Kamesh Madduri
PDF
Cite
DOI
Petascale Computing for Large-Scale Graph Problems
Graph theoretic problems are representative of fundamental kernels in traditional and emerging computational sciences such as …
David A. Bader
PDF
Cite
DOI
Petascale Computing for Large-Scale Graph Problems (Abstract)
Graph theoretic problems are representative of fundamental kernels in traditional and emerging computational sciences such as …
David A. Bader
PDF
Cite
DOI
SWARM: A Parallel Programming Framework for Multicore Processors
Due to fundamental physical limitations and power constraints, we are witnessing a radical change in commodity microprocessor …
David A. Bader
,
Varun Kanade
,
Kamesh Madduri
PDF
Cite
DOI
Symposium Evening Tutorial: High-performance Computing Methods for Computational Genomics
Srinivas Aluru
,
David A. Bader
,
Anantharaman Kalyanaraman
PDF
Cite
DOI
Techniques for Designing Efficient Parallel Graph Algorithms for SMPs and Multicore Processors
Graph problems are finding increasing applications in high performance computing disciplines. Although many regular problems can be …
Guojing Cong
,
David A. Bader
PDF
Cite
DOI
Designing Multithreaded Algorithms for Breadth-First Search and st-connectivity on the Cray MTA-2
Graph abstractions are extensively used to understand and solve challenging computational problems in various scientific and …
David A. Bader
,
Kamesh Madduri
PDF
Cite
DOI
Efficient Implementation of Irregular Algorithms on Cell Multi-core Architecture. Poster Session
David A. Bader
,
V. Agarwal
,
K. Madduri
Cite
ExactMP: An Efficient Parallel Exact Solver for Phylogenetic Tree Reconstruction Using Maximum Parsimony
Constructing phylogenetic trees in the study of the evolutionary history of a group organisms is an extremely challenging problem in …
David A. Bader
,
Vaddadi P. Chandu
,
Mi Yan
PDF
Cite
DOI
High-performance computing methods for computational genomics
The high computational requirements of several applications in computational genomics are aggravated by an exponential growth in …
Srinivas Aluru
,
David A. Bader
,
Anantharaman Kalyanaraman
PDF
Cite
DOI
Parallel Algorithms for Evaluating Centrality Indices in Real-world Networks
This paper discusses fast parallel algorithms for evaluating several centrality indices frequently used in complex network analysis. …
David A. Bader
,
Kamesh Madduri
PDF
Cite
DOI
Parallel Shortest Path Algorithms for Solving Large-Scale Instances
We present an experimental study of parallel algorithms for solving the single source shortest path problem with non-negative edge …
Kamesh Madduri
,
David A. Bader
,
Jonathan W. Berry
,
Joseph R. Crobak
PDF
Cite
DOI
Performance analysis of parallel programs via message-passing graph traversal
The ability to understand the factors contributing to parallel program performance are vital for understanding the impact of machine …
Matthew J. Sottile
,
Vaddadi P. Chandu
,
David A. Bader
PDF
Cite
DOI
A Cache-Aware Parallel Implementation of the Push-Relabel Network Flow Algorithm and Experimental Evaluation of the Gap Relabeling Heuristic
The maximum flow problem is a combinatorial problem of significant importance in a wide variety of research and commercial …
David A. Bader
,
Vipin Sachdeva
PDF
Cite
An Empirical Analysis of Parallel Random Permutation Algorithms on SMPs
We compare parallel algorithms for random permutation generation on symmetric multiprocessors (SMPs). Algorithms considered are the …
Guojing Cong
,
David A. Bader
PDF
Cite
An Experimental Study of Parallel Biconnected Components Algorithms on Symmetric Multiprocessors (SMPs)
We present an experimental study of parallel biconnected components algorithms employing several fundamental parallel primitives, e.g., …
Guojing Cong
,
David A. Bader
PDF
Cite
DOI
BioPerf: a benchmark suite to evaluate high-performance computer architecture on bioinformatics applications
The exponential growth in the amount of genomic data has spurred growing interest in large scale analysis of genetic information. …
David A. Bader
,
Yue Li
,
Tao Li
,
Vipin Sachdeva
PDF
Cite
DOI
BioSPLASH: A sample workload from bioinformatics and computational biology for optimizing next-generation high-performance computer systems. Poster Session
David A. Bader
,
V. Sachdeva
,
A. Trehan
,
V. Agarwal
,
G. Gupta
,
A. N. Singh
PDF
Cite
Design and Implementation of the HPCS Graph Analysis Benchmark on Symmetric Multiprocessors (HiPC Most Impactful Papers Award)
Graph theoretic problems are representative of fundamental computations in traditional and emerging scientific disciplines like …
David A. Bader
,
Kamesh Madduri
PDF
Cite
DOI
High-Performance Algorithm Engineering for Large-Scale Graph Problems and Computational Biology
Many large-scale optimization problems rely on graph theoretic solutions; yet high-performance computing has traditionally focused on …
David A. Bader
PDF
Cite
DOI
Incorporating life sciences applications in the architectural optimizations of next-generation petaflop-system
Advances in experimental techniques have transformed biology into a data-intensive science, with a rapid explosion of data at the …
David A. Bader
,
Vipin Sachdeva
PDF
Cite
DOI
On the Architectural Requirements for Efficient Execution of Graph Algorithms
Combinatorial problems such as those from graph theory pose serious challenges for parallel machines due to non-contiguous, concurrent …
David A. Bader
,
Guojing Cong
,
John Feo
PDF
Cite
DOI
A Fast, Parallel Spanning Tree Algorithm for Symmetric Multiprocessors (SMPs)
We focus on implementing parallel spanning tree algorithms on SMPs. Spanning tree is an important problem in the sense that it is the …
David A. Bader
,
Guojing Cong
PDF
Cite
DOI
A Novel FDTD Application Featuring OpenMP-MPI Hybrid Parallelization
We have developed a high performance hybridized parallel finite difference time domain (FDTD) algorithm featuring both OpenMP shared …
Mehmet F. Su
,
Ihab El-Kady
,
David A. Bader
,
Shawn-Yu Lin
PDF
Cite
DOI
A Parallel State Assignment Algorithm for Finite State Machines
This paper summarizes the design and implementation of a parallel algorithm for state assignment of large Finite State Machines (FSMs). …
David A. Bader
,
Kamesh Madduri
PDF
Cite
DOI
Fast Shared-Memory Algorithms for Computing the Minimum Spanning Forest of Sparse Graphs
Minimum spanning tree (MST) is one of the most studied combinatorial problems with practical applications in VLSI layout, wireless …
David A. Bader
,
Guojing Cong
PDF
Cite
DOI
High Performance Bioinformatics
Bioinformatics is the science of managing, mining, and interpreting information from biological sequences and structures. Genome …
Mohammed Javeed Zaki
,
David A. Bader
,
Johan Montagnat
,
Concettina Guerra
PDF
Cite
DOI
Lock-Free Parallel Algorithms: An Experimental Study
Lock-free shared data structures in the setting of distributed computing have received a fair amount of attention. Major motivations of …
Guojing Cong
,
David A. Bader
PDF
Cite
DOI
The Euler Tour Technique and Parallel Rooted Spanning Tree
Many parallel algorithms for graph problems start with finding a spanning tree and rooting the tree to define some structural …
Guojing Cong
,
David A. Bader
PDF
Cite
DOI
Broadcast on Clusters of SMPs with Optimal Concurrency
Yuzhong Sun
,
David A. Bader
,
Xiaola Lin
,
Yibei Ling
PDF
Cite
Evaluating Arithmetic Expressions Using Tree Contraction: A Fast and Scalable Parallel Implementation for Symmetric Multiprocessors (SMPs)
The ability to provide uniform shared-memory access to a significant number of processors in a single SMP node brings us much closer to …
David A. Bader
,
Sukanya Sreshta
,
Nina R. Weisse-Bernstein
PDF
Cite
DOI
HiCOMB 2002: Workshop Introduction
David A. Bader
,
Srinivas Aluru
PDF
Cite
DOI
New approaches for using gene order data in phylogeny reconstruction
The rapid accumulation of whole genome sequences for a wide diversity of taxa is generating a huge amount of comparative data for …
Robert K. Jansen
,
David Bader
,
Bernard M.E. Moret
,
Linda A. Raubeson
,
Li-San Wang
,
Tandy Warnow
,
Stacia Wyman
PDF
Cite
A Linear-Time Algorithm for Computing Inversion Distance between Signed Permutations with an Experimental Study
Hannenhalli and Pevzner gave the first polynomial-time algorithm for computing the inversion distance between two signed permutations, …
David A. Bader
,
Bernard M. E. Moret
,
Mi Yan
PDF
Cite
DOI
A New Implmentation and Detailed Study of Breakpoint Analysis
Phylogenies derived from gene order data may prove crucial in answering some fundamental open questions in biomolecular evolution. Yet …
Bernard M. E. Moret
,
Stacia K. Wyman
,
David A. Bader
,
Tandy J. Warnow
,
Mi Yan
PDF
Cite
High-Performance Algorithm Engineering for Computational Phylogenetics
Phylogeny reconstruction from molecular data poses complex optimization problems: almost all optimization models are NP-hard and thus …
Bernard M. E. Moret
,
David A. Bader
,
Tandy J. Warnow
PDF
Cite
DOI
Industrial applications of high-performance computing for phylogeny reconstruction
Phylogenies (that is, tree-of-life relationships) derived from gene order data may prove crucial in answering some fundamental open …
David A. Bader
,
Bernard M. E. Moret
,
Lisa Vawter
PDF
Cite
DOI
Using PRAM Algorithms on a Uniform-Memory-Access Shared-Memory Architecture
The ability to provide uniform shared-memory access to a significant number of processors in a single SMP node brings us much closer to …
David A. Bader
,
Ajith K. Illendula
,
Bernard M. E. Moret
,
Nina R. Weisse-Bernstein
PDF
Cite
DOI
Variation in vegetation growth rates: Implications for the evolution of semi-arid landscapes
C. Restrepo
,
B. T. Milne
,
D. Bader
,
W. Pockman
,
A. Kerkhoff
Cite
An Improved Randomized Selection Algorithm With an Experimental Study
David A. Bader
PDF
Cite
High-Performance Algorithms and Applications for SMP Clusters
The future of high-performance computing relies on the efficient and scalable use of clusters with symmetric multiprocessor (SMP) nodes …
David A. Bader
PDF
Cite
Tutorial A: Design and Analysis of High Performance Clusters
Rob Pennington
,
David A. Bader
,
Barney Maccabe
,
Patricia A. Kovatch
,
Stephen L. Scott
PDF
Cite
DOI
A hierarchical data archiving and processing system to generate custom tailored products from AVHRR data
A novel indexing scheme is described to catalogue satellite data on a pixel basis. The objective of this research is to develop an …
S. N. V. Kalluri
,
Z. Zhang
,
J. Jaja
,
D. A. Bader
,
H. Song
,
N. El Saleous
,
E. Vermote
,
J. R. G. Townshend
PDF
Cite
DOI
Design and Analysis of the Alliance/University of New Mexico Roadrunner Linux SMP SuperCluster
This paper discusses high performance clustering from a series of critical topics: architectural design, system software …
David A. Bader
,
Arthur B. Maccabe
,
Jason R. Mastaler
,
John K. McIver III
,
Patricia A. Kovatch
PDF
Cite
DOI
Parallel Algorithms for Image Enhancement and Segmentation by Region Growing with an Experimental Study
Presents efficient and portable implementations of a useful image enhancement process, the symmetric neighborhood filter (SNF), and an …
David A. Bader
,
Joseph JáJá
,
David Harwood
,
Larry S. Davis
PDF
Cite
DOI
Parallel Algorithms for Personalized Communication and Sorting with an Experimental Study (Extended Abstract)
A fundamental challenge for parallel computing is to obtain high-level, architecture independent, algorithms which execute efficiently …
David R. Helman
,
David A. Bader
,
Joseph JáJá
PDF
Cite
DOI
Practical Parallel Algorithms for Dynamic Data Redistribution, Median Finding, and Selection
A common statistical problem is that of finding the median element in a set of data. This paper presents a fast and portable parallel …
David A. Bader
,
Joseph JáJá
PDF
Cite
DOI
Parallel Algorithms for Image Histogramming and Connected Components with an Experimental Study
This paper presents efficient and portable implementations of two useful primitives in image processing algorithms, histogramming and …
David A. Bader
,
Joseph JáJá
PDF
Cite
DOI
Cite
×