A Mapreduce Style Framework for TreesSarje, Abhinav and Aluru, Srinivas (2009) A Mapreduce Style Framework for Trees. Publisher UNSPECIFIED. Full text available as:
AbstractThe 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.
Archive Staff Only: edit this record |
