圖形數據庫對於最短路徑算法更好嗎？

Question

我的目標是爲道路網絡編寫最短路徑算法。

目前我的架構是這樣的：我將所有的數據存儲在啓用PostGIS的PostgreSQL數據庫中。我做了一個SELECT * FROM ways，它在一個具有100,000條邊的表格（方式）上花費不到3秒鐘，然後我將（Java，Ruby或基於任何東西的）最短路徑算法應用到已駐留在內存中的圖上。在具有100,000條邊的圖表上，第二個操作可能需要約1.5秒。

所以，它需要：

• 2-3秒鐘，從數據庫中的所有的方式加載到內存中，並創建一個圖（節點被存儲在一個表的方式（邊緣））;
• 1-1.5秒來計算已經在內存中的圖形上的最短路徑。

這是非常相似，pgRouting呢（據我所知它採用C升壓存儲在內存中的圖），除了pgRouting大約需要2秒的總計算對同一數據集的最短路徑（是的，它速度很快，但它對我來說是一個黑匣子，所以我需要我自己的）。

但最近我發現有關Graph數據庫和關於Neo4j。在他們的網站上，他們聲稱「仍然能夠以亞秒級的速度在數百萬道路和航點的圖表上進行這些計算，這使得在許多情況下可以放棄使用K/V商店的預計算索引的正常方法，並且能夠將路由放到關鍵路徑上，以適應現場條件並構建高度個性化和動態的空間服務。「

所以問題是：圖形數據庫會加快我的特定問題嗎？

問題具有以下性質：

• 數據庫由一個表（方式）的;
• 對數據庫的唯一查詢是獲取所有進入內存的方法（構建圖）;
• 我不需要可擴展性，即圖表可能不會增長。

Answer 1

我沒有「圖形」數據庫的經驗，但根據你的問題來判斷我腦海中有幾件事。

首先，直截了當的答案將是「創建一個這樣的圖形數據庫，並與您的解決方案進行性能比較」。您可以測量內存使用情況，執行時間（速度），CPU利用率和/或其他度量標準。這將爲您提供足夠的數據來做出決定。

我的其他建議是修改你的方法。您描述的三個問題屬性（一個表，加載所有路徑&不需要可伸縮性）適用於您當前的域，但不適用於圖數據庫的一個。這是一個完全不同的編程範例，您可能需要調整和調整您的方法以適應這些特殊類型數據庫的領域。如果您在非標準環境中應用標準方法（如圖形數據庫），那麼執行性能或任何其他類型的比較是不合理的。

重述：將您的問題轉換爲圖形數據庫的條款並進行相應的建模。做完這些之後，對兩種解決方案進行性能比較。

我的賭注是，假設你翻譯了&適合圖形數據庫的問題，它會給你更好的性能。 「存儲讀取排序」的經典方法很簡單，但除非積極優化纔有效。

Answer 2

圖形數據庫最初可能不會將所有數據加載到內存中，但隨着時間的推移，好的數據庫將被設計用於處理超大型數據集。但是，一旦數據存在，圖形數據庫就必須少做關係數據庫遍歷鏈接的工作。這是因爲它可以使用它們的身份直接訪問相關對象，而不必使用B-樹索引和（可能）連接表，所以一旦節點和邊被緩存，它應該更快。

Answer 3

如果您使用任何圖形數據庫（如Neo4j），您肯定不必重新發明輪子。許多最短路徑算法都是內置於此的，它旨在處理複雜性，以防在任何特定道路，單向道路，道路得分等情況下考慮速度限制。如何在數據增長時跟上性能10次，或者100次。考慮到你的總計算時間爲3秒，對於100,000種方式，它可以在1M分鐘內進行，而在Neo4j中，響應將以毫秒爲單位。

Answer 4

與圖形數據庫的突破不僅是表演，但更多的概念：你的路由算法處理單個關係圖表（即圖中的鏈接都是同一類型的），而與graphdatabases你有多 - 關係圖。

這使您可以計算節點之間的最短路徑只採取特定類型的邊緣或避免另一種類型。

欲瞭解更多信息，你應該閱讀關於the algebra behind graph db和管道的概念。

我強烈建議thinkerpop項目從圖形數據庫開始。