在Cypher/Python中爲neo4j優化DBSCAN

您好我一直在嘗試爲Neo4j實現DBSCAN算法，但是我遇到了嚴重的性能瓶頸。我將描述實施，然後尋求幫助。在Cypher/Python中爲neo4j優化DBSCAN

我離散化了可能的ε值，並將每個節點中每個離散化下的鄰居數目計數，以便能夠檢索一個查詢中的所有核心節點。

START a = node(*) 
WHERE a.rel<cutoff threshold>! >= {minp} 
RETURN a

這部分是快，是不是快了部分跟進查詢：

START a = node({i}) 
SET a.label<cutoff threshold>_<minpoints> = {clust} 
WITH a 
MATCH a -[:'|'.join(<valid distance relations>)]- (x) 
WHERE not(has(x.label<cutoff threshold>_<minpoints>)) 
WITH x 
SET x.label<cutoff threshold>_<minpoints>={clust} 
RETURN x

我再挑一個核心節點，從開始，只要還存在着核心節點鄰居，運行上述查詢來標記它們的鄰居。

我認爲問題在於我的圖具有非常不同的稀疏級別 - 從弱相似性開始，它幾乎完全連接，〜10k節點之間有〜50M的關係，而在相似性很強的情況下，只有~20k約10k個節點之間的關係（或更少）。無論如何，它總是非常緩慢。對我來說，最好的辦法是什麼？它是關係類型和起始節點上的索引嗎？我一直無法找到關於這個問題的任何資源，並且令人驚訝的是還沒有實現，因爲這是一個非常標準的圖算法。我可以使用scikit.learn，但然後我將被限制在內存距離matricies :(

來源

2012-09-28 Elliot

也許這是因爲neo4j針對圖遍歷進行了優化，而不是針對圖插入/編輯的主要。我看到neo4j和其他圖形數據庫引擎在數據處理速度上的比較，而neo4j的安靜速度很慢。另一方面，它在圖表遍歷的速度上勝過其他人 – ulkas

你試過的是什麼版本的neo4j？

直到1.8性能一直沒有密碼（而不是語言）的設計目標看看最近的快照（1.9-SNAP）。

還要確保您的熱門數據集不僅僅是從磁盤加載（否則您測量的是磁盤IO），因此您的memory mapped settings以及JVM堆足夠大。

您可能還想查看Neo4j企業中具有較小內存佔用量的GCR緩存。

查詢中count(x)的基數是多少？如果它太小，則會有太多的小型交易正在進行。取決於你的python嵌入式運行或者REST使用更大的tx-scope或者REST-batch-operations

你已經在使用很好的參數了。你的rel-types的變化是什麼？

是否有機會與我們分享您的數據集/生成器和代碼（Neo4j）以進行性能測試？

來源

2012-09-28 15:31:20

感謝您的提示！ count（x）的基數是高度可變的 - 我至少檢查每個節點一次（在覈心集合中），所以通常它很小（0-10），但對於某些核心節點，它會更大， 1000具體。理想情況下，我希望能夠僅返回具有未加標籤的傳出鏈接的節點，因爲這會顯着減少小基數查詢。我將權重離散化到不同的鏈接類型，因爲我不知道如何以有效的方式查詢關係，使得r.weight <閾值。 – Elliot

此外，我很高興分享數據+源代碼，但必須先獲取至少一種聚類方法，然後纔能有時間爲您打包。 DBSCAN並非「真的」是正確的事情，我認爲OPTICS可能適用於我的數據，但我可能只是使用HDP，因此我可以有重疊的羣集。 – Elliot

隨意分享您認爲合理的任何內容。我們也可以繼續關於Neo4j谷歌組的討論。 –

有DBSCAN實現圍繞使用索引。我不知道關於neo4j所以我不能告訴你是否你的你可能需要預先計算的東西實際上是圖的稀疏版本，只有在epsilon閾值內的邊緣。你的數據集，所以你可能想使用OPTICS，它是DBSCAN的一個變體，它去掉了epsilon參數（也不需要區分「核心」節點，因爲每個節點都是某個核心節點epsilon）不要使用Weka版本（或者weka-inspired python版本那是浮動的）。他們是一半光學和一半DBSCAN。

當您有高效的排序可更新堆時，OPTICS可以非常快。

來源

2012-09-28 06:18:53

是的，我看過OPTICS，但我想我會在更簡單的算法上削減我的牙齒（也找不到一個不是Weka的好的算法但我會更難看）。 scikit實現適用於我的直接用例，但圖形數據庫實現具有持續性增量更新的潛力。做epsilon閾值並不是非常有用，因爲我需要這兩個級別，並且它將爲重複檢測節省時間，但它不會用於模糊聚類（語言/文檔類型檢測）。我寧願有一個適用於兩者的實現。 – Elliot

在Cypher/Python中爲neo4j優化DBSCAN

回答

相關問題