When you say graph algos using a KV store, do you mean you’re gonna make a graph database out of a KV store that’s a truly native graph db, meaning it benefits from index free adjacency?
I was recently looking for examples of those and found HelixDB, a native graph db that uses LMDB as its underlying storage engine. Could be a candidate for a native graph db nostr relay. Pretty new though, not sure whether it’s fully functional, unlike neo4j which is very well established.
Login to reply
Replies (1)
i think so, but i'm not sure i fully understand that.
i just made a pair of tables, one is event/pubkey/kind and a byte flag that indicates the event is authored by the pubkey, or it points to that pubkey, or that pubkey points to it, and then the second is pubkey/event/kind, a forward and reverse lookup
so i figure you would then follow an edge-inwards path so pubkey a, and pubkey b, then trace each one to the next, so it would alternate pubkey->event->pubkey->etc and it would explore the first level of each, looking for the event on each vector, and iterate depth, until it finds the common points that exist between them, discarding longer ones when it finds shorter ones.
so i think that technically is index free adjacency because it is a scan on a linear, lexicographically sorted table, that consumes nodes as it passes, skipping them if already seen on the path, and the computation time would be some factor of the number of vertexes on each, by the depth between them, and each node on the path would contribute some factor to the number of keys that must be iterated. once the shortest midpoints are found, you would have the path unwrapped
that's just my naive conception of the algorithm. i imagine that even in a graph in the millions that path lengths would be between 1 and maybe 10-12 or so, on the outside.
keep in mind also that the kv store is going to keep all of the graph indexes in memory during the operation so once the as yet unknown path points are found, and the common node is discovered, the remainder of iteration is going to likely be mostly in memory.
i need to fix the index order. kind is the first thing that must match, and putting it first groups all vectors of that type in one table.