A short keynote review of Course at school

---

Lec2

• Distributed File System

  • Chunk,Master,Client

• MapReduce

  • Map,shuffle(group by key),Reduce
  • Wordcount,Join,PageRank

• Hashing

  • lambda = (number of keys / TableSize) -> not waste space
  • minimize collisions
  • collision resolution
    • Separate Chaining , lamda can bigger than 1
    • Closed Hashing ,lambda<=1
    • not good at Table Traversal -> search-tree

Lec3

• PageRank

  • Recursive Form
  • Maxtrix Form
    • Power Iteration
      • proof
  • Random Walk
  • dead ends & spider traps
  • Teleports

• Topic-Sepcific PageRank

  • Teleports in topic

• SimRank

  • Walk in k-partite graph

• Link Spam

  • Spam's PageRank
  • Trust Rank
  • Spam Mass Estimation(PR-TR/PR)

• HITS

  • Hubs & Authorities
  • a=Ah,h=Aa
  • pricipal eigenvector

PR HITS in & out

PageRank MapReduce:

Power Iteration & Matrix Encoding Block-based Update Algorithm Block-Stripe Update Algorithm

Lec4

• Bipartite Matching

  • Onlien/Offline
  • CR -> 0.5

• CTR

  • greedy
    • CR0.5
  • Balance
    • Min Revenue 2/3B
    • CR
      • Best 3/4
      • Worst 0.63(1-1/e)

Lec5

• A-Priori
• Shingle
• Jaccard similarities
• MinHashing
• LSH
  • r & b
  • s
  • 1-(1-t^r)^b

Lec6

• SGD
• Sampling
  • fixed proportion(d/(10x+19d))
  • fixed-size
• Queries
  • Sliding Window
    • Uniformity assumption
    • non-uniform-> DGIM
      • Bad: unknown region small but unknown area at the -> Cnt1 only
      • Buckets & Timestamps
      • Sum the sizes of all buckets but the last & add half the size of the last bucket
      • r -> O(1/r) end
• Filtering?

Lec9

Cosine, Jaccard, and Euclidean -> vectors,set,points

• Hierarchical clustering

  • Agglomerative

• Cohesion

  • Diameter
  • Average Dist
  • Density-based

• KMeans

  • Populating Clusters
  • select k
    • Try diff k
    • Elbow Method(Average distance falls rapidly until right k)

• DFR

  • DS , CS, RS
  • Mahalanobis Distance -> close

• Spectral Clustering

  • Laplacian Matrix: L=D-A
  • Decomposition-> Eigenvalues -> Eigenvectors
  • Clustering