Fast nearest neighbor (NN) finding has been extensively studied. While some fast NN algorithms using metrics rely on the essential properties of metric spaces, the others using non-metric measures fail for large-size templates. However in some applications with very large size templates, the best performance is achieved by NN methods based on the dissimilarity measures resulting in a special space where computations cannot be pruned by the algorithms based-on the triangular inequality. For such NN methods, the existing fast algorithms except condensing algorithms are not applicable. In this paper, a fast hierarchical search algorithm is proposed to find k-NNs using a non-metric measure in a binary feature space. Experiments with handwritten digit recognition show that the new algorithm reduces on average dissimilarity computations by more than 90% while losing the accuracy by less than 0.1%, with a 10% increase in memory.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    A fast algorithm for finding k-nearest neighbors with non-metric dissimilarity


    Contributors:
    Bin Zhang, (author) / Srihari, S.N. (author)


    Publication date :

    2002-01-01


    Size :

    320800 byte




    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    A Fast Algorithm for Finding k-Nearest Neighbors with Non-Metric Dissimilarity

    Zhang, B. / Srihari, S. N. | British Library Conference Proceedings | 2002


    IMPROVING TRUST IN DEEP NEURAL NETWORKS WITH NEAREST NEIGHBORS

    Lee, Ritchie / Clarke, Justin / Agogino, Adrian et al. | TIBKAT | 2020


    Improving Trust in Deep Neural Networks with Nearest Neighbors

    Lee, Ritchie / Clarke, Justin / Agogino, Adrian et al. | AIAA | 2020