class_docstr: Sliding WIndow-based Nearest Neighbor (SWINN) search using Graphs.
  
  Extends the NNDescent algorithm[^1] to handle vertex addition and removal in a FIFO data
  ingestion policy. SWINN builds and keeps a directed graph where edges connect the nearest
  neighbors. Any distance metric can be used to build the graph. By using a directed graph,
  the user must set the desired number of neighbors. More neighbors imply more accurate
  search queries at the cost of increased running time and memory usage. Note that although
  the number of directed neighbors is limited by the user, there is no direct control on the
  number of reverse neighbors, i.e., the number of vertices that have an edge to a given vertex.
  
  The basic idea of SWINN and NNDescent is that "the neighbor of my neighbors might as well be
  my neighbor". Hence, the connections are constantly revisited to improve the graph structure.
  The algorithm for creating and maintaining the search graph can be described
  in general lines as follows:
  
  * Start with a random neighborhood graph;
  
  * For each node in the search graph: refine the current neighborhood by checking if there
  are better neighborhood options among the neighbors of the current neighbors;
  
  * If the total number of neighborhood changes is smaller than a given stopping criterion, then stop.
  
  SWINN adds strategies to remove vertices from the search graph and pruning redundant edges. SWINN is
  more efficient when the selected `maxlen` is greater than 500. For small sized data windows, using
  the lazy/exhaustive search, i.e., `neighbors.LazySearch` might be a better idea.
  
  Parameters
  ----------
  graph_k
      The maximum number of direct nearest neighbors each node has.
  maxlen
      The maximum size of the data buffer.
  warm_up
      How many data instances to observe before starting the search graph.
  dist_func
      The distance function used to compare two items. If not set, use the Minkowski distance
      with `p=2`.
  max_candidates
      The maximum number of vertices to consider when performing local neighborhood joins. If not set
      SWINN will use `min(50, max(50, self.graph_k))`.
  delta
      Early stop parameter for the neighborhood refinement procedure. NNDescent will stop running
      if the maximum number of iterations is reached or the number of edge changes after an iteration
      is smaller than or equal to `delta * graph_k * n_nodes`. In the last expression, `n_nodes`
      refers to the number of graph nodes involved in the (local) neighborhood refinement.
  prune_prob
      The probability of removing redundant edges. Must be between `0` and `1`. If set to zero,
      no edge will be pruned. When set to one, every potentially redundant edge will be dropped.
  n_iters
      The maximum number of NNDescent iterations to perform to refine the search index.
  seed
      Random seed for reproducibility.
  
  Notes
  -----
  There is an accuracy/speed trade-off between `graph_k` and `sample_rate`. To ensure a single
  connected component, and thus an effective search index, one can increase `graph_k`. The
  `connectivity` method is a helper to determine whether the search index has a single connected component.
  However, search accuracy might come at the cost of increased memory usage and slow processing. To alleviate
  that, one can rely on decreasing the `sample_rate` to avoid exploring all the undirected edges of a node
  during search queries and local graph refinements. Moreover, the edge pruning procedures also help
  decreasing the computational costs. Note that, anything that limits the number of explored neighbors or
  prunes edges might have a negative impact on search accuracy.
  
  References
  ----------
  [^1]: Dong, W., Moses, C., & Li, K. (2011, March). Efficient k-nearest neighbor graph construction for
  generic similarity measures. In Proceedings of the 20th international conference on World wide web (pp. 577-586).
class_docstr_tok: ["Sliding","WIndow-based","Nearest","Neighbor","(","SWINN",")","search","using","Graphs",".","Extends","the","NNDescent","algorithm","[","^1","]","to","handle","vertex","addition","and","removal","in","a","FIFO","data","ingestion","policy",".","SWINN","builds","and","keeps","a","directed","graph","where","edges","connect","the","nearest","neighbors",".","Any","distance","metric","can","be","used","to","build","the","graph",".","By","using","a","directed","graph",",","the","user","must","set","the","desired","number","of","neighbors",".","More","neighbors","imply","more","accurate","search","queries","at","the","cost","of","increased","running","time","and","memory","usage",".","Note","that","although","the","number","of","directed","neighbors","is","limited","by","the","user",",","there","is","no","direct","control","on","the","number","of","reverse","neighbors",",","i.e.",",","the","number","of","vertices","that","have","an","edge","to","a","given","vertex",".","The","basic","idea","of","SWINN","and","NNDescent","is","that","``","the","neighbor","of","my","neighbors","might","as","well","be","my","neighbor","''",".","Hence",",","the","connections","are","constantly","revisited","to","improve","the","graph","structure",".","The","algorithm","for","creating","and","maintaining","the","search","graph","can","be","described","in","general","lines","as","follows",":","*","Start","with","a","random","neighborhood","graph",";","*","For","each","node","in","the","search","graph",":","refine","the","current","neighborhood","by","checking","if","there","are","better","neighborhood","options","among","the","neighbors","of","the","current","neighbors",";","*","If","the","total","number","of","neighborhood","changes","is","smaller","than","a","given","stopping","criterion",",","then","stop",".","SWINN","adds","strategies","to","remove","vertices","from","the","search","graph","and","pruning","redundant","edges",".","SWINN","is","more","efficient","when","the","selected","`","maxlen","`","is","greater","than","500",".","For","small","sized","data","windows",",","using","the","lazy\/exhaustive","search",",","i.e.",",","`","neighbors.LazySearch","`","might","be","a","better","idea",".","Parameters","--","--","--","--","--","graph_k","The","maximum","number","of","direct","nearest","neighbors","each","node","has",".","maxlen","The","maximum","size","of","the","data","buffer",".","warm_up","How","many","data","instances","to","observe","before","starting","the","search","graph",".","dist_func","The","distance","function","used","to","compare","two","items",".","If","not","set",",","use","the","Minkowski","distance","with","`","p=2","`",".","max_candidates","The","maximum","number","of","vertices","to","consider","when","performing","local","neighborhood","joins",".","If","not","set","SWINN","will","use","`","min","(","50",",","max","(","50",",","self.graph_k",")",")","`",".","delta","Early","stop","parameter","for","the","neighborhood","refinement","procedure",".","NNDescent","will","stop","running","if","the","maximum","number","of","iterations","is","reached","or","the","number","of","edge","changes","after","an","iteration","is","smaller","than","or","equal","to","`","delta","*","graph_k","*","n_nodes","`",".","In","the","last","expression",",","`","n_nodes","`","refers","to","the","number","of","graph","nodes","involved","in","the","(","local",")","neighborhood","refinement",".","prune_prob","The","probability","of","removing","redundant","edges",".","Must","be","between","`","0","`","and","`","1","`",".","If","set","to","zero",",","no","edge","will","be","pruned",".","When","set","to","one",",","every","potentially","redundant","edge","will","be","dropped",".","n_iters","The","maximum","number","of","NNDescent","iterations","to","perform","to","refine","the","search","index",".","seed","Random","seed","for","reproducibility",".","Notes","--","--","-","There","is","an","accuracy\/speed","trade-off","between","`","graph_k","`","and","`","sample_rate","`",".","To","ensure","a","single","connected","component",",","and","thus","an","effective","search","index",",","one","can","increase","`","graph_k","`",".","The","`","connectivity","`","method","is","a","helper","to","determine","whether","the","search","index","has","a","single","connected","component",".","However",",","search","accuracy","might","come","at","the","cost","of","increased","memory","usage","and","slow","processing",".","To","alleviate","that",",","one","can","rely","on","decreasing","the","`","sample_rate","`","to","avoid","exploring","all","the","undirected","edges","of","a","node","during","search","queries","and","local","graph","refinements",".","Moreover",",","the","edge","pruning","procedures","also","help","decreasing","the","computational","costs",".","Note","that",",","anything","that","limits","the","number","of","explored","neighbors","or","prunes","edges","might","have","a","negative","impact","on","search","accuracy",".","References","--","--","--","--","--","[","^1","]",":","Dong",",","W.",",","Moses",",","C.",",","&","Li",",","K.","(","2011",",","March",")",".","Efficient","k-nearest","neighbor","graph","construction","for","generic","similarity","measures",".","In","Proceedings","of","the","20th","international","conference","on","World","wide","web","(","pp",".","577-586",")","."]
code: def _linear_scan(self, item, k):
      # Lazy search while the warm-up period is not finished
      points = [(p.item, self.dist_func(item, p.item)) for p in self]
  
      if points:
          return tuple(
              map(
                  list,
                  zip(*sorted(points, key=operator.itemgetter(-1))[:k]),
              )
          )
  
      return None
  
imports: from __future__ import annotations
  import collections
  import functools
  import heapq
  import itertools
  import math
  import operator
  import random
  import typing
  from river import utils
  from river.neighbors.base import BaseNN, DistanceFunc, FunctionWrapper
  from .nn_vertex import Vertex
label_desc: Use image node_id 10 for calling the SWINN obj's underlying member method code with example usage: obj._linear_scan(item, k) and returns: None, tuple