Week 6 (large scale data analysis using mapreduce

Question 1

what are these examples of?

Answer 1

distance measures

Question 2

what is the goal behind link analysis

Answer 2

understanding large problem w/ unstructured data

Question 3

how did early search engines work

Answer 3

crawled the web and listed the terms in an inverted index

Question 4

what is an inverted index in the the context of storage of terms

Answer 4

data structure which makes it easy, given a term, to find pointer to all places where that term appears

Question 5

create an inverted index for the given texts

Answer 5

Question 6

a term search for the terms Colorado State University, would give what set

Answer 6

Question 7

what is term spam

Answer 7

Question 8

goals behind a page rank algorithim

Answer 8

provide effective sumnmaries for search results

ordering/ranking results

Question 9

why does a pagerank algorithim simulate random surfers

Answer 9

pages that would have a large number of surfers were considered more “important” than pages that would be barely visited

Question 10

how is a page judged in a page rank algorithim (basic)

Answer 10

terms occuring on the page

and terms used in or near links to that page

Question 11

what is the highest level definition of pagerank

Answer 11

function which assigns a real number to each page on the web

Question 12

what does a higher pagerank of a page mean

Answer 12

the more important it is

Question 13

given this graph, suppose a random surfer starts at page A, what are the probs that a surfer will be on each page in the next step

Answer 13

Question 14

now suppose surfer at B, whats the prob of next step

Answer 14

Question 15

for pagerank, what is the dimension of the transition matrix M

Answer 15

n columns and n rows

Question 16

what does the transition matrix of this graph look like

Answer 16

Question 17

what does the first and second column of this transition matrix mean

Answer 17

Question 18

what does this matrix mean/represent?

Answer 18

Question 19

for the transition matrix M, if we surf at any of the n page of web with equal prob. What will the inital vector look like and where is it located

Answer 19

1/n for each component

farthest left, first col vector (i think)

Question 20

what does the matrix mean and what does the vector mean?

and what does this equal

Answer 20

M = prob for next step from current location

Vec = probability for being in the current location

== distribution of the surfer after this step, probability for being in the next possible location

Question 21

what is v_j and m_ij ?

Answer 21

m_ij is prob that a surfer at node J will move to node i at the next step

v_j is ther prob that the surfer was at node j at prev step

Question 22

what is x_i

Answer 22

prob that a random surfer will be at node i at the next step

Question 23

what 2 conditions

Answer 23

graph is strongly connected

there are no dead ends (nodes that have no arcs out)

Question 24

how many iters to have v_j converge

Answer 24

50-75 iters

Question 25

Answer 25

Question 26

why do we need to do matrix vector multiplication in mapreduce with a sufficiently large dataset

Answer 26

vector v cannot fit in main memory

more than 1.4 billion pages

Question 27

in matrix-vector multiplication, what will be stored in the files

Answer 27

matrix M and vector V stored seperatly

Question 28

in matrix-vector multiplication, what does the map function do

Answer 28

Question 29

in matrix-vector multiplication, what does the reduce function look like

Answer 29

Question 30

in matrix-vector multiplication, what do you do if the vector v cant fit in main memory

Answer 30

Question 31

in matrix-vector multiplication, what does stripe-ing look like

Answer 31

Question 32

what is a dead end and why is it a problem

Answer 32

a page with no links out, surfers reaching page will dissapear

Question 33

what is a spider trap

Answer 33

groups of pages that all have outlinks but never link to any other pages

Question 34

what would happen if dead ends were allowed

Answer 34

Question 35

2 solutions for dealing with dead ends

Answer 35

Question 36

in recursive deletion, on the pages that are deleted, whats their page rank

Answer 36

the parent, or if the parent is deleted then its the parent of that

it just goes down the tree

Question 37

with recursive deletion, the sums will eventually exceed 1. how does this change the definition of our matrix

Answer 37