Technological Innovation as an Evolutionary Process

Technological Innovation as an Evolutionary Process

On the keyless hash table

4/25/2004 11:43 AM

Additional discussion on “structural holonomy” -> .

A previous version of the note has been modified so as to focus only on how a set of atomic elements can be given a linear, or total order, similar to the order given by an index on the counting numbers. Then the occurrence, co-occurrences, of compounds made up of these atoms can be encoded into a key-less hash table. The procedure is likely the optimal way to encode ontology structures such as Orbs and RDF. A study of the Orb notational paper is likely to explain to most astute readers why this is so.

My notion of a key-less hash table is based on the simple treatment of an ASCII string as a base 64 number, and the use of the natural order on the counting numbers to place a fixed number of hash containers into memory. As far as I know, the combination of concepts leading me to think of the phrase “ hash table” was original to me, and first occurred in the year 2004.

Once one uses any order, including alphabetic order, then one can always answer the question, "is the data value in this set", in n or less "machine cycles" where 2 ⁿ > number of values in the set. If the answer is yes, one has a pointer to the data value.

The general concept is related to substructural elements, called atoms of categoricalAbstraction (cA) atoms, being composed using eventChemistries (eC) to organize data in a computer process. In general terms the set of atoms of an English language ASCII string are the 52 letters. Other language groups have different sets of letters. Ken Ewell’s underlying innovation is based on a mapping of alphabet characters, and patterns of alphabet characters, to semantic primitives. So in this case we also have a set of atoms, under 50 if I remember correctly, and these can be ordered as if counting numbers.

No meaning is given to the order, as this is simply a means to map things into a structural holonomy. The ordering of the atoms is then used to directly produce an ordering of the compounds whose compositions include atoms. The fundamental insight of positional notation is expressed in Hindu arithmetic dating back over three thousand years.

This insight was not seen in Roman numerals, and an importation of the innovation of Hindu, or Arabic, numbers was seen as the basis for European renaissance.

My technology, invented and made public domain in 2002, called SLIP (Shallow Link analysis Iterated scatter-gather and Parcelation), depends on addressing this "set membership" principle. I have coded it four ways.

1) The FoxPro Rushmore indexing technology is one of the best indexing technologies and is about 100 times slower on the same task than the key-less hash table.

2) The use of a Berkeley Hash Table management system was chosen by Nathan and I to avoid the use of this simple trick of regarding the ASCII string as a base 64 number, and I think the performance there, if tested would be about 10 times slower.

3) I asked Nathan to implement the Referential Information Base concept but use alphabetic order so that the data encoding is not dependant on third party software and does not treat the strings as numbers. We still have a key-less hash table, and in this case there is no infringement on the Hilbert engine patent. One simply uses the standard string compare in Perl.

4) A fourth implementation moves completely away from the notion of integers, into a theory of eventChemistry with categoricalAbstraction atoms defined by generalFramework theory. This generalizes the concept of a “binary” finite state machine to a system of “n-ary” finite state machines where the n varies and matches to a modular arithmetic that depends on the set of possible state transitions as observed empirically. In this case, the key-less hash table has a set of data values that are composed of a linear string of elementary symbols having an arbitrary, non-meaningful, order. The generalization from this point is natural and follows well-established pure mathematics. The implementation of these pure mathematical concepts is disclosed here at this time (4/25/2004 10:38 AM), so as to provide a public record.

The main issue is not the extra memory needed for hash tables over key-less hash tables.

Hash tables need about 150% the memory of key-less hash. The main issue is the hash function and the number of steps needed to compute the key. In the four implementations of a hash table, also referred to as a structural holonomy. My FoxPro implementation establishes a proof of principle for structural holonomy using classical database indexing. The second implementation establishes Ontology referential bases (Orbs) as standard hash tables. The third implementation uses a string comparison rather than a number comparison. The forth implementation simplifies the underlying concepts and re-expresses the notion of a linear order on a set of symbols and a positional notation that pushes up the property of linear order to a set of symbol aggregations.

And this is where we have as yet undisclosed by-passes and new provisional patents. As I file these provisional patents (at $80 per filing), a new area of pure mathematics is exposed. My moral grounding tells me that this mathematics should not be patentable, but my awareness of recent history tells me that the PTO does not agree and will likely award patents based on a complete filing, within a year, of the provisional patent filing.

The key-less hash table has no collisions, where two different values get mapped to the same container. The key-less hash table allocates only the containers that are actually needed to put data into. In my concept of a key-less hash table, the hash function is simply an overload of the ASCII string with a lookup table indicating any pre-selected ordering of the 64 characters (26+26 = 52 is sufficient.)

The separation of sub-structure and compositional structure from meaning is addressed in a series of beads in the graphical representation of human knowledge bead thread.

[1] [2] [3] [4] [5]

An additional innovation, beyond the simple key-less hash table, is based on the modulus function n mod m. The modulus function returns the residue left over after division of one integer by another integer. The modulus function was studied by the ancient Greeks and is the foundation for much of elementary number theory.

This is where the pure mathematics is. In this new application of elementary number theory, one gets the innovations that very few have suggested, Zenkin

http://www.ontologystream.com/IRRTest/Evaluation/ARLReport.htm

and a few others have worked in related areas.

The most powerful design principles will be those that are based on exceedingly simple steps, and design principles that need to be transparent to the user.

The powerful conceptualization properties of the CoreSystem’s Cubicon language might be combined by deep insights on the nature of computing. The inventory of all categories of software patents might then be compared with basic designs based on Cubicon design elements. This is the true "Next Step" envisioned by Steve Jobs and others in the development of NextStep and its Interface builder.

Nathan and I are addressing the development of key-less hash table ontology and data schema management systems that have simple and powerful design principles.

The goal is a new Peer-to-Peer Orb system.