十大路径缩减地图减少

Question

我正在研究一个需要路径导航图的项目。

问题描述： 为了给出项目上下文，示例UI预计看起来类似于：http://bl.ocks.org/mbostock/4063570 。不同之处在于它将用于站点导航。我的问题是在后端处理数据。

对于用户路径A-> B-> C-> D->电子 我预先计算的数据格式如下：

Origin:Start:End:Level 
A A B L1 
A B C L2 
A C D L3 
A D E L4 

现在，假设我有几百万的记录像这样与100的起源，我可以将它们分组，汇总尺寸并按大小desc排序并进入前10名。因此，对于每个起源，开始和Level，我应该有10条记录。 所以对于一个4级的图，对于图中的一个给定的起始节点，我将有10 .. 10^2 .. 10^3 .. 10^4。

真正的问题： 排序后的前10位不能带走所有不需要的L3和L4。对于给定的原点，L1的末尾应该是L2的开始，L2的末尾应该是L3的开始，依此类推。由于这个原因，我有许多记录，其中许多L2开始不属于L1结束，并且随着等级增加而倍增。 插图：

A A B L1 
A B C L2 
A F G L2 <-- this comes in top 10 after aggregation, but start is not the end of L1 (B in this case) 

我的尝试：排序和切片前10后，我做一个自我在1。每个级别1加入数以百万计的记录我有10个级别。它在计算上非常昂贵。

我在寻找什么： 通用和更便宜的Map-Reduce解决方案。更好的是，如果我可以在烫伤的情况下得到它。

Answer 1

在这里，我有一个解决办法，但我不知道这是给你的西装：

我想你想要做的就是带走所有的不是，需要记录下哪些喜欢什么：

AAB L1

ABC L2

AFG L2（不适合，带走，由于没有从A开始至F通过L2）

于是带走一些未所需的R时我们必须知道这些记录是否需要;我给出的解决方案如下：

首先我们必须有一个在内存中的数据结构数据库（如Redis或Hazelcast）;在第一个MapReduce中，我们什么都不做，只是将数据插入到内存数据结构数据库中;我们在这里插入的是地图数据（关键是开始：L1 B：：像A级L5，并且该值是一个列表是年底）

所以一个地图，也许是这样的：

答：L1 - “乙

答：L2-> CG

我们就会知道所有需要的记录，因为我们有InMemoryDB第一的MapReduce后; 第二个MapReduce我们拿出不适合的记录;

我们可以在映射器中查找像A F G L2这样的记录，我们在InMemoryDB中查询Map，就像getList使用键A：L1（因为我们这里在L2开始形式A）在列表中是F;如果F是In，它是必需的，如果不是，