Week 6 (large scale data analysis using mapreduce Flashcards
what are these examples of?
distance measures
what is the goal behind link analysis
understanding large problem w/ unstructured data
how did early search engines work
crawled the web and listed the terms in an inverted index
what is an inverted index in the the context of storage of terms
data structure which makes it easy, given a term, to find pointer to all places where that term appears
create an inverted index for the given texts
a term search for the terms Colorado State University, would give what set
what is term spam
goals behind a page rank algorithim
provide effective sumnmaries for search results
ordering/ranking results
why does a pagerank algorithim simulate random surfers
pages that would have a large number of surfers were considered more “important” than pages that would be barely visited
how is a page judged in a page rank algorithim (basic)
terms occuring on the page
and terms used in or near links to that page
what is the highest level definition of pagerank
function which assigns a real number to each page on the web
what does a higher pagerank of a page mean
the more important it is
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
now suppose surfer at B, whats the prob of next step
for pagerank, what is the dimension of the transition matrix M
n columns and n rows
what does the transition matrix of this graph look like
what does the first and second column of this transition matrix mean
what does this matrix mean/represent?
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
1/n for each component
farthest left, first col vector (i think)
what does the matrix mean and what does the vector mean?
and what does this equal
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
what is v_j and m_ij ?
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
what is x_i
prob that a random surfer will be at node i at the next step
what 2 conditions
graph is strongly connected
there are no dead ends (nodes that have no arcs out)
how many iters to have v_j converge
50-75 iters
why do we need to do matrix vector multiplication in mapreduce with a sufficiently large dataset
vector v cannot fit in main memory
more than 1.4 billion pages
in matrix-vector multiplication, what will be stored in the files
matrix M and vector V stored seperatly
in matrix-vector multiplication, what does the map function do
in matrix-vector multiplication, what does the reduce function look like
in matrix-vector multiplication, what do you do if the vector v cant fit in main memory
in matrix-vector multiplication, what does stripe-ing look like
what is a dead end and why is it a problem
a page with no links out, surfers reaching page will dissapear
what is a spider trap
groups of pages that all have outlinks but never link to any other pages
what would happen if dead ends were allowed
2 solutions for dealing with dead ends
in recursive deletion, on the pages that are deleted, whats their page rank
the parent, or if the parent is deleted then its the parent of that
it just goes down the tree
with recursive deletion, the sums will eventually exceed 1. how does this change the definition of our matrix
