PerformanceMeasures.java

package mhtree.benchmarking;

import messif.algorithms.Algorithm;
import messif.algorithms.AlgorithmMethodException;
import messif.objects.util.DistanceRankedObject;
import messif.objects.util.RankedAbstractObject;
import messif.operations.query.KNNQueryOperation;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;

public class PerformanceMeasures {

    public static double measureErrorOnThePosition(KNNQueryOperation approxKNNQueryOperation, Algorithm tree) throws NoSuchMethodException, AlgorithmMethodException {
        KNNQueryOperation rankedObjects = new KNNQueryOperation(approxKNNQueryOperation.getQueryObject(), tree.getObjectCount());
        tree.executeOperation(rankedObjects);

        Map<String, Integer> IDtoPosition = new HashMap<>(rankedObjects.getAnswerCount());

        int i = 1;
        for (RankedAbstractObject object : rankedObjects) {
            IDtoPosition.put(object.getObject().getLocatorURI(), i);
            i++;
        }

        double sum = 0;

        int approxPosition = 1;
        for (RankedAbstractObject object : approxKNNQueryOperation) {
            sum += IDtoPosition.get(object.getObject().getLocatorURI()) - approxPosition;
            approxPosition++;
        }

        return sum / (approxKNNQueryOperation.getAnswerCount() * rankedObjects.getAnswerCount());
    }

    // comparing done based on distances, counts how many of the same distances of KNNQueryOperation were presents in the answer of ApproxKNNQueryOperation
    public static double measureRecall(KNNQueryOperation approxKNNQueryOperation, Algorithm tree) throws NoSuchMethodException, AlgorithmMethodException {
        if (approxKNNQueryOperation.getAnswerCount() == 0) return 0d;

        KNNQueryOperation knnQueryOperation = new KNNQueryOperation(approxKNNQueryOperation.getQueryObject(), approxKNNQueryOperation.getK());
        tree.executeOperation(knnQueryOperation);

        List<RankedAbstractObject> kNNObjects = new ArrayList<>(knnQueryOperation.getAnswerCount());
        for (RankedAbstractObject object : knnQueryOperation)
            kNNObjects.add(object);

        Map<Float, Long> frequencyMap = kNNObjects
                .stream()
                .map(DistanceRankedObject::getDistance)
                .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));

        long trueKNNFoundCount = 0;

        for (RankedAbstractObject approxObject : approxKNNQueryOperation) {
            float distance = approxObject.getDistance();
            if (frequencyMap.containsKey(distance)) {
                long count = frequencyMap.get(distance);
                if (count == 1) {
                    frequencyMap.remove(distance);
                } else {
                    frequencyMap.replace(distance, count - 1);
                }
                trueKNNFoundCount++;
            }
        }

        return trueKNNFoundCount / (double) knnQueryOperation.getAnswerCount();
    }

    public static double measureRecall(KNNQueryOperation approxKNNQueryOperation, Map<String, List<RankedAbstractObject>> trueKNN) {
        if (approxKNNQueryOperation.getAnswerCount() == 0) return 0d;

        List<RankedAbstractObject> kNNObjects = trueKNN.get(approxKNNQueryOperation.getQueryObject().getLocatorURI())
                                                    .subList(0, approxKNNQueryOperation.getK());

        Map<Float, Long> frequencyMap = kNNObjects
                .stream()
                .map(DistanceRankedObject::getDistance)
                .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));

        long trueKNNFoundCount = 0;

        for (RankedAbstractObject approxObject : approxKNNQueryOperation) {
            float distance = approxObject.getDistance();
            if (frequencyMap.containsKey(distance)) {
                long count = frequencyMap.get(distance);
                if (count == 1) {
                    frequencyMap.remove(distance);
                } else {
                    frequencyMap.replace(distance, count - 1);
                }
                trueKNNFoundCount++;
            }
        }

        return trueKNNFoundCount / (double) kNNObjects.size();
    }
}