1
\$\begingroup\$

I have written the following interface to represent data structures such as VP trees that perform nearest-neighbor searches.

/**
 * A data structure supporting nearest-neighbor searches.
 *
 * @param <T>  The type stored in the index.
 */
public interface MetricIndex<T> {
    /**
     * A nearest-neighbor match.
     *
     * @param <T>  The type of element found.
     */
    interface Match<T> {
        /**
         * @return The element discovered by the nearest-neighbor search.
         */
        T element();

        /**
         * @return The distance from {@link #element()} to the search target.
         */
       double distance();
    }

    /**
     * Create a new {@link Match} object.
     *
     * @param element   The element discovered by the nearest-neighbor search.
     * @param distance  The distance from {@code element} to the search target.
     * @return A new {@link Match} object.
     */
    static <T> Match<T> match(T element, double distance) {
        return new MetricIndexMatch<>(element, distance);
    }

    /**
     * @return A {@link Comparator} that sorts nearer {@link Match}es first.
     */
    static Comparator<Match<?>> nearestFirst() {
        return Comparator.comparing(Match::distance);
    }

    /**
     * @return The number of elements in the index.
     */
    int size();

    /**
     * @return Whether this index is empty.
     */
    default boolean isEmpty() {
        return size() == 0;
    }

    /**
     * Find the nearest element in the index to {@code target}.
     *
     * @param target  The target for the nearest-neighbor search.
     * @return The nearest element to {@code target}, or {@code null} if the
     *         index is empty.
     */
    default @Nullable Match<T> nearest(T target) {
        return nearestWithin(target, Double.POSITIVE_INFINITY).orElse(null);
    }

    /**
     * Find the nearest element in the index within a distance of
     * {@code threshold} to {@code target}.
     *
     * @param target     The target for the nearest-neighbor search.
     * @param threshold  The maximum allowable distance.
     * @return The nearest element within a distance of {@code threshold} to
     *         {@code target}, or {@link Optional#empty()} if no such element
     *         exists.
     */
    default Optional<Match<T>> nearestWithin(T target, double threshold) {
        return kNearestWithin(target, 1, threshold)
                .stream()
                .findFirst();
    }

    /**
     * Find the {@code k} nearest elements in the index to {@code target}.
     *
     * @param target  The target for the nearest-neighbor search.
     * @param k       The maximum size of the result set.
     * @return The (up to) {@code k} nearest elements to {@code target},
     *         nearest first.
     */
    default List<Match<T>> kNearest(T target, int k) {
        return kNearestWithin(target, k, Double.POSITIVE_INFINITY);
    }

    /**
     * Find the {@code k} nearest elements in the index within a distance of
     * {@code threshold} to {@code target}.
     *
     * @param target     The target for the nearest-neighbor search.
     * @param k          The maximum size of the result set.
     * @param threshold  The maximum allowable distance.
     * @return The (up to) {@code k} nearest elements within a distance of
     *         {@code threshold} to {@code target}, nearest first.
     */
    List<Match<T>> kNearestWithin(T target, int k, double threshold);
}

MetricIndexMatch<T> is the obvious package-private immutable implementation of MetricIndex.Match<T>.

I'm especially curious what people think of the API difference between nearest() and nearestWithin(). My reasoning is that nearest() almost always returns a value (only null if the index is empty), so the Optional overhead is usually unnecessary, while nearestWithin() could easily fail to find a match within the given threshold.

I'm also curious whether people think this interface should extend Collection<T>.

\$\endgroup\$
  • \$\begingroup\$ Like it much better with comments (I prefer a formatting easier on vertical space - any contemporary code editor should take care of differences in preferences like that). In Optional<Match<T>> nearestWithin(T target, double threshold), there's a reference to limit. Consider not including static <T> Match<T> match(), or including MetricIndexMatch, if nesting it in MetricIndex (and renaming it to SimpleMatch). Re Collection<T>: let your interface define one thing. \$\endgroup\$ – greybeard Jan 13 '16 at 23:56
  • \$\begingroup\$ @greybeard Thanks! I fixed the limit/threshold typo and squished the JavaDocs a bit, but they can only get so small within the width. \$\endgroup\$ – Tavian Barnes Jan 14 '16 at 0:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.