1

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

问题描述：为了给出项目上下文，示例 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-reduce 解决方案。如果我能在烫伤的情况下得到它会更好。

4

1 回答 1

2

在这里，我有一个解决方案，但我不确定它是否适合您：

我想你想要做的是带走所有不需要的记录，例如：

AAB L1

ABC L2

AFG L2（不适合，带走，因为没有从A到F通过L2开始）

所以在拿走一些不需要的记录时，一定要知道这些记录是否需要；我给出的解决方案如下：

首先，我们必须有一个内存数据结构 DB（类似于 Redis 或 Hazelcast）；在第一个 MapReduce 中，我们只向内存数据结构 DB 插入数据；我们在这里插入的是地图数据（key是start:level，如A:L1 B:L5，value是一个List，即结束）

所以地图可能是这样的：

A:L1->B

A:L2->CG

在第一个 MapReduce 之后，我们将知道所有需要的记录，因为我们有 InMemoryDB；第二个 MapReduce 我们取出不适合的记录；

我们可以在 mapper 中判断像 AFG L2 这样的记录我们在 InMemoryDB 中查询 Map 就像 getList 使用键 A:L1（使用这个是因为我们在 L2 开始表单 A）是 List 中的 F；如果 F 是 In 则需要，如果不是则不需要；

于 2013-10-18T07:10:53.957 回答