In che modo Titan ottiene una ricerca costante del tempo utilizzando HBase/Cassandra?

Question

Nei O'Reilly libro "database del grafico" nel capitolo 6, che è su come Neo4j memorizza un database grafico che dice:

Per comprendere il motivo per cui l'elaborazione grafico nativo è così molto più efficiente di grafici basati su indicizzazione pesante, considerare quanto segue. A seconda dell'implementazione, le ricerche dell'indice potrebbero essere O (log n) in complessità algoritmica rispetto a O (1) per cercare relazioni immediate. Per attraversare una rete di m passi, il costo dell'approccio indicizzato, a O (m log n), fa sembrare nullo il costo di O (m) per un'implementazione che utilizza l'adiacenza dell'indice senza indici.

Esso viene poi spiegato che Neo4j raggiunge questo ricerca costante di tempo memorizzando tutti i nodi e le relazioni come record dimensione fissa:

Con record di dimensioni fisse e ID record puntatore simili, attraversamenti sono implementati semplicemente inseguendo i puntatori attorno a una struttura dati, che può essere eseguita a velocità molto elevata con . Per attraversare una particolare relazione da un nodo a un altro, il database esegue diversi calcoli di ID economici (questi calcoli sono molto più economici di cercando indici globali, come dovremmo fare se simulare un grafico in un documento non nativo non grafico database)

Quest'ultima frase fa scattare la mia domanda: in che modo Titan, che utilizza Cassandra o HBase come back-end di archiviazione, raggiunge questi miglioramenti di prestazioni o compensa?

Answer 1

Neo4j raggiunge O (1) solo quando i dati sono in memoria nella stessa JVM. Quando i dati sono su disco, Neo4j è lento a causa del puntatore che insegue sul disco (hanno una rappresentazione povera del disco).

Titan raggiunge solo O (1) quando i dati sono in memoria nella stessa JVM. Quando i dati sono su disco, Titan è più veloce di Neo4j perché ha una migliore rappresentazione del disco.

Vedere il seguente post sul blog che spiega quanto sopra quantitativamente: http://thinkaurelius.com/2013/11/24/boutique-graph-data-with-titan/

Quindi, è importante capire quando la gente dice O (1) quale parte della gerarchia di memoria sono in Quando sei in una. singola JVM (macchina singola), è facile da essere veloce in quanto sia Neo4j che Titan dimostrano con i rispettivi motori di caching. Quando non è possibile inserire l'intero grafico in memoria, è necessario fare affidamento su layout di disco intelligenti, cache distribuite e simili.

Si prega di consultare i seguenti due post del blog per ulteriori informazioni:

http://thinkaurelius.com/2013/11/01/a-letter-regarding-native-graph-databases/ http://thinkaurelius.com/2013/07/22/scalable-graph-computing-der-gekrummte-graph/

Answer 2

OrientDB utilizza un approccio simile in cui i rapporti vengono gestiti senza indici (adiacenza libero-index), ma piuttosto con puntatori diretti (LINKS) tra i vertici. È come nei puntatori di memoria ma sul disco. In questo modo OrientDB ottiene O (1) sul movimento in memoria e su disco.

Ma se hai un vertice "Città" con migliaia di bordi ai vertici "Persona", e stai cercando tutte le persone con età> 18, quindi OrientDB utilizza gli indici perché è coinvolta una query, quindi in questo caso è O (log N).