Data-dependent dissimilarity measure: an effective alternative to geometric distance measures

Sunil Aryal, Kai Ming Ting, Takashi Washio, Gholamreza Haffari

    Research output: Contribution to journalArticleResearchpeer-review

    22 Citations (Scopus)


    Nearest neighbor search is a core process in many data mining algorithms. Finding reliable closest matches of a test instance is still a challenging task as the effectiveness of many general-purpose distance measures such as ℓp-norm decreases as the number of dimensions increases. Their performances vary significantly in different data distributions. This is mainly because they compute the distance between two instances solely based on their geometric positions in the feature space, and data distribution has no influence on the distance measure. This paper presents a simple data-dependent general-purpose dissimilarity measure called ‘mp-dissimilarity’. Rather than relying on geometric distance, it measures the dissimilarity between two instances as a probability mass in a region that encloses the two instances in every dimension. It deems two instances in a sparse region to be more similar than two instances of equal inter-point geometric distance in a dense region. Our empirical results in k-NN classification and content-based multimedia information retrieval tasks show that the proposed mp-dissimilarity measure produces better task-specific performance than existing widely used general-purpose distance measures such as ℓp-norm and cosine distance across a wide range of moderate- to high-dimensional data sets with continuous only, discrete only, and mixed attributes.

    Original languageEnglish
    Pages (from-to)479-506
    Number of pages28
    JournalKnowledge and Information Systems
    Issue number2
    Publication statusPublished - 1 Nov 2017


    • Cosine distance
    • Distance measure
    • m-dissimilarity
    • ℓ-norm

    Cite this