Constraint Programming MapReduce'd
Open Access
- 18 May 2016
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1-4
Abstract
While Constraint Programming (CP) aims to explore efficiently large search trees, MapReduce (MR) is a framework that focuses on huge databases and text files. In this work, we try to bridge these two cutting-edge paradigms in order to solve Constraint Satisfaction Problems (CSPs) in distributed and/or parallel environments. We implement a CP system that is responsible to distribute the parts of the serial search tree to the workers in order to explore it. MR is responsible to allocate the physical resources of a cluster and assigns them to the workers. The CP and MR phases interchange and this novel coordination results into significant speedups while solving CSPs. Empirically, our approach is applied on common CSPs, such as N Queens and Number Partitioning.Keywords
This publication has 9 references indexed in Scilit:
- Improvement of the Embarrassingly Parallel Search for Data Centers2014
- Self-splitting of Workload in Parallel Computation2014
- ~okeanos: Building a Cloud, Cluster by ClusterIEEE Internet Computing, 2013
- Enumerating subgraph instances using map-reduce2013
- An Algorithm for Querying Linked Data Using Map-ReduceLecture Notes in Computer Science, 2013
- Embarrassingly Parallel Search2013
- ~okeanos IaaS2012
- Detecting influenza epidemics using search engine query dataNature, 2009
- Confidence-Based Work Stealing in Parallel Constraint Programming2009