Tuesday, November 8, 2011

G pointers, local

In nested ort the nodes have local pointers, the real link, actually. It has an MSB part counting sequential order and a LSB part covering sequential links. SImplifies everything, the pointer becomes a link property.

Where Google had to mangle a row column indicator or compact matrices, we have to mangle a sequential level and a sibling level. We have to make a formal pointer arithmetic that makes efficient selects on the pointer values.

Thus when building Gout, a push on the Gout graph is either a sequential push or a sibling push. The pointer arithmetic is a bit different. Maintaining the pointers on G1 and G2 pose similar problems. So I introduce pointer math:

Push sequential: MSB++, LSB=0
Push Sibling MSB no change,LSB++
When G1 or G2 deplete a descending branch, an jump over to the nest sibling, then Gout as the pointer set up for it to also track back, and jump over.

Makes for quick scans on collective set routines, especially if we can build indices on key vaues of MSB inthe pointer. That makes for very fast dictionary look ups. How do we introduce indexing, hmmm... OK, solution for version one. Indexing is an internal property, is a database is index, the engine knows that and utilizes the index on MSB. This is mainly for dictionary lists, so we can presumed dictionaries were dumped into the World of G with intelligence, outside the programming environment. The engine can figure it out.

Speaking of MSB and LSB. LSB, simply is the incremental count of the record ID, MSB is the rank of the graph. But we now that our most efficient encoding will make the graph node count go as Nlog(N), N being the rank. So ous MSB,LSB arithmetic meet Benford's law, correct? We have natural optimizing parameters to encoding of ontologies.

No comments: