Package smile.neighbor

Class LinearSearch<K,V>

java.lang.Object
smile.neighbor.LinearSearch<K,V>
Type Parameters:
K - the type of keys.
V - the type of associated objects.
All Implemented Interfaces:
Serializable, KNNSearch<K,V>, RNNSearch<K,V>
public class LinearSearch<K,V> extends Object implements KNNSearch<K,V>, RNNSearch<K,V>, Serializable
Brute force linear nearest neighbor search. This simplest solution computes the distance from the query point to every other point in the database, keeping track of the "best so far". There are no search data structures to maintain, so linear search has no space complexity beyond the storage of the database. Although it is very simple, naive search outperforms space partitioning approaches (e.g. K-D trees) on higher dimensional spaces.

By default, the query object (reference equality) is excluded from the neighborhood. Note that you may observe weird behavior with String objects. JVM will pool the string literal objects. So the below variables String a = "ABC"; String b = "ABC"; String c = "AB" + "C"; are actually equal in reference test a == b == c. With toy data that you type explicitly in the code, this will cause problems. Fortunately, the data would be read from secondary storage in production.

See Also:

  • Constructor Details

    • LinearSearch

      public LinearSearch(K[] keys, V[] data, Distance<K> distance)
      Constructor.
      Parameters:
      keys - the data keys.
      data - the data objects.
      distance - the distance function.

    • LinearSearch

      public LinearSearch(List<K> keys, List<V> data, Distance<K> distance)
      Constructor.
      Parameters:
      keys - the data keys.
      data - the data objects.
      distance - the distance function.

    • LinearSearch

      public LinearSearch(V[] data, Distance<K> distance, Function<V,K> key)
      Constructor.
      Parameters:
      data - the data objects.
      distance - the distance function.
      key - the lambda to extra the key from data object.

    • LinearSearch

      public LinearSearch(List<V> data, Distance<K> distance, Function<V,K> key)
      Constructor.
      Parameters:
      data - the data objects.
      distance - the distance function.
      key - the lambda to extra the key from data object.

  • Method Details

    • of

      public static <T> LinearSearch<T,T> of(T[] data, Distance<T> distance)
      Return linear nearest neighbor search.
      Type Parameters:
      T - the type of keys and values.
      Parameters:
      data - the data objects, which are also used as key.
      distance - the distance function.
      Returns:
      Linear nearest neighbor search.

    • of

      public static <T> LinearSearch<T,T> of(List<T> data, Distance<T> distance)
      Return linear nearest neighbor search.
      Type Parameters:
      T - the type of keys and values.
      Parameters:
      data - the data objects, which are also used as key.
      distance - the distance function.
      Returns:
      Linear nearest neighbor search.

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • nearest

      public Neighbor<K,V> nearest(K q)
      Description copied from interface: KNNSearch
      Returns the nearest neighbor. In machine learning, we often build a nearest neighbor search data structure, and then search with object in the same dataset. The object itself is of course the nearest one with distance 0. Since this is generally useless, we check the reference during the search and excludes the query object from the results.
      Specified by:
      nearest in interface KNNSearch<K,V>
      Parameters:
      q - the query key.
      Returns:
      the nearest neighbor

    • search

      public Neighbor<K,V>[] search(K q, int k)
      Description copied from interface: KNNSearch
      Retrieves the k nearest neighbors to the query key.
      Specified by:
      search in interface KNNSearch<K,V>
      Parameters:
      q - the query key.
      k - the number of nearest neighbors to search for.
      Returns:
      the k nearest neighbors

    • search

      public void search(K q, double radius, List<Neighbor<K,V>> neighbors)
      Description copied from interface: RNNSearch
      Retrieves the neighbors in a fixed radius of query object, i.e. d(q, v) <= radius.
      Specified by:
      search in interface RNNSearch<K,V>
      Parameters:
      q - the query key.
      radius - the radius of search range from target.
      neighbors - the list to store found neighbors on output.