search method

Implementation

List<VectorSearchHit> search(
  Vector query,
  int k, {
  VectorMetric? metric,
  int? ef,
}) {
  if (query.dim != dim) {
    throw StateError(
      'HnswIndex.search: query dim ${query.dim} != index dim $dim',
    );
  }
  if (k <= 0 || _ids.isEmpty) return const [];
  final m = metric ?? defaultMetric;
  final larger = m == VectorMetric.innerProduct;
  final effEf = math.max(k, ef ?? efSearch);

  // Precompute query-side scalar for cosine.
  double qNorm = 0.0;
  if (m == VectorMetric.cosine) {
    for (final x in query.values) {
      qNorm += x * x;
    }
    qNorm = math.sqrt(qNorm);
    if (qNorm == 0.0) qNorm = 1.0;
  }

  double distQ(int nodeId) => _distQuery(query, nodeId, m, qNorm);

  // Greedy descent from top layer with ef=1.
  var cur = _entry;
  for (var lc = _topLayer; lc > 0; lc--) {
    var curD = distQ(cur);
    var improved = true;
    while (improved) {
      improved = false;
      if (lc >= _links[cur].length) break;
      for (final nb in _links[cur][lc]) {
        final di = distQ(nb);
        if (_isBetter(di, curD, larger)) {
          curD = di;
          cur = nb;
          improved = true;
        }
      }
    }
  }

  // Beam search at layer 0.
  final w = _searchLayerQuery(distQ, cur, effEf, 0, larger);
  w.sort((a, b) => larger ? b.$1.compareTo(a.$1) : a.$1.compareTo(b.$1));
  final effK = math.min(k, w.length);
  final out = <VectorSearchHit>[];
  for (var i = 0; i < effK; i++) {
    final s = m == VectorMetric.l2 ? math.sqrt(w[i].$1) : w[i].$1;
    out.add(VectorSearchHit(_ids[w[i].$2], s));
  }
  return out;
}