compute-minkowski-distance

Minkowski Distance

Computes the Minkowski distance between two arrays.

The Minkowski distance defines a distance between two points in a normed vector space.

Special cases:

• When p=1, the distance is known as the Manhattan distance.
• When p=2, the distance is known as the Euclidean distance.
• In the limit that p --> +infinity, the distance is known as the Chebyshev distance.

Installation

$ npm install compute-minkowski-distance

For use in the browser, use browserify.

Usage

var minkowski = require( 'compute-minkowski-distance' );

minkowski( x, y, [opts] )

Computes the Minkowski distance between two arrays.

var x = [ 2, 4, 5, 3, 8, 2 ],
    y = [ 3, 1, 5, -3, 7, 2 ];
 
var d = minkowski( x, y );
// returns ~6.86

The function accepts the following options:

• p: norm order (p > 0).
• accessor: accessor function for accessing array values.

By default, the norm order is 2 (Euclidean distance). To specify a different order, set the p option.

var x = [ 2, 4, 5, 3, 8, 2 ],
    y = [ 3, 1, 5, 3, 7, 2 ];
 
var d = minkowski( x, y, {
    'p': 1
});
// returns 5

For object arrays, provide an accessor function for accessing numeric values.

var x = [
    {'x':2},
    {'x':4},
    {'x':5}
];
 
var y = [
    [1,1],
    [2,2],
    [3,7]
];
 
function getValue( d, i, j ) {
    if ( j === 0 ) {
        return d.x;
    }
    return d[ 1 ];
}
 
var dist = minkowski( x, y, {
    'accessor': getValue
});
// returns 3

The accessor function is provided three arguments:

• d: current datum.
• i: current datum index.
• j: array index; e.g., array x has index 0, and array y has index 1.

If provided empty arrays, the function returns null.

Notes

Warning: only specific p values allow for proper consideration of overflow and underflow; i.e., Euclidean, Manhattan, and Chebyshev distances. In the general case, you may overflow for large p values.

Examples

var minkowski = require( 'compute-minkowski-distance' );
 
var x = new Array( 100 ),
    y = new Array( 100 );
 
for ( var i = 0; i < x.length; i++ ) {
    x[ i ] = Math.round( Math.random()*100 );
    y[ i ] = Math.round( Math.random()*100 );
}
 
// Euclidean distance (default):
console.log( minkowski( x, y ) );
 
// Manhattan (city block) distance:
console.log( minkowski( x, y, {
    'p': 1
}));
 
// Chebyshev distance:
console.log( minkowski( x, y, {
    'p': Number.POSITIVE_INFINITY
}));
 
// Some other distance:
console.log( minkowski( x, y, {
    'p': 3
}));

To run the example code from the top-level application directory,

$ node ./examples/index.js

Tests

Unit

Unit tests use the Mocha test framework with Chai assertions. To run the tests, execute the following command in the top-level application directory:

$ make test

All new feature development should have corresponding unit tests to validate correct functionality.

Test Coverage

This repository uses Istanbul as its code coverage tool. To generate a test coverage report, execute the following command in the top-level application directory:

$ make test-cov

Istanbul creates a ./reports/coverage directory. To access an HTML version of the report,

$ make view-cov

---

License

MIT license.

Copyright

Copyright © 2015. Philipp Burckhardt.