Memory Map Implementation

A "memory map" is a collection of vectors with normalized factors. It may go by different names, such as "Self-organizing Maps (SOMS)", and variations on this theme are common in AI and neural research. The question at hand is about making such algorithms more efficient.

Here is an example map with a zero-to-one normalization range that a space probe may use as it samples planets:

• brightness (reflectivity or albido) - 0=dark, 0.5=grey, 1.0=white
• absolute brightness - 0 is dark and 1 is say surface of sun. A log scale would be used.
• variability of planet image(s) - 0=smooth, 0.5=medium variations, 1=full contrast (black and white only)
• Air pressure - log scale from 0 to 1, zero being empty space pressure, and 1 perhaps being threashold of probe. An expendable sub-probe may be needed for this measurement since gas giants won't let a probe come back out.
• Oxegen amount - log scale (0 to 1) - Note that percentage might not be sensative enough to low amounts, thus we may want to stretch the lower-end using a reverse log scale or the like.
• Hard surface detected - 0=no surface detected, 0.5=mushy-or-soft, 1=hard surface

So we get a list of 6 measurements. Now suppose we had a database of planets in the galaxy. We could use probe samples to guess which planet it landed on. The basic algorithm to find the closest match is:

  s = getSampleVector();
  best_sample = blank;   // initialize
  min_diff = 999;  
  for p = each_planet_in_galaxy() {
     diff = abs(p1-s1) + abs(p2-s2) ... + abs(p6-s6);
     if (diff < min_diff) {
        best_sample = p;
        min_diff = diff;
     }
  }
  print("Best matching vector: " . showV(best_sample));

A fancier version would show multiple top-ranking matches, something like this:

  Rank Diff         Sample              Planet
  -----------------------------------------------------
  1    0.25  (0.25,0.52,0.98,...) (0.26,0.50,0.95,...)
  2    0.30  (0.25,0.52,0.98,...) (0.24,0.58,0.93,...)
  3    0.32  (0.25,0.52,0.98,...) (0.15,0.61,0.91,...)
  4    0.40  etc...

The question I have is, what kind of algorithms can be used to speed up the matching/scoring process such that one does not have to do a sequential search? Some of the simplistic approaches I have thought of (eg. index strings) tend to weigh some factors heavier than others, which is not what we want.

Notes

• For descrete categories, such as clothing (shirts, pants, socks, etc.), one could adjust it so that a match would be 1 and a non-match would be zero. It may complicate our storing process, but not necessarily our scoring algorithm (once translation is done).

• Variations put different weights on different factors. Here is an example where w[n] is the weighting factor:

      diff = w1*abs(p1-s1) + w2*abs(p2-s2) ... + w6*abs(p6-s6)

---

CategoryArtificialIntelligence, CategoryPerformance