search method

List<VectorSearchHit> search(
  1. Vector query,
  2. int k, {
  3. VectorMetric? metric,
})

Top-k nearest neighbors of query under Hamming distance. The metric argument is accepted for API symmetry with the other index kinds but ignored — LSH always ranks in Hamming space.

Implementation

List<VectorSearchHit> search(
  Vector query,
  int k, {
  VectorMetric? metric,
}) {
  if (query.dim != dim) {
    throw StateError(
      'LshIndex.search: query dim ${query.dim} != index dim $dim',
    );
  }
  if (k <= 0 || _ids.isEmpty) return const [];
  final n = _ids.length;
  final effK = math.min(k, n);
  final qcode = Uint8List(codeSize);
  _encodeOne(query.values, qcode, 0);

  final scores = List<double>.filled(effK, 0.0);
  final ids = List<Object?>.filled(effK, null);
  var filled = 0;
  for (var r = 0; r < n; r++) {
    final di = _hamming(qcode, 0, _codes, r * codeSize).toDouble();
    if (filled < effK) {
      var j = filled;
      while (j > 0 && di < scores[j - 1]) {
        scores[j] = scores[j - 1];
        ids[j] = ids[j - 1];
        j--;
      }
      scores[j] = di;
      ids[j] = _ids[r];
      filled++;
    } else if (di < scores[effK - 1]) {
      var j = effK - 1;
      while (j > 0 && di < scores[j - 1]) {
        scores[j] = scores[j - 1];
        ids[j] = ids[j - 1];
        j--;
      }
      scores[j] = di;
      ids[j] = _ids[r];
    }
  }
  return [
    for (var i = 0; i < filled; i++) VectorSearchHit(ids[i], scores[i])
  ];
}