我在做一个项目，需要路径导航图。
问题描述：要提供项目上下文，示例ui应类似于：http://bl.ocks.org/mbostock/4063570 。不同的是，它将用于站点导航。我的问题是在后端处理数据。
对于用户路径a->b->c->d->e，我预计算的数据格式如下所示：
Origin:Start:End:Level
A A B L1
A B C L2
A C D L3
A D E L4现在，假设我有上百万条这样的记录，有100个起源，我可以把它们分组，聚合大小，按大小排序，然后取前10个。所以对于每个起点，起点和关卡，我应该有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减少解决方案。如果我能把它放在滚烫的背景下就更好了。
1条答案
按热度按时间9w11ddsr1#
这里我有一个解决方案，但我不确定它是否适合您：
我想你要做的是拿走所有不需要的记录，比如：
a a b l1
a b c l2级
f g l2（不适合，带走，因为从a到f到l2没有起点）
因此，当拿走一些不需要的记录时，我们必须知道这些记录是否需要；我给出的解决方案如下：
首先我们必须有一个内存中的数据结构db（像redis或hazelcast）；首先，mapreduce将数据插入内存数据结构db；我们在这里插入的是Map数据（关键是start:level like a:l1 b:l5，值是一个列表，它是结尾）
所以Map可能是这样的：
a:l1->b
a:l2->c g
在第一个mapreduce之后，我们将知道所有需要的记录，因为我们有inmemorydb；第二个mapreduce，我们取出不适合的记录；
我们可以在mapper处判断一个像fgl2这样的记录我们在inmemorydb中查询这个Map像getlist使用键a:l1（使用这个键是因为我们在l2处从表单a开始）是列表中的f；如果f在中，它是必需的，如果不是；