跳到主要内容

東京大学 情報理工学系研究科 電子情報学専攻 2010年8月実施 専門 第3問

标签：

Author​

adj-matrix

Description​

Consider counting the number of occurrences of each word in a large set of documents on a large cluster of computers. The set of documents is partitioned into NN sets, and they are processed in parallel by NN machines. Answer the following questions.

(1) Each machine splits a partial set of documents into words. Then the list of words is sorted, and translated into the list of (word, frequency) pairs. The following pseudo code reads a sorted list of words, and outputs (word, frequency) pairs. Find errors in this code, and explain how to correct the code.

count_frequency(File sorted_words_file) {
    int num = 0;
    String word, previous_word = null;
    while (read a word from sorted_words_file) {
        if (word is not previous_word AND previous_word is not null) {
            output_pair(word, num);
        }
        num = num + 1;
        previous_word = word;
    }
}

(2) Show the pseudo code for the function that takes two lists of (word, frequency) pairs, and merge them into a single list.

(3) Explain how to merge NN lists of (word, frequency) pairs generated by NN machines.

(4) Consider distributing the list of words into NN machines before sorting and counting for avoiding the time consuming merge process. It requires a function that maps each word into an integer from 00 to (N−1)(N-1). Show a concrete example of this mapping function.

(5) Describe how to balance the load across the machines when the distribution of word frequency is not uniform, and show a concrete mapping function to be used.

题目描述​

在大型计算机集群上统计大规模文档集中每个单词的出现次数。文档集被划分为 NN 份，由 NN 台机器并行处理。回答下列问题。

(1) 每台机器先把自己负责的文档拆分成单词，将单词列表排序，再转换为“（单词，频数）”对的列表。下面的伪代码读取一个已排序的单词列表并输出这些数对。找出其中的错误，并说明应如何修正。

count_frequency(File sorted_words_file) {
    int num = 0;
    String word, previous_word = null;
    while (read a word from sorted_words_file) {
        if (word is not previous_word AND previous_word is not null) {
            output_pair(word, num);
        }
        num = num + 1;
        previous_word = word;
    }
}

(2) 写出一个函数的伪代码：输入两个“（单词，频数）”对的列表，将它们合并为一个列表。

(3) 说明如何合并由 NN 台机器生成的 NN 个“（单词，频数）”对列表。

(4) 为避免耗时的合并过程，考虑在排序和计数之前先把单词分发到 NN 台机器。为此需要一个把每个单词映射到 00 至 N−1N-1 中某个整数的函数。给出这种映射函数的一个具体例子。

(5) 当单词频率分布不均匀时，说明如何平衡各机器的负载，并给出一个可用的具体映射函数。

考点​

  • 归并排序与多路归并：要求在保持单词有序的前提下合并二路及 NN 路词频表，并正确累加相同单词的频数。
  • 哈希分区与数据倾斜：要求设计单词到机器编号的映射，并针对非均匀词频给出能够平衡负载的分区方案。

Kai​

(1)​

  • Error 1: output_pair(word, num) outputs the current word with previous count.

    Correction: output_pair(previous_word, num)

  • Error 2: The counter num is not reset after outputting.

    Correction: Set num = 0 after the output block.

  • Error 3: The last group of words is not outputted after while loop finishes.

    Correction: Add an if (num > 0) output_pair(previous_word, num);

(2)​

merge (list A, list B) {
    pa = A.head, pb = B.head;
    result = ∅;
    while (pa is not null AND pb is not null) {
        if (pa.word < pb.word) {
            result.append(pa);
            pa = pa.next;
        } else if (pa.word > pb.word) {
            result.append(pb);
            pb = pb.next;
        } else {
            result.append(pa.word, pa.frequency + pb.frequency);
            pa = pa.next, pb = pb.next;
        }
    }
    while (pa is not null) {
        result.append(pa);
        pa = pa.next;
    }
    while (pb is not null) {
        result.append(pb);
        pb = pb.next;
    }
}

(3)​

Using a Min-Heap of size NN to perform a multi-way merge.

  • ① Extract the minimum element from the heap.
  • ② Check the new minimum. If it has the same word, extract it and add its frequency.
  • ③ Repeat ② until output the merged.
  • ④ Insert the next elements from the lists that provided the extracted words into the heap.
  • ⑤ Repeat until empty.

(4)​

Use Hash Partitioning to map.

Example: machine_id = hash(word) MOD N.

hash(word) can be ∑ASCII⁡(char)\sum \operatorname{ASCII}(char) or MD5 and so on.

(5)​

Use Range Partitioning based on Sampling.

Select N−1N-1 pivot words (P1,P2,…,PN−1P_1, P_2, \dots, P_{N-1}) such that the total frequency in each range is approximately equal.

Then Mapping Function:

f(word)=iwherePi≤word<Pi+1(P0=−∞,PN=+∞)f(word) = i \quad \text{where} \quad P_i \le word < P_{i+1} \quad (P_0 = -\infty, P_N = +\infty)
本页目录