Neighborhood Navigation Query

This is normally the only parameter needed to dial in the desired search performance.

When given, the navigation algorithm uses Cosine similarity to evaluate nodes in the graph against the probe. All graph nodes must have a vector assigned for the search to work.

Use the expression language to add custom filters applied to any visited node during graph exploration. The expression must be a local evaluator, i.e. it cannot reference any of the next* arc attributes or head vertex attributes/properties, or perform any stage*() or collect*() operations.

This heap can be made larger than needed to hold k hits which in some cases may increase the ability to find true nearest neighbors. Effective result_capacity is never lower than k given by Neighborhood( hits=k ).

Navigation is controlled by a running threshold estimate which must be exceeded for a candidate node to be considered for the result and to facilitate continued traversal. This threshold is computed from a delayed observation at the frontier. High inertia leads to more aggressive exploration (higher recall) due to a slowly rising threshold. Low inertia does the opposite, causing the threshold to rise quickly thus terminating the search sooner (lower latency.)

A positive number selects a queue-based frontier for the navigation algorithm. By default the frontier is maintained in a beam (heap) which is populated from scratch at every new level of expansion depth and then fully consumed at the next depth. However, selecting a queue-based frontier changes this behavor. The frontier queue is continually populated and consumed, causing it to grow rapidly at first and then later consumed to exhaustion.

A visited node that was accepted into the frontier will later facilitate further exploration (if its score is still above the running threshold.) The process of exploring a node’s neighborhood is called expansion. Set expansion_limit to restrict how many neighborhoods will be explored before terminating the search.

Navigation is performed by expanding frontier nodes (i.e. searching their neighborhoods.) This activity adds new promising nodes to the frontier. When all frontier nodes that were present at start of expansion have been consumed the algorithm moves one level deeper into the graph, now expanding nodes that were recently added to the frontier. Set depth_limit to restrict max distance (hops) from the entry point before terminating the search.

Use this to set a maximum allowed search time. Navigation search always carries some risk of runaway execution (in pathological graphs.) Production services should set a timeout to prevent unexpected edge cases from destabilizing the system. (A reasonable upper limit would be something like 2 times the 99.9th latency percentile.)

Navigation search visits graph nodes to evaluate them. Some nodes are accepted into the result or the frontier, most are discarded. As the graph is explored the number of visited nodes grows. All visited nodes are recorded in a set to prevent cyclic exploration. The visited node set consumes memory. To avoid unbounded memory usage visit_limit can be set to terminate the search after a maximum number of node visits.

If the proximity graph is constructed with a synthetic entry point, use entry_width to pick the number of starting nodes in the graph. This is helpful if the synthetic entry point connects to a maximally diverse set of nodes in the graph. Selecting the top best entry_point nodes as seeds for navigation can help speed up convergence and generally leads to better performance. For example, a synthetic entry point may be connected to 500 diverse (mutually unrelated) nodes. Selecting five of these using entry_width=5 helps give the search a flying start by teleporting straight into potentially relevant graph regions.

Beam search uses a focused frontier of promising nodes captured into a heap of a certain max size (beam_width.) As better nodes are discovered, inferior nodes are evicted from the beam. Once all nodes in the previous beam have been expanded a new beam (just built) takes its place and search continues. The initial beam is a special case and consists of all neighbors of the start node. When expansion of a previous beam results in an empty new beam (zero promising nodes found) search terminates. Use beam_width to set the max number of promising nodes captured at each level of expansion depth.

The smallest beam permitted if beam width is subject to adjustment during search.

The largest beam permitted if beam width is subject to adjustment during search.

At each level of expansion (hops from entry point) the next level’s beam width will be the current level’s beam width multiplied by beam_decay. Values lower than 1.0 then gradually shrinks the beam width (but never below beam_min.)

The optimal beam width is both data dependent and query dependent. When adaptive_beam is True the algorithm adjusts beam width automatically for each query by measuring result set improvement during search. When the result set is quickly improving with new, better items the beam becomes narrower. When search stagnates without finding better items the beam becomes wider (but never above beam_max.) If beam_decay is less than 1.0 the narrowing bias is applied on top of the adaptive width.

To expand a frontier node its score must be greater than the current threshold. Depth discount alpha adjusts the effective threshold used when deciding if a node should be expanded. Higher values (above -1.0) make the gate more permissive with exploration depth, i.e. a node many hops away from the entry point may be expanded even if its score is slightly below the current threshold. Conversely, lower values (below -1.0) make the gate stricter with exploration depth, thereby expediting termination as neighborhoods far from the entry point are reached.

To expand a frontier node its score must be greater than the current threshold. Evaluation discount beta adjusts the effective threshold used when deciding if a node should be expanded. Higher values (above 0.0) make the gate more permissive as the number of visited nodes grows, i.e. a node visited late in the search may still be expanded even if its score is slightly below the current threshold. Conversely, lower values (below 0.0) make the gate stricter as the number of visited nodes grows, thereby promoting faster termination after many node visits. Evaluation discount is disabled with beta = 0.0.

To expand a frontier node its score must be greater than the current threshold. Global offset gamma adjusts the effective threshold used when deciding if a node should be expanded. Higher values (above 0.0) make the gate more permissive and lower values (below 0.0) make the gate stricter. Global offset is disabled with gamma = 0.0.

When adaptive_beam is enabled the beam controller adjusts beam width automatically based on how successful search currently is at improving the result set. When the result is improving quickly the beam is narrowed, and when result improvement stagnates the beam is widened. Modulation strength can be adjusted using controller reactivity delta. Higher values modulates width more strongly and lower values lessen the effect of the beam controller. Nominal control is obtained with delta = 0.0 and the controller is disabled with delta = -1.0.

Visited nodes are evaluated using a scoring function. (For vector similarity this function is score = Cosine(probe, node) + 1.0.) If a node’s score is at or above the current threshold it counts as an observation at the frontier and is injected into the observation history queue whose size is determined by inertia. (The node may also be entered into the result and/or frontier if its score is good enough.) Conversely, if the node’s score is below the current threshold the score is ignored and instead the current threshold is injected into the history queue, representing a sample-and-hold observation at the frontier. A non-zero epsilon modifies the current threshold used when making these decisions. Positive epsilon values increase difficulty and negative values make the gate more permissive. +} NOTE: Normally, use tiny epsilon values. For reference, the automatic values derived from bias are in the range -0.00067 to 0.001. (The parameter’s large range -1.0 to 1.0 is intended for special use cases and debugging.)

At the end of the observation history queue (whose length is controlled by inertia) sits an exponential moving average smoothing function. Its purpose is to prevent outlier samples observed at the frontier from abruptly changing the threshold used by the expansion controller and node evaluator. Infinite smoothing is obtained with zeta = 0.0, i.e. threshold never changes from its initial (0.0) value. Smoothing is disabled with zeta = 1.0, i.e. raw (delayed) frontier observations are presented as current threshold.

This parameter applies weighted adjustment to alpha, beta, gamma, delta, epsilon, and zeta simultaneously. Its purpose is to temper (omega < 1.0) the individually optimized parameters for better navigation stability. During custom performance tuning it is easy to over-tune individual parameters to maximize their effects. This can sometimes push the algorithm to the edge of stability. It is often a good idea to dial back these individual settings with omega < 1.0. Experimenting with omega can help finalize performance tuning by allowing slight adjustments to multiple parameters at the same time.

If the graph uses arcs with modifier M_INT to connect nodes and the values of those arcs indicate priority (where 0 is highest), then kappa may be used to enable traversal thinning. A value kappa=1 or higher tells the algorithm to apply a thinning rule (via lambda) to possibly skip arcs with priority >= kappa. This can be useful for rough searches that need extra speed, as part of evaluating overall graph structure during build, debugging, or other special use cases. Normally this parameter should be left at 0.

If kappa is > 0 then lambda determines which arcs (whose value >= kappa) will be ignored. Skipping rule for arcs with value >= kappa is as follows for different values of lambda: 0=skip ALL, 1=skip 50%, 2=75%, 3=88%, 4=94%, 5=97%, 6=98%, 7=99%.

When using an externally managed pyvgx.Memory object m with Neighborhood( memory=m, …​ ) various internal counters and beam width control variables are accumulated inside m. If reset_metrics=False when re-using a memory object these counters and control variables will continue to accumulate. This can be useful for debugging or for special cases where search is manually divided into multiple Neighborhood() calls.

Some internal counters are visible and may be accessed via m.counters attribute. The return value is a tuple: (score_evaluations, threshold_contributions, accepted_into_frontier, accepted_into_result, recursion_depth, node_expansions, node_visits, node_revisits_avoided).

When using an externally managed pyvgx.Memory object m with Neighborhood( memory=m, …​ ) the node visitation set built during traversal is kept inside m. If reset_map=False when re-using a memory object with another Neighborhood() query the visitation set is remembered and will prevent visiting the same nodes visited in the previous query. This can be useful for debugging or when search is manually divided into multiple Neighborhood() calls with different entry points.