Paper Info
Title
A MapReduce Style Framework for Computations on Trees
Abstract
The emergence of cloud computing and Google's MapReduce paradigm is renewing interest in the development of broadly applicable high level abstractions as a means to deliver easy programmability and cyber resources to the user, while hiding complexities of system architecture, parallelism and algorithms, heterogeneity, and fault-tolerance. In this paper, we present a high-level framework for computations on tree structures. Despite the diversity and types of tree structures, and the algorithmic ways in which they are utilized, our abstraction provides sufficient generality to be broadly applicable. We show how certain frequently used operations on tree structures can be cast in terms of our framework. We further demonstrate the applicability of our framework by solving two applications -- k-nearest neighbors and fast multipole method (FMM) based simulations -- by merely using our framework in multiple ways. We developed a generic programming based implementation of the framework using C++ and MPI, and demonstrate its performance on the aforementioned applications using homogeneous multi-core clusters.
Year
DOI
Venue
2010
10.1109/ICPP.2010.42
Parallel Processing
Keywords
Field
DocType
C++ language,application program interfaces,distributed programming,tree data structures,C++,FMM based simulation,Google MapReduce paradigm,MPI,MapReduce style framework,fast multipole method,fault tolerance,k-nearest neighbors,multicore cluster,programmability,system architecture complexity,tree structures
Computer science,Parallel algorithm,Parallel computing,Tree (data structure),Theoretical computer science,Tree structure,Fast multipole method,Systems architecture,Generic programming,Generality,Cloud computing,Distributed computing
Conference
ISSN
ISBN
Citations 
0190-3918 E-ISBN : 978-0-7695-4156-3
978-0-7695-4156-3
1
PageRank 
References 
Authors
0.35
16
2
Name
Order
Citations
PageRank
Abhinav Sarje1355.71
Aluru, Srinivas21166122.83