Re: Fast point matching algorithm

If you are working with discrete data spaces, i.e. if you can easily
make exact comparisons (example: data are strings or integers), you can
use algorithms from RDBMS indexing:

(1) use a hashing algorithm to produce "signatures" for all points, so
you can employ any single-value comparision method (instead of working
progressively for every dimension).
(2) organize the largest set (A) into a binary (or n-order) sorted tree
structure and iterate through all the members of the smallest set (B).

Since the total time complexity will be |B|*log(|A|) , you want to have
the largest set "inside" the log, i.e. organized as a sorted tree
structure.


--
Harris

.

Quantcast