Function dot_product_topk

nodedb/src/engine/vector/sparse/search.rs:32–83

Search the sparse inverted index for documents most similar to the query. Computes dot-product scores by iterating query dimensions and accumulating weights from posting lists. Returns top-K results sorted by score descending. Complexity: O(Σ postings_length for query dimensions + K log K).

(
    index: &SparseInvertedIndex,
    query: &SparseVector,
    top_k: usize,
)

///
/// Complexity: O(Σ postings_length for query dimensions + K log K).
pub fn dot_product_topk(
    index: &SparseInvertedIndex,
    query: &SparseVector,
    top_k: usize,
) -> Vec<SparseSearchResult> {
    if query.is_empty() || index.is_empty() || top_k == 0 {
        return Vec::new();
    }

    // Accumulate scores per document.
    let mut scores: HashMap<u32, f32> = HashMap::new();

    for &(dim, q_weight) in query.entries() {
        if let Some(postings) = index.get_postings(dim) {
            for &(doc_id, doc_weight) in postings {
                *scores.entry(doc_id).or_insert(0.0) += q_weight * doc_weight;
            }
        }
    }

    if scores.is_empty() {
        return Vec::new();
    }

    // Top-K selection via min-heap bounded to K entries.
    let mut heap: BinaryHeap<std::cmp::Reverse<HeapEntry>> = BinaryHeap::with_capacity(top_k + 1);

    for (doc_id, score) in &scores {
        heap.push(std::cmp::Reverse(HeapEntry {
            score: *score,
            doc_id: *doc_id,
        }));
        if heap.len() > top_k {
            heap.pop(); // Remove smallest.
        }
    }

    // Drain heap into results (highest score first).
    // `into_sorted_vec` on `BinaryHeap<Reverse<T>>` returns ascending `Reverse`
    // order, which is descending actual score order.
    let results: Vec<SparseSearchResult> = heap
        .into_sorted_vec()
        .into_iter()
        .map(|std::cmp::Reverse(entry)| SparseSearchResult {
            internal_id: entry.doc_id,
            score: entry.score,
            doc_id: index.resolve_doc_id(entry.doc_id).map(String::from),
        })
        .collect();

    results
}

/// Min-heap entry: ordered by score ascending so the heap root is the minimum.
#[derive(Debug)]