ISU Electrical and Computer Engineering Archives

A Mapreduce Style Framework for Trees

Sarje, Abhinav and Aluru, Srinivas (2009) A Mapreduce Style Framework for Trees. Publisher UNSPECIFIED.

Full text available as:

PDF - Requires Adobe Acrobat Reader or other PDF viewer.

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, while hiding complexities of system architecture, heterogeneity, fault-tolerance, and parallel algorithms. In this paper, we present a high-level framework for searches and 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 a number of basic tree operations can be cast in terms of our framework, and further demonstrate its applicability by solving two applications – k-nearest neighbors and many-body simulations – by merely using the proposed framework in multiple ways. Finally, we discuss algorithmic strategies for building such a framework to enable tree-based applications on parallel systems.

EPrint Type:Technical Report
Uncontrolled Keywords:Tree Framework MapReduce Abstract
Subjects:Computer Engineering > SOFTWARE SYSTEMS > Parallel and Distributed Computing
Computer Engineering > SOFTWARE SYSTEMS > Computational Biology and Computational Science
Computer Engineering > SOFTWARE SYSTEMS > Software Engineering
ID Code:495
Identification Number:Identification Number UNSPECIFIED
Deposited By:Abhinav Sarje
Deposited On:02 June 2009

Archive Staff Only: edit this record