十大路徑縮減地圖減少

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，它是必需的，如果不是，