David A. Bader
David A. Bader
Home
People
Posts
Projects
Books
Publications
Talks
Contact
CV
Light
Dark
Automatic
2
A Simple and Efficient Algorithm for Finding Minimum Spanning Tree Replacement Edges
Given an undirected, weighted graph, the minimum spanning tree (MST)is a tree that connects all of the vertices of the graph with …
David Bader
,
Paul Burkhardt
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 Bader
,
Henning Meyerhenke
PDF
Cite
DOI
Anomaly Detection in Catalog Streams
Detecting anomalies with high accuracy and real time from large amounts of streaming data is a challenge for many real-world …
Chen Yang
,
Zhihui Du
,
Xiaofeng Meng
,
Xukang Zhang
,
Xinli Hao
,
David Bader
PDF
Cite
DOI
Dynamics signature based anomaly detection
Identifying anomalies, especially weak anomalies in constantly changing targets, is more difficult than in stable targets. In this …
Ivan Hendy Goenawan
,
Zhihui Du
,
Chao Wu
,
Yankui Sun
,
Jianyan Wei
,
David Bader
PDF
Cite
DOI
Linux and Supercomputing: How my passion for building COTS systems led to an HPC revolution
David A. Bader built the first Linux Supercomputer.
David Bader
PDF
Cite
DOI
Interactive Graph Stream Analytics in Arkouda
Data from emerging applications, such as cybersecurity and social networking, can be abstracted as graphs whose edges are updated …
Zhihui Du
,
Oliver Alvarado Rodriguez
,
Joseph Patchett
,
David Bader
PDF
Cite
DOI
Traversing Large Graphs on GPUs with Unified Memory
Due to the limited capacity of GPU memory, the majority of prior work on graph applications on GPUs has been restricted to graphs of …
Prasun Gera
,
Hyojong Kim
,
Piyush Sao
,
Hyesoon Kim
,
David Bader
PDF
Cite
DOI
Editorial from the Editor-in-Chief
David A. Bader
PDF
Cite
DOI
Tailoring parallel alternating criteria search for domain specific MIPs: Application to maritime inventory routing
Parallel Alternating Criteria Search (PACS) relies on the combination of computer parallelism and Large Neighborhood Searches to …
Lluís-Miquel Munguía
,
Shabbir Ahmed
,
David A. Bader
,
George L. Nemhauser
,
Yufen Shao
,
Dimitri J. Papageorgiou
PDF
Cite
DOI
Accelerating GPU betweenness centrality
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
Alternating criteria search: a parallel large neighborhood search algorithm for mixed integer programs
We present a parallel large neighborhood search framework for finding high quality primal solutions for general mixed-integer programs …
Lluís-Miquel Munguía
,
Shabbir Ahmed
,
David A. Bader
,
George L. Nemhauser
,
Yufen Shao
PDF
Cite
DOI
Incrementally updating Katz centrality in dynamic graphs
A variety of large datasets, such as social networks or biological data, can be represented as graphs. A common query in graph analysis …
Eisha Nathan
,
David A. Bader
PDF
Cite
DOI
Numerically approximating centrality for graph ranking guarantees
Many real-world datasets can be represented as graphs. Using iterative solvers to approximate graph centrality measures allows us to …
Eisha Nathan
,
Geoffrey Sanders
,
Van Emden Henson
,
David A. Bader
PDF
Cite
DOI
A parallel local search framework for the Fixed-Charge Multicommodity Network Flow problem
We present a parallel local search approach for obtaining high quality solutions to the Fixed Charge Multicommodity Network Flow …
Lluís-Miquel Munguía
,
Shabbir Ahmed
,
David A. Bader
,
George L. Nemhauser
,
Vikas Goel
,
Yufen Shao
PDF
Cite
DOI
Designing and implementing a heuristic cross-architecture combination for graph traversal
Breadth-First Search (BFS) is widely used in real-world applications including computational biology, social networks, and electronic …
Yang You
,
Haohuan Fu
,
David A. Bader
,
Guangwen Yang
PDF
Cite
DOI
Editor's Note
Presents the introductory editorial for this issue of the publication.
David A. Bader
PDF
Cite
DOI
Editor's Note
Presents the introductory editorial for this issue of the publication.
David A. Bader
PDF
Cite
DOI
Exemplar or Matching: Modeling DCJ Problems with Unequal Content Genome Data
The edit distance under the DCJ model can be computed in linear time for genomes with equal content or with Indels. But it becomes …
Zhaoming Yin
,
Jijun Tang
,
Stephen W. Schaeffer
,
David A. Bader
PDF
Cite
Graph Ranking Guarantees for Numerical Approximations to Katz Centrality
Graphs and networks are prevalent in modeling relational datasets from many fields of research. By using iterative solvers to …
Eisha Nathan
,
Geoffrey Sanders
,
James Fairbanks
,
Van Emden Henson
,
David A. Bader
PDF
Cite
DOI
Local Community Detection in Dynamic Graphs Using Personalized Centrality
Analyzing massive graphs poses challenges due to the vast amount of data available. Extracting smaller relevant subgraphs allows for …
Eisha Nathan
,
Anita Zakrzewska
,
E. Jason Riedy
,
David A. Bader
PDF
Cite
DOI
Modeling the Power Variability of Core Speed Scaling on Homogeneous Multicore Systems
We describe a family of power models that can capture the nonuniform power effects of speed scaling among homogeneous cores on …
Zhihui Du
,
Rong Ge
,
Victor W. Lee
,
Richard W. Vuduc
,
David A. Bader
,
Ligang He
PDF
Cite
DOI
Spectral partitioning with blends of eigenvectors
Many common methods for data analysis rely on linear algebra. We provide new results connecting data analysis error to numerical …
James P. Fairbanks
,
David A. Bader
,
Geoffrey D. Sanders
PDF
Cite
DOI
A New Parallel Method for Binary Black Hole Simulations
Simulating binary black hole (BBH) systems are a computationally intensive problem and it can lead to great scientific discovery. How …
Quan Yang
,
Zhihui Du
,
Zhou-Jian Cao
,
Jian Tao
,
David A. Bader
PDF
Cite
DOI
Editor's Note
Welcome to this year’s first issue of IEEE Transactions on Parallel and Distributed Systems (TPDS). The author is privileged to …
David A. Bader
PDF
Cite
DOI
Evolving MPI+X Toward Exascale
This installment of Computer’s series highlighting the work published in IEEE Computer Society journals comes from IEEE …
David A. Bader
PDF
Cite
DOI
Exemplar or matching: modeling DCJ problems with unequal content genome data
The edit distance under the DCJ model can be computed in linear time for genomes with equal content or with Indels. But it becomes …
Zhaoming Yin
,
Jijun Tang
,
Stephen W. Schaeffer
,
David A. Bader
PDF
Cite
DOI
HPC node performance and energy modeling with the co-location of applications
Multicore processors have become an integral part of modern large-scale and high-performance parallel and distributed computing …
Daniel Dauwe
,
Eric Jonardi
,
Ryan Friese
,
Sudeep Pasricha
,
Anthony A. Maciejewski
,
David A. Bader
,
Howard Jay Siegel
PDF
Cite
DOI
Tracking local communities in streaming graphs with a dynamic algorithm
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
Behavioral clusters in dynamic graphs
This paper contributes a method for combining sparse parallel graph algorithms with dense parallel linear algebra algorithms in order …
James P. Fairbanks
,
Ramakrishnan Kannan
,
Haesun Park
,
David A. Bader
PDF
Cite
DOI
Editor's Note
Presents the introductory editorial for this issue of the publication
David A. Bader
PDF
Cite
DOI
Graphs, Matrices, and the GraphBLAS: Seven Good Reasons
The analysis of graphs has become increasingly important to a wide range of applications. Graph analysis presents a number of unique …
Jeremy Kepner
,
David Bader
,
Aydın Buluç
,
John Gilbert
,
Timothy Mattson
,
Henning Meyerhenke
PDF
Cite
DOI
Spectral Partitioning with Blends of Eigenvectors
Many common methods for data analysis rely on linear algebra. We provide new results connecting data analysis error to numerical …
James P. Fairbanks
,
Geoffrey D. Sanders
,
David A. Bader
PDF
Cite
State of the Journal
Reports on the current state of the IEEE Transactions on Computers.
David A. Bader
PDF
Cite
DOI
WEC: Improving Durability of SSD Cache Drives by Caching Write-Efficient Data
Serving as cache disks, flash-based solid-state drives (SSDs) can significantly boost the performance of read-intensive applications. …
Yunpeng Chai
,
Zhihui Du
,
Xiao Qin
,
David A. Bader
PDF
Cite
DOI
Introduction to Special Issue ALENEX'12
David A. Bader
,
Petra Mutzel
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 …
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 W. Poole
,
Steven P. Reinhardt
,
Mike Stonebraker
,
Steve Wallach
,
Andrew Yoo
PDF
Cite
State of the Journal
I am excited with my new role as incoming Editor-in-Chief (EiC) of IEEE Transactions on Parallel and Distributed Systems (TPDS) and …
David A. Bader
PDF
Cite
DOI
A Brief Study of Open Source Graph Databases
With the proliferation of large irregular sparse relational datasets, new storage and analysis platforms have arisen to fill gaps in …
Robert McColl
,
David Ediger
,
Jason Poovey
,
Dan Campbell
,
David A. Bader
PDF
Cite
Faster Betweenness Centrality Based on Data Structure Experimentation
Betweenness centrality is a graph analytic that states the importance of a vertex based on the number of shortest paths that it is on. …
Oded Green
,
David A. Bader
PDF
Cite
DOI
GraphCT: Multithreaded Algorithms for Massive Graph Analysis
The digital world has given rise to massive quantities of data that include rich semantic and complex networks. A social graph, for …
David Ediger
,
Karl Jiang
,
E. Jason Riedy
,
David A. Bader
PDF
Cite
DOI
Massive streaming data analytics: a graph-based approach
E. Jason Riedy
,
David A. Bader
PDF
Cite
DOI
PASQUAL: Parallel Techniques for Next Generation Genome Sequence Assembly
The study of genomes has been revolutionized by sequencing machines that output many short overlapping substrings (called reads). The …
Xing Liu
,
Pushkar R. Pande
,
Henning Meyerhenke
,
David A. Bader
PDF
Cite
DOI
Streaming Breakpoint Graph Analytics for Accelerating and Parallelizing the Computation of DCJ Median of Three Genomes
The problem of finding the median of three genomes is the key process in building the most parsimonious phylogenetic trees from genome …
Zhaoming Yin
,
Jijun Tang
,
Stephen W. Schaeffer
,
David A. Bader
PDF
Cite
DOI
Sustainable Software Development for Next-Gen Sequencing (NGS) Bioinformatics on Emerging Platforms
DNA sequence analysis is fundamental to life science research. The rapid development of next generation sequencing (NGS) technologies, …
Shel Swenson
,
Yogesh Simmhan
,
Viktor K. Prasanna
,
Manish Parashar
,
E. Jason Riedy
,
David A. Bader
,
Richard W. Vuduc
PDF
Cite
ACM journal on experimental algorithmics special issue on multicore algorithms
The recent switch to multicore processors brought a dramatic change that affects a large spectrum of systems from embedded and …
David A. Bader
,
Philippas Tsigas
PDF
Cite
DOI
Efficient Data Migration to Conserve Energy in Streaming Media Storage Systems
Reducing energy consumption has been an important design issue for large-scale streaming media storage systems. Existing energy …
Yunpeng Chai
,
Zhihui Du
,
David A. Bader
,
Xiao Qin
PDF
Cite
DOI
GTfold: Enabling parallel RNA secondary structure prediction on multi-core desktops
Background Accurate and efficient RNA secondary structure prediction remains an important open problem in computational molecular …
M. Shel Swenson
,
Joshua Anderson
,
Andrew Ash
,
Prashant Gaurav
,
Zsuzsanna Sükösd
,
David A. Bader
,
Stephen C. Harvey
,
Christine E. Heitsch
PDF
Cite
DOI
Rec-DCM-Eigen: Reconstructing a Less Parsimonious but More Accurate Tree in Shorter Time
Maximum parsimony (MP) methods aim to reconstruct the phylogeny of extant species by finding the most parsimonious evolutionary …
Seunghwa Kang
,
Jijun Tang
,
Stephen W. Schaeffer
,
David A. Bader
PDF
Cite
DOI
Algorithm Engineering Challenges in Multicore and Manycore Systems
Modern multicore and manycore systems have the strong potential to deliver both high performance and high power efficiency. The large …
Seunghwa Kang
,
David Ediger
,
David A. Bader
PDF
Cite
DOI
GPUMemSort: A High Performance Graphic Co-processors Sorting Algorithm for Large Scale In-Memory Data
In this paper, we present a GPU-based sorting algorithm, GPUMemSort, which achieves high performance in sorting large-scale in-memory …
Yin Ye
,
Zhihui Du
,
David A. Bader
PDF
Cite
DOI
Guest Editor's Introduction: Special Issue on High-Performance Computing with Accelerators
The 12 papers in this special issue on high-performance computing with accelerators discuss a range of different accelerator …
David A. Bader
,
David R. Kaeli
,
Volodymyr V. Kindratenko
PDF
Cite
DOI
On the random access performance of Cell Broadband Engine with graph analysis application
The Cell Broad Engine (BE) Processor has unique memory access architecture besides its powerful computing engines. Many …
Mingyu Chen
,
David A. Bader
PDF
Cite
Computing discrete transforms on the Cell Broadband Engine
Discrete transforms are of primary importance and fundamental kernels in many computationally intensive scientific applications. In …
David A. Bader
,
Virat Agarwal
,
Seunghwa Kang
PDF
Cite
DOI
Faster FAST: multicore acceleration of streaming financial data
By 2010, the global options and equity markets will average over 128 billion messages per day, amounting to trillions of dollars in …
Virat Agarwal
,
David A. Bader
,
Lin Dan
,
Lurng-Kuo Liu
,
Davide Pasetto
,
Michael Perrone
,
Fabrizio Petrini
PDF
Cite
DOI
A graph-theoretic analysis of the human protein-interaction network using multicore parallel algorithms
Due to fundamental physical limitations and power constraints, we are witnessing a paradigm shift in commodity microprocessor …
David A. Bader
,
Kamesh Madduri
PDF
Cite
DOI
Guest editorial: High-performance computational biology
David A. Bader
,
Srinivas Aluru
PDF
Cite
DOI
Dynamic Load Balancing in Distributed Systems in the Presence of Delays: A Regeneration-Theory Approach
A regeneration-theory approach is undertaken to analytically characterize the average overall completion time in a distributed system. …
Sagar Dhakal
,
Majeed M. Hayat
,
Jorge E. Pezoa
,
Cundong Yang
,
David A. Bader
PDF
Cite
DOI
High performance combinatorial algorithm design on the Cell Broadband Engine processor
The Sony–Toshiba–IBM Cell Broadband Engine (Cell/B.E.) is a heterogeneous multicore architecture that consists of a traditional …
David A. Bader
,
Virat Agarwal
,
Kamesh Madduri
,
Seunghwa Kang
PDF
Cite
DOI
On the design of high-performance algorithms for aligning multiple protein sequences on mesh-based multiprocessor architectures
In this paper, we address the problem of multiple sequence alignment (MSA) for handling very large number of proteins sequences on …
Diana H. P. Low
,
Bharadwaj Veeravalli
,
David A. Bader
PDF
Cite
DOI
Computational Grand Challenges in Assembling the Tree of Life: Problems and Solutions
The computation of ever larger as well as more accurate phylogenetic (evolutionary) trees with the ultimate goal to compute the tree of …
David A. Bader
,
Usman Roshan
,
Alexandros Stamatakis
PDF
Cite
DOI
Designing irregular parallel algorithms with mutual exclusion and lock-free protocols
Irregular parallel algorithms pose a significant challenge for achieving high performance because of the difficulty predicting memory …
Guojing Cong
,
David A. Bader
PDF
Cite
DOI
Designing Scalable Synthetic Compact Applications for Benchmarking High Productivity Computing Systems
One of the main objectives of the DARPA High Productivity Computing Systems (HPCS) program is to reassess the way we define and measure …
D. A. Bader
,
K. Madduri
,
J. R. Gilbert
,
V. Shah
,
J. Kepner
,
T. Meuse
,
A. Krishnamurthy
PDF
Cite
Editorial: Special Section on High-Performance Computational Biology
Srinivas Aluru
,
Nancy M. Amato
,
David A. Bader
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
A fast, parallel spanning tree algorithm 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
,
Guojing Cong
PDF
Cite
DOI
A Framework for Measuring Supercomputer Productivity
We propose a framework for measuring the productivity of high performance computing (HPC) systems, based on common economic definitions …
Marc Snir
,
David A. Bader
PDF
Cite
DOI
An improved, randomized algorithm for parallel selection with an experimental study
A common statistical problem is that of finding the median element in a set of data. This paper presents an efficient randomized …
David A. Bader
PDF
Cite
DOI
Computational biology and high-performance computing
Understanding evolution and the basic structure and function of proteins are two grand challenge problems in biology that can be solved …
David A. Bader
PDF
Cite
DOI
Special Issue: High Performance Computational Biology
David A. Bader
,
Srinivas Aluru
PDF
Cite
DOI
Guest Editor's Introduction: Special issue on high-performance computational biology
Srinivas Aluru is an associate professor and Associate Chair for Graduate Education in the Department of Electrical and Computer …
Srinivas Aluru
,
David A. Bader
PDF
Cite
DOI
Generalized block shift network for clusters
In this work, a generalized topology of block shift networks (BSNs), named generalized block shift network (GBSN), is propose or …
Yuzhong Sun
,
Xiaola Lin
,
Yi Pan
,
R. W. H. Lau
,
D. A. Bader
,
P. Y. S. Cheung
PDF
Cite
DOI
High-Performance Algorithm Engineering for Computational Phylogenetics
A phylogeny is the evolutionary history of a group of organisms; systematists (and other biologists) attempt to reconstruct this …
Bernard M. E. Moret
,
David A. Bader
,
Tandy J. Warnow
PDF
Cite
DOI
A Linear-Time Algorithm for Computing Inversion Distance Between Two 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
Applications
David A. Bader
,
Rob Pennington
PDF
Cite
DOI
High performance computing algorithms for land cover dynamics using remote sensing data
Global and regional land cover studies need to apply complex models on selected subsets of large volumes of multi-sensor and …
Satya Kalluri
,
David A. Bader
,
John Townshend
,
Joseph JáJá
,
Hassan Fallahadl
,
Zengyan Zhang
,
Hassan Fallah-adl
PDF
Cite
DOI
Kronos: A software system for the processing and retrieval of large-scale AVHRR data sets
Raw remotely sensed satellite data have to be processed andmapped into a standard projection in order to produce a multi-temporal data …
Zengyan Zhang
,
Joseph F. JaJa
,
David A. Bader
,
Satya N. V. Kalluri
,
Huiping Song
,
Nazmi El Saleous
,
Eric Vermote
,
John R. G. Townshend
PDF
Cite
A New, Architectural Paradigm for High-performance Computing
At first thought, one may not realize the need for a special issue of Parallel and Distributed Computing Practices focused on Cluster …
David A. Bader
PDF
Cite
SIMPLE: A Methodology for Programming High Performance Algorithms on Clusters of Symmetric Multiprocessors (SMPs)
We describe a methodology for developing high performance programs running on clusters of SMP nodes. The SMP cluster programming …
David A. Bader
,
Joseph JáJá
PDF
Cite
DOI
A New Deterministic Parallel Sorting Algorithm with an Experimental Evaluation
We introduce a new deterministic parallel sorting algorithm for distributed memory machines based on the regular sampling approach. The …
David R. Helman
,
Joseph JáJá
,
David A. Bader
PDF
Cite
DOI
A Randomized Parallel Sorting Algorithm with an Experimental Study
Previous schemes for sorting on general-purpose parallel machines have had to choose between poor load balancing and irregular …
David R. Helman
,
David A. Bader
,
Joseph JáJá
PDF
Cite
DOI
Parallel algorithms for image enhancement and segmentation by region growing, with an experimental study
This paper presents efficient and portable implementations of a powerful image enhancement process, the Symmetric Neighborhood Filter …
David A. Bader
,
Joseph JáJá
,
David Harwood
,
Larry S. Davis
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
Practical Parallel Algorithms for Personalized Communication and Integer Sorting
A fundamental challenge for parallel computing is to obtain high-level, architecture independent, algorithms which efficiently execute …
David A. Bader
,
David R. Helman
,
Joseph JáJá
PDF
Cite
DOI
Scalable data parallel algorithms for texture synthesis using Gibbs random fields
This article introduces scalable data parallel algorithms for image processing. Focusing on Gibbs and Markov random field model …
David A. Bader
,
Joseph JáJá
,
Rama Chellappa
PDF
Cite
DOI
Cite
×