Class DiversifyingNearestChildrenKnnCollector.NodeIdCachingHeap

  • Enclosing class:
    DiversifyingNearestChildrenKnnCollector

    private static class DiversifyingNearestChildrenKnnCollector.NodeIdCachingHeap
    extends java.lang.Object
    This is a minimum binary heap, inspired by LongHeap. But instead of encoding and using `long` values. Node ids and scores are kept separate. Additionally, this prevents duplicate nodes from being added.

    So, for every node added, we will update its score if the newly provided score is better. Every time we update a node's stored score, we ensure the heap's order.

    • Constructor Detail

      • NodeIdCachingHeap

        public NodeIdCachingHeap​(int maxSize)
    • Method Detail

      • topNode

        public final int topNode()
      • topScore

        public final float topScore()
      • pushIn

        private void pushIn​(int nodeId,
                            int parentId,
                            float score)
      • updateElement

        private void updateElement​(int heapIndex,
                                   int nodeId,
                                   int parentId,
                                   float score)
      • insertWithOverflow

        public boolean insertWithOverflow​(int node,
                                          int parentNode,
                                          float score)
        Adds a value to an heap in log(size) time. If the number of values would exceed the heap's maxSize, the least value is discarded.

        If `node` already exists in the heap, this will return true if the stored score is updated OR the heap is not currently at the maxSize.

        Returns:
        whether the value was added or updated
      • popToDrain

        private void popToDrain()
      • updateTop

        private void updateTop​(int nodeId,
                               int parentId,
                               float score)
      • size

        public final int size()
        Returns the number of elements currently stored in the PriorityQueue.
      • upHeap

        private void upHeap​(int origPos)
      • downHeap

        private int downHeap​(int i)
      • downHeapWithoutCacheUpdate

        private int downHeapWithoutCacheUpdate​(int i)