ESespeed·Dec 5, 2015
I have started to converge on this space from a different perspective -- thinking about how to design a graph database in terms of discrete topology, which has led me to thinking in terms of the holographic principle: "the description of a volume of space can be thought of as encoded on a boundary to the region". Specifically, I have been exploring how to use shape to succinctly and uniquely define an object/relation in terms of the composition of its constituent parts in a way that enables fast decomposition back into its constituent parts.
For example, picture a spatial structure resulting from a the prime decomposition (https://en.wikipedia.org/wiki/Integer_factorization#Prime_de...) of all the positive 64 bit integers [0 to 2^63-1]. In this space, the prime numbers are the base of this discrete topology. Picture the trees resulting f
Read the rest
rom all the decompositions, with the roots jutting up into space like peaks in a mountain range. This gives the numbers shape and provides a foundation to anchor more abstract objects representations.
To further illustrate the point, we could define a discrete topology with each unicode character (https://en.wikipedia.org/wiki/Unicode#Code_point_planes_and_...) as a base element. Now define an algorithm to decompose strings into its constituent parts. Similarly, we could do the same thing with dates and time, decomposing them into trees, and likewise with geo coordinates in space. Or, we could map all of these structures onto a tree of its binary representation.
Now with these discrete elements as anchor points existing in multiple dimensions, define relations betweens them, and use the elements and relations to compose higher-level objects.
For example, in a property graph (https://github.com/tinkerpop/gremlin/wiki/Defining-a-Propert...), each vertex can contain key/value attributes, and traditionally when adding a new vertex, a vertex ID is assigned using a sequence generator. Edges are composed of two vertices, a label, optional key/value properties, and an edge ID is commonly assigned using a sequence generator. Each vertex and edge is traditionally stored as a row in the database, and traversing the graph is a process that begins with looking up the "start vertex", looking up its outgoing edges, traversing the outgoing edges to the incoming vertices, and continuing this process while using constraints to direct the traversal and filter out vertices and paths. For large graphs distributed across multiple machines, finding optimal ways to partition the graph across multiple machines is a challenge.
What if instead of identifying each vertex and edge by a meaningless integer, we uniquely define each vertex and edge by a compact representation of its constituent parts, like the cells of a body compose to form a person?
For example, consider the key/value properties in a vertex, such as:
{type: "person", handle: "espeed", location: "Dallas, TX", age: 38, updated: 20151205112207}
...using our discrete topology, each key/value pair is uniquely represented as a point in space, and the set of points are grouped together in a cell. Multiple cells compose together to form a cell complex (https://en.wikipedia.org/wiki/CW_complex). When the set points are in general position, there exists a unique Delaunay triangulation (https://en.wikipedia.org/wiki/Delaunay_triangulation).
Use Delaunay triangulation to encode a unique ID for each vertex, and then use the resulting vertex IDs, label, orientation, and optional key/value properties to compose edges. Edges then compose together to form a graph.
Here's the question I'm exploring: Can we encode a graph in such a way that traversing the graph is reduced to a geometric algorithm?