Yioop - PHP Search Engine

Mar 7 In-Class Exercise.

Post your solutions to the Mar 7 In-Class Exercise to this thread.

Best,

Chris

(Edited: 2018-03-07)

Post your solutions to the Mar 7 In-Class Exercise to this thread. Best, Chris

-- Mar 7 In-Class Exercise

  Run the crawler and produce pairs (i,j)

  Map: feed each pair (i,j) to mapper[i]. 
  Mapper[i,j] produces a tuple
  of the form ((j, (i, in)), (i,(j, out)))
  which are then fed to the reducers according 
  to the keys

  Reducer: The reducer either receives
  (j, (i, in)) or (j, (i', out)). For 
  every unique pair of (i,i'), output (j,(i,i'))

  Map: each mapper receives a 
  tuple (j,(i,i')) and outputs (i,i')

  Reduce: each reducer receives (i,i')
  output (i,i')

(Edited: 2018-03-07)

Run the crawler and produce pairs (i,j) Map: feed each pair (i,j) to mapper[i]. Mapper[i,j] produces a tuple of the form ((j, (i, in)), (i,(j, out))) which are then fed to the reducers according to the keys Reducer: The reducer either receives (j, (i, in)) or (j, (i', out)). For every unique pair of (i,i'), output (j,(i,i')) Map: each mapper receives a tuple (j,(i,i')) and outputs (i,i') Reduce: each reducer receives (i,i') output (i,i')

-- Mar 7 In-Class Exercise

1. First we have a bunch of links going into a map program which maps every url `i` with with a specific `j` it is linked to. We map these as a <j,<i,out>>. But this also gives us the mapping <i,<j,in>>. This will be useful to us.

2. Now if we reduce the tuples, that are represented as such: <j,<i,in>> & <j, <i',out>>. This has given us the second degree link between `i` and `i'`. Since this is a reducer, we cannot modify the keys. Thus the output of this step will be <j,<i,i'>>.

3. Now we map our result into pairs <i,i'>, and thus have our answer.

(Edited: 2018-03-07)

1. First we have a bunch of links going into a map program which maps every url @BT@i@BT@ with with a specific @BT@j@BT@ it is linked to. We map these as a <j,<i,out>>. But this also gives us the mapping <i,<j,in>>. This will be useful to us. 2. Now if we reduce the tuples, that are represented as such: <j,<i,in>> & <j, <i',out>>. This has given us the second degree link between @BT@i@BT@ and @BT@i'@BT@. Since this is a reducer, we cannot modify the keys. Thus the output of this step will be <j,<i,i'>>. 3. Now we map our result into pairs <i,i'>, and thus have our answer.

-- Mar 7 In-Class Exercise

 Map:
 For every i, output a list like:
 <i,j> -> <<j,<i,in>>, <i,<j,out>>>

 Reduce:
 Now, for all keys with j, will be mapped to the same reduce like:
 <j,<i,in>>,<j,<i',out>> -> <j,<i,i'>>

 The output of reduce will then be given to another map function, where the key will be stripped:
 <j,<i,i'>> -> <i,i'>

 Finally, the reducer will output all the <i,i'>

(Edited: 2018-03-07)

Map: For every i, output a list like: <i,j> -> <<j,<i,in>>, <i,<j,out>>> Reduce: Now, for all keys with j, will be mapped to the same reduce like: <j,<i,in>>,<j,<i',out>> -> <j,<i,i'>> The output of reduce will then be given to another map function, where the key will be stripped: <j,<i,i'>> -> <i,i'> Finally, the reducer will output all the <i,i'>

-- Mar 7 In-Class Exercise

input to mapper <i,j1>,<i,j2>.....<i,jt>

output of mapper ((j, (i, in)), (i,(j, out)))

output of reducer <j, <i,i`>

output of mapper <i,i'>

output of reducer <i,i'>

(Edited: 2018-03-07)

input to mapper <i,j1>,<i,j2>.....<i,jt> output of mapper ((j, (i, in)), (i,(j, out))) output of reducer <j, <i,i@BT@> output of mapper <i,i'> output of reducer <i,i'>

-- Mar 7 In-Class Exercise

Round 1:

Mapper :

Input to the mapper: send key value pairs <i,j>

Output of the mapper: <j,<i,in>>,<i,<j,out>>

Reducer:

Input to the reducer:<j,<i,in>> or <j,<i',out>>

Output of the reducer:<j,<i,i'>,...>

Round2:

Mapper:

Input to the mapper: <j,<i,i'>,...>

Output of the mapper: <<i,i'>, <k,k'>...>

Reducer: Does nothing

(Edited: 2018-03-07)

'''Round 1:''' '''Mapper :''' Input to the mapper: send key value pairs <i,j> Output of the mapper: <j,<i,in>>,<i,<j,out>> '''Reducer: ''' Input to the reducer:<j,<i,in>> or <j,<i',out>> Output of the reducer:<j,<i,i'>,...> '''Round2:''' '''Mapper:''' Input to the mapper: <j,<i,i'>,...> Output of the mapper: <<i,i'>, <k,k'>...> '''Reducer:''' Does nothing

-- Mar 7 In-Class Exercise

Name: Kunal Deshmukh ---- 1. MAP: emit keys j which point to i as a pair (j, iin) 2. REDUCE: for each i, emit a list of to the reducer REDUCER: reducer simply passes all inputs received by the mapper.

<nowiki> Name: Kunal Deshmukh ---- 1. MAP: emit keys j which point to i as a pair (j, iin) 2. REDUCE: for each i, emit a list of <j,<i,i'>> MAP: for each pair received by the reducer, map removes 'j' component and passes <i,i'> to the reducer REDUCER: reducer simply passes all inputs received by the mapper. </nowiki>

-- Mar 7 In-Class Exercise

 Round 1
 
 mapper - U is the set containing (i,j)
 for i,j in U:
    output(<<j,<i,in>>) as out1
    output(<i,<j,out>>>) as out2
  return out1, out2

 reducer - 
    for key1, value1 in out1:
          if key1 in out2.keys():
             two_hops_output.append(<<key1,value1>, <key2, out2[key2]>>)
    return two_hops_output
 Round 2 -

 mapper - input - two_hops_output
   for value1, value2 in two_hops_output:
       output(value[0],value[0]) as out1
   return out1
 reducer - 
    for value in out1:
      final_output.append(value)
     return final_output

Round 1 mapper - U is the set containing (i,j) for i,j in U: output(<<j,<i,in>>) as out1 output(<i,<j,out>>>) as out2 return out1, out2 reducer - for key1, value1 in out1: if key1 in out2.keys(): two_hops_output.append(<<key1,value1>, <key2, out2[key2]>>) return two_hops_output Round 2 - mapper - input - two_hops_output for value1, value2 in two_hops_output: output(value[0],value[0]) as out1 return out1 reducer - for value in out1: final_output.append(value) return final_output

-- Mar 7 In-Class Exercise

Map 1:

  For every i, output:
  <i,j> -> <<j,<i,in>>, <i,<j,out>>>

Reduce 1:

   All records with key j, will be shuffled to the same reduce:
   <j,<i,in>>,<j,<i',out>> -> <j,<i,i'>>

Map 2:

  The key is removed:
 <j,<i,i'>> -> <i,i'>

Reduce 2:

  It simply outputs all the <i,i'> received from all mappers.

Map 1: For every i, output: <i,j> -> <<j,<i,in>>, <i,<j,out>>> Reduce 1: All records with key j, will be shuffled to the same reduce: <j,<i,in>>,<j,<i',out>> -> <j,<i,i'>> Map 2: The key is removed: <j,<i,i'>> -> <i,i'> Reduce 2: It simply outputs all the <i,i'> received from all mappers.

-- Mar 7 In-Class Exercise

  pairs <i,j> is the input to Map

  Step1
  Map: feed each pair <i,j> to m[i]. 
  m[i] produces a tuple of the form <<j, <i, in>>, <i,<j, out>>>

  Reduce: The reducer would reduce the tuples by key j
  input: <j, <i, in>> , <j, <i', out>>
  output: <j,<i,i'>>

  Step2
  Map: strip key j
  input: each mapper receives tuple <j,<i,i'>>
  outputs: <i,i'>

  Reduce:  does nothing.
  input: <i,i'>
  output <i,i'>

pairs <i,j> is the input to Map Step1 Map: feed each pair <i,j> to m[i]. m[i] produces a tuple of the form <<j, <i, in>>, <i,<j, out>>> Reduce: The reducer would reduce the tuples by key j input: <j, <i, in>> , <j, <i', out>> output: <j,<i,i'>> Step2 Map: strip key j input: each mapper receives tuple <j,<i,i'>> outputs: <i,i'> Reduce: does nothing. input: <i,i'> output <i,i'>