Matched-field processing speedup through fast nearest-neighbor search in excitation space.
Pierre Zakarauskas, John M. Ozard, Don G. Berryman, Mike Wilmut · The Journal of the Acoustical Society of America · 1992
By casting the matching portion of the MFP problem into a nearest-neighbor search, one may apply the fast nearest-neighbor search algorithm to obtain potentially considerable speedups. This algorithm makes it possible to find the replica closest to a test pattern (peak of the Bartlett processor output), in a time which is asymptotically constant with the number of replicas. The algorithm first partitions the excitation space, and finds which partition each of the replicas falls into. When a test pattern is supplied, one compares it to all replicas within the partitions which are within a given distance R to the test pattern. If the distance d between the closest replica found during the first pass and the test pattern is less than R, then the search stops. If not, then a second pass is done using d as a search parameter to select partitions. This algorithm guarantees that the nearest neighbor is found. The mean number of operations done to find the nearest neighbor is presented as a function of the density of patterns per partition and the dimensionality of the excitation space. A global minimum is shown to exist for the mean number of operations at a partition size corresponding to slightly less than one replica per partition.