Retrieving data from file-systems or databases requires 2 modes; exact-match and near-match. Exact-match retrieves data based on a key. An example is locating a word in a dictionary (e.g. "buffage"; it either exists or it does not). Near-match optionally includes the previous or next key (e.g. "buff" or "buffalo"). NoChop and BinaryChop support both modes.

BinaryChop (aka BinarySearch) was chosen to race against NoChop as it is viewed as being the quickest current data-retrieval algorithm. AGD Research also considers it to be a worthy competitor of NoChop; its' simplicity-and-elegance are awe-inspiring. It has less than 30 lines of code and uses miniscule memory.

BinaryChop works by chopping a sorted list of keys into 2 equal-sized half-lists and establishing if the search key is in the first or second half-list, and retains that half before discarding the other. It then keeps repeating this process until the search-key is located or not (download the white-paper for details of NoChop and QuickSort from the Downloads web-page).

The accompanying spreadsheet shows the results of the 2 algorithms retrieving 10k passwords and 23k world-cities, and new tabs and data-sets can easily be created. NoChop's supremacy is already at +350% (4.5 times faster = Mach 4.5). and this is with first-generation, non-optimized code (BinaryChop has benefitted from over 60 years of "tweaking").

The NoChop/STree combination is ideal for massive parallelization, and the accompanying flow-diagram on shows one approach. A set of 256 STrees is pre-built containing the data and a simple triage would interrogate the appropriate one based on the first ascii-character of the search-key. A smart one would balance load on a configurable number of processors.

This approach lends itself to augmenting and/or replacing existing ones used to support the back-end of online-and-mobile retail and similar applications. Both SQL (relational) and NoSQL (distributed in-memory) databases can easily incorporate the NoChop/STree combination in their existing architectures.

Retrieve imageRetrieve image