大规模数据处理与云计算-文字检索算法.pptVIP

* Why is IR hard? Because language is hard! fateful D.J.[?fe?tf?l] K.K.[?fetf?l] adj. 重大的,有很大影响的,引起灾难的,灾难性的 star-crossed D.J.[?stɑ:?kr?:st, -?kr?st] K.K.[?stɑr?kr?st, -?krɑst] adj. 运气不好的 倒霉的;不幸的 * Assume document is relevant if it has a lot of query terms Replace relevance(q, di) with sim(q, di) Compute similarity of vector representations * * in a nutshell 简言之；一言以蔽之 * Search Engines Information Retrieval in Practice, page 166 * * 22 * 22 Vocabulary Size: Heaps’ Law Heaps’ Law: linear in log-log space Vocabulary size grows unbounded! M is vocabulary size T is collection size (number of tokens) k and b are constants Typically, k is between 30 and 100, b is between 0.4 and 0.6 * Heaps’ Law for RCV1 Reuters-RCV1 collection: 806,791 newswire documents (Aug 20, 1996-August 19, 1997) k = 44 b = 0.49 First 1,000,020 terms: Predicted = 38,323 Actual = 38,365 Manning, Raghavan, Schütze, Introduction to Information Retrieval (2008) * Postings Size: Zipf’s Law Zipf’s Law: (also) linear in log-log space Specific case of Power Law distributions In other words: A few elements occur very frequently Many elements occur very infrequently cf is the collection frequency of i-th common term c is a constant * Zipf’s Law for RCV1 Reuters-RCV1 collection: 806,791 newswire documents (Aug 20, 1996-August 19, 1997) Fit isn’t that good… but good enough! Manning, Raghavan, Schütze, Introduction to Information Retrieval (2008) * Figure from: Newman, M. E. J. (2005) “Power laws, Pareto distributions and Zipfs law.” Contemporary Physics 46:323–351. Power Laws are everywhere! * MapReduce: Index Construction Map over all documents Emit term as key, (docno, tf) as value Emit other information as necessary (e.g., term position) Sort/shuffle: group postings by term Reduce Gather and sort the postings (e.g., by docno or tf) Write postings to disk MapReduce does all the heavy lifting! * 1 1 2 1 1 2 2 1 1 1 1 1 1 1 1 2 Inverted Indexing with MapReduce 1 one 1 two 1 fish one fish,