我在文本文件中有大量数据（1000000行），每行有128列。
现在我正试图用这些大数据构建一个kd树。我想用map reduce进行计算。
暴力解决我的问题：
1） 编写map reduce作业以查找每列的方差，并选择方差最大的列
2） 以（列名、方差值）为输入，编写另一个map reduce作业，将输入数据分成两部分。对于给定的列名，第1部分包含值小于输入值的所有行；第2部分包含值大于输入值的所有行。
3） 对于每个零件，重复步骤1和步骤2，继续此过程，直到每个零件中剩下500个值。
列名、方差值构成了我的树的单个节点。所以对于树高10的暴力方法，我需要运行1024个map reduce作业。
我的问题：
1）是否有任何方法可以通过运行较少的map reduce作业来提高效率？
2）我每次都在读取相同的数据。有什么办法可以避免吗？
3）是否有其他框架（如pig、hive等）对此类任务有效？
4）我可以使用什么样的框架将数据保存到数据存储中并方便地检索数据？
请帮忙。。。
2条答案
按热度按时间vd2z7a6w1#
对于树的每个节点的mr作业，有o（n）=2^n个作业（其中n是树的高度），这对Yarn的开销不利。但是通过简单的编程技巧，你可以把它降到o（n）=n。以下是一些想法：
在键前面添加额外的分区列，该列是nodeid（树中的每个节点都有唯一的id）。这将创建独立的数据流，并将确保来自树的不同分支的键不会混合，并且对于每层节点，在waves中的nodeid上下文中计算所有方差。这将消除每个节点都有一个mr作业的必要性，而代码变化很小，并确保有o（n）=n个作业，而不是o（n）=2^n；
数据不会围绕拆分值排序，而从父列表拆分元素时，必须将其传输到目标子列表，并且集群节点之间将存在网络通信。因此，使用多台机器在集群上缓存整个数据集可能不会带来显著的改进；
在计算了树的几个级别之后，可能会出现这样的情况：某些节点ID有许多行可以放入Map器或缩减器的内存中，然后您可以继续在内存中完全处理该子树，从而避免代价高昂的mr作业，这可能会在到达树的底部时减少mr作业的数量，或者在处理接近底部时减少数据量；
另一种优化方法是编写一个mr作业，该作业在Map器中围绕每个节点的选定值进行拆分，并通过多路输出输出这些值，并将具有下一个树级别的子节点ID的键发送到reducer，以计算子列表中列的方差。当然，第一次运行没有拆分值，但所有后续运行都将有多个拆分值，每个子节点ID一个。
vptzau2j2#
为什么不试试使用apachespark呢(https://spark.apache.org/)这里？…这似乎是spark的完美用例