class_docstr: NNDescent for fast approximate nearest neighbor queries. NNDescent is
  very flexible and supports a wide variety of distances, including
  non-metric distances. NNDescent also scales well against high dimensional
  graph_data in many cases. This implementation provides a straightfoward
  interface, with access to some tuning parameters.
  
  Parameters
  ----------
  data: array of shape (n_samples, n_features)
      The training graph_data set to find nearest neighbors in.
  
  metric: string or callable (optional, default='euclidean')
      The metric to use for computing nearest neighbors. If a callable is
      used it must be a numba njit compiled function. Supported metrics
      include:
          * euclidean
          * manhattan
          * chebyshev
          * minkowski
          * canberra
          * braycurtis
          * mahalanobis
          * wminkowski
          * seuclidean
          * cosine
          * correlation
          * haversine
          * hamming
          * jaccard
          * dice
          * russelrao
          * kulsinski
          * rogerstanimoto
          * sokalmichener
          * sokalsneath
          * yule
          * hellinger
          * wasserstein-1d
      Metrics that take arguments (such as minkowski, mahalanobis etc.)
      can have arguments passed via the metric_kwds dictionary. At this
      time care must be taken and dictionary elements must be ordered
      appropriately; this will hopefully be fixed in the future.
  
  metric_kwds: dict (optional, default {})
      Arguments to pass on to the metric, such as the ``p`` value for
      Minkowski distance.
  
  n_neighbors: int (optional, default=30)
      The number of neighbors to use in k-neighbor graph graph_data structure
      used for fast approximate nearest neighbor search. Larger values
      will result in more accurate search results at the cost of
      computation time.
  
  n_trees: int (optional, default=None)
      This implementation uses random projection forests for initializing the index
      build process. This parameter controls the number of trees in that forest. A
      larger number will result in more accurate neighbor computation at the cost
      of performance. The default of None means a value will be chosen based on the
      size of the graph_data.
  
  leaf_size: int (optional, default=None)
      The maximum number of points in a leaf for the random projection trees.
      The default of None means a value will be chosen based on n_neighbors.
  
  pruning_degree_multiplier: float (optional, default=1.5)
      How aggressively to prune the graph. Since the search graph is undirected
      (and thus includes nearest neighbors and reverse nearest neighbors) vertices
      can have very high degree -- the graph will be pruned such that no
      vertex has degree greater than
      ``pruning_degree_multiplier * n_neighbors``.
  
  diversify_prob: float (optional, default=1.0)
      The search graph get "diversified" by removing potentially unnecessary
      edges. This controls the volume of edges removed. A value of 0.0 ensures
      that no edges get removed, and larger values result in significantly more
      aggressive edge removal. A value of 1.0 will prune all edges that it can.
  
  n_search_trees: int (optional, default=1)
      The number of random projection trees to use in initializing searching or
      querying.
  
      .. deprecated:: 0.5.5
  
  tree_init: bool (optional, default=True)
      Whether to use random projection trees for initialization.
  
  init_graph: np.ndarray (optional, default=None)
      2D array of indices of candidate neighbours of the shape
      (data.shape[0], n_neighbours). If the j-th neighbour of the i-th
      instances is unknown, use init_graph[i, j] = -1
  
  init_dist: np.ndarray (optional, default=None)
      2D array with the same shape as init_graph,
      such that metric(data[i], data[init_graph[i, j]]) equals
      init_dist[i, j]
  
  random_state: int, RandomState instance or None, optional (default: None)
      If int, random_state is the seed used by the random number generator;
      If RandomState instance, random_state is the random number generator;
      If None, the random number generator is the RandomState instance used
      by `np.random`.
  
  algorithm: string (optional, default='standard')
      This implementation provides an alternative algorithm for
      construction of the k-neighbors graph used as a search index. The
      alternative algorithm can be fast for large ``n_neighbors`` values.
      The``'alternative'`` algorithm has been deprecated and is no longer
      available.
  
  low_memory: boolean (optional, default=True)
      Whether to use a lower memory, but more computationally expensive
      approach to index construction.
  
  max_candidates: int (optional, default=None)
      Internally each "self-join" keeps a maximum number of candidates (
      nearest neighbors and reverse nearest neighbors) to be considered.
      This value controls this aspect of the algorithm. Larger values will
      provide more accurate search results later, but potentially at
      non-negligible computation cost in building the index. Don't tweak
      this value unless you know what you're doing.
  
  max_rptree_depth: int (optional, default=100)
      Maximum depth of random projection trees. Increasing this may result in a
      richer, deeper random projection forest, but it may be composed of many
      degenerate branches. Increase leaf_size in order to keep shallower, wider
      nondegenerate trees. Such wide trees, however, may yield poor performance
      of the preparation of the NN descent.
  
  n_iters: int (optional, default=None)
      The maximum number of NN-descent iterations to perform. The
      NN-descent algorithm can abort early if limited progress is being
      made, so this only controls the worst case. Don't tweak
      this value unless you know what you're doing. The default of None means
      a value will be chosen based on the size of the graph_data.
  
  delta: float (optional, default=0.001)
      Controls the early abort due to limited progress. Larger values
      will result in earlier aborts, providing less accurate indexes,
      and less accurate searching. Don't tweak this value unless you know
      what you're doing.
  
  n_jobs: int or None, optional (default=None)
      The number of parallel jobs to run for neighbors index construction.
      ``None`` means 1 unless in a :obj:`joblib.parallel_backend` context.
      ``-1`` means using all processors.
  
  compressed: bool (optional, default=False)
      Whether to prune out data not needed for searching the index. This will
      result in a significantly smaller index, particularly useful for saving,
      but will remove information that might otherwise be useful.
  
  parallel_batch_queries: bool (optional, default=False)
      Whether to use parallelism of batched queries. This can be useful for large
      batches of queries on multicore machines, but results in performance degradation
      for single queries, so is poor for streaming use.
  
  verbose: bool (optional, default=False)
      Whether to print status graph_data during the computation.
class_docstr_tok: ["NNDescent","for","fast","approximate","nearest","neighbor","queries",".","NNDescent","is","very","flexible","and","supports","a","wide","variety","of","distances",",","including","non-metric","distances",".","NNDescent","also","scales","well","against","high","dimensional","graph_data","in","many","cases",".","This","implementation","provides","a","straightfoward","interface",",","with","access","to","some","tuning","parameters",".","Parameters","--","--","--","--","--","data",":","array","of","shape","(","n_samples",",","n_features",")","The","training","graph_data","set","to","find","nearest","neighbors","in",".","metric",":","string","or","callable","(","optional",",","default='euclidean","'",")","The","metric","to","use","for","computing","nearest","neighbors",".","If","a","callable","is","used","it","must","be","a","numba","njit","compiled","function",".","Supported","metrics","include",":","*","euclidean","*","manhattan","*","chebyshev","*","minkowski","*","canberra","*","braycurtis","*","mahalanobis","*","wminkowski","*","seuclidean","*","cosine","*","correlation","*","haversine","*","hamming","*","jaccard","*","dice","*","russelrao","*","kulsinski","*","rogerstanimoto","*","sokalmichener","*","sokalsneath","*","yule","*","hellinger","*","wasserstein-1d","Metrics","that","take","arguments","(","such","as","minkowski",",","mahalanobis","etc",".",")","can","have","arguments","passed","via","the","metric_kwds","dictionary",".","At","this","time","care","must","be","taken","and","dictionary","elements","must","be","ordered","appropriately",";","this","will","hopefully","be","fixed","in","the","future",".","metric_kwds",":","dict","(","optional",",","default","{","}",")","Arguments","to","pass","on","to","the","metric",",","such","as","the","``","p","``","value","for","Minkowski","distance",".","n_neighbors",":","int","(","optional",",","default=30",")","The","number","of","neighbors","to","use","in","k-neighbor","graph","graph_data","structure","used","for","fast","approximate","nearest","neighbor","search",".","Larger","values","will","result","in","more","accurate","search","results","at","the","cost","of","computation","time",".","n_trees",":","int","(","optional",",","default=None",")","This","implementation","uses","random","projection","forests","for","initializing","the","index","build","process",".","This","parameter","controls","the","number","of","trees","in","that","forest",".","A","larger","number","will","result","in","more","accurate","neighbor","computation","at","the","cost","of","performance",".","The","default","of","None","means","a","value","will","be","chosen","based","on","the","size","of","the","graph_data",".","leaf_size",":","int","(","optional",",","default=None",")","The","maximum","number","of","points","in","a","leaf","for","the","random","projection","trees",".","The","default","of","None","means","a","value","will","be","chosen","based","on","n_neighbors",".","pruning_degree_multiplier",":","float","(","optional",",","default=1.5",")","How","aggressively","to","prune","the","graph",".","Since","the","search","graph","is","undirected","(","and","thus","includes","nearest","neighbors","and","reverse","nearest","neighbors",")","vertices","can","have","very","high","degree","--","the","graph","will","be","pruned","such","that","no","vertex","has","degree","greater","than","``","pruning_degree_multiplier","*","n_neighbors","``",".","diversify_prob",":","float","(","optional",",","default=1.0",")","The","search","graph","get","``","diversified","''","by","removing","potentially","unnecessary","edges",".","This","controls","the","volume","of","edges","removed",".","A","value","of","0.0","ensures","that","no","edges","get","removed",",","and","larger","values","result","in","significantly","more","aggressive","edge","removal",".","A","value","of","1.0","will","prune","all","edges","that","it","can",".","n_search_trees",":","int","(","optional",",","default=1",")","The","number","of","random","projection","trees","to","use","in","initializing","searching","or","querying",".","..","deprecated",":",":","0.5.5","tree_init",":","bool","(","optional",",","default=True",")","Whether","to","use","random","projection","trees","for","initialization",".","init_graph",":","np.ndarray","(","optional",",","default=None",")","2D","array","of","indices","of","candidate","neighbours","of","the","shape","(","data.shape","[","0","]",",","n_neighbours",")",".","If","the","j-th","neighbour","of","the","i-th","instances","is","unknown",",","use","init_graph","[","i",",","j","]","=","-1","init_dist",":","np.ndarray","(","optional",",","default=None",")","2D","array","with","the","same","shape","as","init_graph",",","such","that","metric","(","data","[","i","]",",","data","[","init_graph","[","i",",","j","]","]",")","equals","init_dist","[","i",",","j","]","random_state",":","int",",","RandomState","instance","or","None",",","optional","(","default",":","None",")","If","int",",","random_state","is","the","seed","used","by","the","random","number","generator",";","If","RandomState","instance",",","random_state","is","the","random","number","generator",";","If","None",",","the","random","number","generator","is","the","RandomState","instance","used","by","`","np.random","`",".","algorithm",":","string","(","optional",",","default='standard","'",")","This","implementation","provides","an","alternative","algorithm","for","construction","of","the","k-neighbors","graph","used","as","a","search","index",".","The","alternative","algorithm","can","be","fast","for","large","``","n_neighbors","``","values",".","The","``","'alternative","'","``","algorithm","has","been","deprecated","and","is","no","longer","available",".","low_memory",":","boolean","(","optional",",","default=True",")","Whether","to","use","a","lower","memory",",","but","more","computationally","expensive","approach","to","index","construction",".","max_candidates",":","int","(","optional",",","default=None",")","Internally","each","``","self-join","''","keeps","a","maximum","number","of","candidates","(","nearest","neighbors","and","reverse","nearest","neighbors",")","to","be","considered",".","This","value","controls","this","aspect","of","the","algorithm",".","Larger","values","will","provide","more","accurate","search","results","later",",","but","potentially","at","non-negligible","computation","cost","in","building","the","index",".","Do","n't","tweak","this","value","unless","you","know","what","you","'re","doing",".","max_rptree_depth",":","int","(","optional",",","default=100",")","Maximum","depth","of","random","projection","trees",".","Increasing","this","may","result","in","a","richer",",","deeper","random","projection","forest",",","but","it","may","be","composed","of","many","degenerate","branches",".","Increase","leaf_size","in","order","to","keep","shallower",",","wider","nondegenerate","trees",".","Such","wide","trees",",","however",",","may","yield","poor","performance","of","the","preparation","of","the","NN","descent",".","n_iters",":","int","(","optional",",","default=None",")","The","maximum","number","of","NN-descent","iterations","to","perform",".","The","NN-descent","algorithm","can","abort","early","if","limited","progress","is","being","made",",","so","this","only","controls","the","worst","case",".","Do","n't","tweak","this","value","unless","you","know","what","you","'re","doing",".","The","default","of","None","means","a","value","will","be","chosen","based","on","the","size","of","the","graph_data",".","delta",":","float","(","optional",",","default=0.001",")","Controls","the","early","abort","due","to","limited","progress",".","Larger","values","will","result","in","earlier","aborts",",","providing","less","accurate","indexes",",","and","less","accurate","searching",".","Do","n't","tweak","this","value","unless","you","know","what","you","'re","doing",".","n_jobs",":","int","or","None",",","optional","(","default=None",")","The","number","of","parallel","jobs","to","run","for","neighbors","index","construction",".","``","None","``","means","1","unless","in","a",":","obj",":","`","joblib.parallel_backend","`","context",".","``","-1","``","means","using","all","processors",".","compressed",":","bool","(","optional",",","default=False",")","Whether","to","prune","out","data","not","needed","for","searching","the","index",".","This","will","result","in","a","significantly","smaller","index",",","particularly","useful","for","saving",",","but","will","remove","information","that","might","otherwise","be","useful",".","parallel_batch_queries",":","bool","(","optional",",","default=False",")","Whether","to","use","parallelism","of","batched","queries",".","This","can","be","useful","for","large","batches","of","queries","on","multicore","machines",",","but","results","in","performance","degradation","for","single","queries",",","so","is","poor","for","streaming","use",".","verbose",":","bool","(","optional",",","default=False",")","Whether","to","print","status","graph_data","during","the","computation","."]
code: def _init_sparse_search_function(self):
      if self.verbose:
          print(ts(), "Building and compiling sparse search function")
  
      if self.tree_init:
          tree_hyperplanes = self._search_forest[0].hyperplanes
          tree_offsets = self._search_forest[0].offsets
          tree_indices = self._search_forest[0].indices
          tree_children = self._search_forest[0].children
  
          @numba.njit(
              [
                  numba.types.Array(
                      numba.types.int32, 1, "C", readonly=True
                  )(
                      numba.types.Array(
                          numba.types.int32, 1, "C", readonly=True
                      ),
                      numba.types.Array(
                          numba.types.float32, 1, "C", readonly=True
                      ),
                      numba.types.Array(
                          numba.types.int64, 1, "C", readonly=False
                      ),
                  )
              ],
              locals={
                  "node": numba.types.uint32,
                  "side": numba.types.boolean,
              },
          )
          def sparse_tree_search_closure(
              point_inds, point_data, rng_state
          ):
              node = 0
              while tree_children[node, 0] > 0:
                  side = sparse_select_side(
                      tree_hyperplanes[node],
                      tree_offsets[node],
                      point_inds,
                      point_data,
                      rng_state,
                  )
                  if side == 0:
                      node = tree_children[node, 0]
                  else:
                      node = tree_children[node, 1]
  
              return -tree_children[node]
  
          self._tree_search = sparse_tree_search_closure
      else:
  
          @numba.njit()
          def sparse_tree_search_closure(
              point_inds, point_data, rng_state
          ):
              return (0, 0)
  
          self._tree_search = sparse_tree_search_closure
          tree_indices = np.zeros(1, dtype=np.int64)
  
      from pynndescent.distances import (
          alternative_dot,
          alternative_cosine,
      )
  
      data_inds = self._raw_data.indices
      data_indptr = self._raw_data.indptr
      data_data = self._raw_data.data
      indptr = self._search_graph.indptr
      indices = self._search_graph.indices
      dist = self._distance_func
      n_neighbors = self.n_neighbors
      parallel_search = self.parallel_batch_queries
  
      @numba.njit(
          fastmath=True,
          locals={
              "current_query": numba.types.float32[::1],
              "i": numba.types.uint32,
              "heap_priorities": numba.types.float32[::1],
              "heap_indices": numba.types.int32[::1],
              "candidate": numba.types.int32,
              "d": numba.types.float32,
              "visited": numba.types.uint8[::1],
              "indices": numba.types.int32[::1],
              "indptr": numba.types.int32[::1],
              "data": numba.types.float32[:, ::1],
              "heap_size": numba.types.int16,
              "distance_scale": numba.types.float32,
              "seed_scale": numba.types.float32,
          },
          parallel=self.parallel_batch_queries,
      )
      def search_closure(
          query_inds,
          query_indptr,
          query_data,
          k,
          epsilon,
          visited,
          rng_state,
      ):
          n_query_points = query_indptr.shape[0] - 1
          n_index_points = data_indptr.shape[0] - 1
          result = make_heap(n_query_points, k)
          distance_scale = 1.0 + epsilon
          internal_rng_state = np.copy(rng_state)
  
          for i in numba.prange(n_query_points):
              # Avoid races on visited if parallel
              if parallel_search:
                  visited_nodes = np.zeros_like(visited)
              else:
                  visited_nodes = visited
                  visited_nodes[:] = 0
  
              current_query_inds = query_inds[
                  query_indptr[i] : query_indptr[i + 1]
              ]
              current_query_data = query_data[
                  query_indptr[i] : query_indptr[i + 1]
              ]
  
              if dist == alternative_dot or dist == alternative_cosine:
                  norm = np.sqrt((current_query_data**2).sum())
                  if norm > 0.0:
                      current_query_data = current_query_data / norm
                  else:
                      continue
  
              heap_priorities = result[1][i]
              heap_indices = result[0][i]
              seed_set = [
                  (np.float32(np.inf), np.int32(-1)) for j in range(0)
              ]
              heapq.heapify(seed_set)
  
              ############ Init ################
              index_bounds = sparse_tree_search_closure(
                  current_query_inds,
                  current_query_data,
                  internal_rng_state,
              )
              candidate_indices = tree_indices[
                  index_bounds[0] : index_bounds[1]
              ]
  
              n_initial_points = candidate_indices.shape[0]
              n_random_samples = min(k, n_neighbors) - n_initial_points
  
              for j in range(n_initial_points):
                  candidate = candidate_indices[j]
  
                  from_inds = data_inds[
                      data_indptr[candidate] : data_indptr[
                          candidate + 1
                      ]
                  ]
                  from_data = data_data[
                      data_indptr[candidate] : data_indptr[
                          candidate + 1
                      ]
                  ]
  
                  d = np.float32(
                      dist(
                          from_inds,
                          from_data,
                          current_query_inds,
                          current_query_data,
                      )
                  )
                  # indices are guaranteed different
                  simple_heap_push(
                      heap_priorities, heap_indices, d, candidate
                  )
                  heapq.heappush(seed_set, (d, candidate))
                  mark_visited(visited_nodes, candidate)
  
              if n_random_samples > 0:
                  for j in range(n_random_samples):
                      candidate = np.int32(
                          np.abs(tau_rand_int(internal_rng_state))
                          % n_index_points
                      )
                      if (
                          has_been_visited(visited_nodes, candidate)
                          == 0
                      ):
                          from_inds = data_inds[
                              data_indptr[candidate] : data_indptr[
                                  candidate + 1
                              ]
                          ]
                          from_data = data_data[
                              data_indptr[candidate] : data_indptr[
                                  candidate + 1
                              ]
                          ]
  
                          d = np.float32(
                              dist(
                                  from_inds,
                                  from_data,
                                  current_query_inds,
                                  current_query_data,
                              )
                          )
  
                          simple_heap_push(
                              heap_priorities,
                              heap_indices,
                              d,
                              candidate,
                          )
                          heapq.heappush(seed_set, (d, candidate))
                          mark_visited(visited_nodes, candidate)
  
              ############ Search ##############
              distance_bound = distance_scale * heap_priorities[0]
  
              # Find smallest seed point
              d_vertex, vertex = heapq.heappop(seed_set)
  
              while d_vertex < distance_bound:
                  for j in range(indptr[vertex], indptr[vertex + 1]):
                      candidate = indices[j]
  
                      if (
                          has_been_visited(visited_nodes, candidate)
                          == 0
                      ):
                          mark_visited(visited_nodes, candidate)
  
                          from_inds = data_inds[
                              data_indptr[candidate] : data_indptr[
                                  candidate + 1
                              ]
                          ]
                          from_data = data_data[
                              data_indptr[candidate] : data_indptr[
                                  candidate + 1
                              ]
                          ]
  
                          d = np.float32(
                              dist(
                                  from_inds,
                                  from_data,
                                  current_query_inds,
                                  current_query_data,
                              )
                          )
  
                          if d < distance_bound:
                              simple_heap_push(
                                  heap_priorities,
                                  heap_indices,
                                  d,
                                  candidate,
                              )
                              heapq.heappush(seed_set, (d, candidate))
                              # Update bound
                              distance_bound = (
                                  distance_scale * heap_priorities[0]
                              )
  
                  # find new smallest seed point
                  if len(seed_set) == 0:
                      break
                  else:
                      d_vertex, vertex = heapq.heappop(seed_set)
  
          return result
  
      self._search_function = search_closure
      if hasattr(deheap_sort, "py_func"):
          self._deheap_function = numba.njit(
              parallel=self.parallel_batch_queries
          )(deheap_sort.py_func)
      else:
          self._deheap_function = deheap_sort
  
      # Force compilation of the search function (hardcoded k, epsilon)
      query_data = self._raw_data[:1]
      inds, dists, _ = self._search_function(
          query_data.indices,
          query_data.indptr,
          query_data.data,
          5,
          0.0,
          self._visited,
          self.search_rng_state,
      )
      _ = self._deheap_function(inds, dists)
  
imports: from warnings import warn
  import numba
  import numpy
  from sklearn.utils import check_random_state, check_array
  from sklearn.preprocessing import normalize
  from sklearn.base import BaseEstimator, TransformerMixin
  from scipy.sparse import csr_matrix, coo_matrix, isspmatrix_csr, vstack, issparse
  import heapq
  import pynndescent.sparse
  import pynndescent.sparse_nndescent
  import pynndescent.distances
  from pynndescent.utils import tau_rand_int, tau_rand, make_heap, deheap_sort, new_build_candidates, ts, simple_heap_push, checked_flagged_heap_push, has_been_visited, mark_visited, apply_graph_updates_high_memory, apply_graph_updates_low_memory, initalize_heap_from_graph_indices, initalize_heap_from_graph_indices_and_distances, sparse_initalize_heap_from_graph_indices
  from pynndescent.rp_trees import make_forest, rptree_leaf_array, convert_tree_format, FlatTree, denumbaify_tree, renumbaify_tree, select_side, sparse_select_side, score_linked_tree
label_desc: Use image node_id 6 for calling the NNDescent obj's underlying member method code with example usage: obj._init_sparse_search_function() and returns: result, unknown, int,  int