MapReduce: Difference between revisions

The MapReduce programming paradigm was also described in [[Danny Hillis]]'s 1985 thesis <ref name="WDHmit86">{{cite book |author-first=W. Danny |author-last=Hillis |date=1986 |title=The Connection Machine |publisher=[[MIT Press]] |isbn=0262081571 |url-access=registration |url=https://archive.org/details/connectionmachin00hill }}</ref> intended for use on the [[Connection Machine]], where it was called "xapping/reduction"<ref>{{cite web |url=http://bitsavers.trailing-edge.com/pdf/thinkingMachines/CM2/HA87-4_Connection_Machine_Model_CM-2_Technical_Summary_Apr1987.pdf |title=Connection Machine Model CM-2 Technical Summary |author=<!--Not stated--> |date=1987-04-01 |publisher=[[Thinking Machines Corporation]] |access-date=2022-11-21}}</ref> and relied upon that machine's special hardware to accelerate both map and reduce. The dialect ultimately used for the Connection Machine, the 1986 [[StarLisp]], had parallel <code>*map</code> and <code>reduce!!</code>,<ref>{{cite web |url=https://www.softwarepreservation.org/projects/LISP/starlisp/supplement-to-the-starlisp-reference-manual-version-5-0.pdf |title=Supplement to the *Lisp Reference Manual |author=<!--Not stated--> |date=1988-09-01 |publisher=[[Thinking Machines Corporation]] |access-date=2022-11-21}}</ref> which in turn was based on the 1984 [[Common Lisp]], which had non-parallel <code>map</code> and <code>reduce</code> built in.<ref>{{cite web |url=https://collections.lib.utah.edu/dl_files/20/2e/202ebf04b52d043c78297444bc9bc4fbc17b6b5e.pdf |title=Rediflow Architecture Prospectus |author=<!--Not stated--> |date=1986-04-05 |publisher=[[University of Utah School of Computing|University of Utah Department of Computer Science]] |access-date=2022-11-21}}</ref> The [[binaryFold (higher-order function)#Linear vs. tree-like_folds|tree-like]] approach that the Connection Machine's [[Hypercube_internetwork_topology|hypercube architecture]] uses to execute <code>reduce</code> in <math>O(\log n)</math> time<ref>{{cite book |url=https://www.cise.ufl.edu/~sahni/papers/imagemono.pdf#page=20 |title=Hypercube Algorithms for Image Processing and Pattern Recognition |last=Ranka |first=Sanjay |date=1989 |access-date=2022-12-08 |section=2.6 Data Sum |publisher=University of Florida}}</ref> is effectively the same as the approach referred to within the Google paper as prior work.{{r|GoogleMapReduce|p=11|q=an associative function can be computed over all prefixes of an N element array in log N time on N processors using parallel prefix computations. MapReduce can be considered a simplification and distillation of some of these models}}