F = 2PR/(P + R)

(tp + tn)/(tp + tn + fp + fn)

• Defination:
  • 1. Precision: # of retrieved relevant / # of retrieved
    2. Recall: # of retrieved relevant /# of relevant
  • 1. Precision = tp / (tp + fp)
    2. Recall = tp/(tp + fn)
• Harmonic mean of precision, recall (F-measure):
  • Harmonic mean of n numbers: n/(1/a1 + 1/a2 + 1/a3 + ….1/an)
  • F-measure = 2RP/(R + P)
• MAP = Sum(AvgP(i))/Q

• 4 Properties:
  • 1. No negative
    2. D(x, y) iff x = y
    3. D(x, y) = D(y, x) symmetric
    4. D(x, y) <= D(x, z) + D(z, y) Triangle Inequality
• 5 Specific distance measure :
  • 1. Jaccard Distance: (Jaccard Similarity: (A &B) /( A or B); Jaccard Distance: 1- JS)
    2. Hamming Distance:
    3. Euclidean Distance

• 3 different ways the crawlers can interact:
  • 1. Independent: no coordination, every process follows its extracted links
    2. Dynamic assignment: a central coordinator dynamically divides the web into small partitions and assign each partition to a process
    3. static assignment: web is partitioned and assigned without a central coordinator before the crawler starts.

= REL(1) + REL(2)/log(3) + REL(3)/log(4) + ….REL(n)/log(n + 1)

• Zipf’s Law: y = 1/x
  • y is the frequency of the word, and x is its ranking in the frequency table. C = -1.
  • Zipf’s law—log-log scale:

    since data has exponetial grow, when using log-log scale, it becomes a straight line with slope c like: logy = logK + Clogx

• Heap’s Law: V= Kn^C
  • If V is the size of the vocabulary and n is the number of words
  • K = 10 ~ 100， C= 0.4 ~ 0.6

• speed up the merging of positing in an inverted index

• For term with the same pronunciation to be encoded to the same string so that matching can occur despite minor difference in spelling.

• sum(Ai Bi)/sqrt(sum(Ai^2)) sum(Bi^2)

• = sum(1/rank(Qi))/N

Tokenization（语义切分）: The task of chopping a document into pieces called tokens,and possibly throw away possible characters.

• three main properties:
  1. easy to calculate hash value for any given data (对已知data hash 容易)
  2. difficult to get text that has a given hash vlaue (从hash value得到text难)
  3. a small change to data yields a different hash value (较小的改变可能产生不同的hash value)
  4. ——不记了
• hash functions: MD5, SHA-1(SHA-2)