Solver-class: Spatial-KWD Solver

In SpatialKWD: Spatial KWD for Large Spatial Maps

Spatial-KWD Solver

Description

The Solver class is the main wrapper to the core algorithms implemented in the Spatial KWD package. It has several methods that permit to compare two, or more, objects of type Histogram2D. If you use the helper functions described at the begging of this document, you can avoid using this class directly

Arguments

n	Number of bins in the histograms Xs, Yw, W1, W2, Ws.
H1	First object of type Histogram2D.
H2	Second object of type Histogram2D.
L	Approximation parameter. Higher values of L give a more accurate solution, but they require a longer running time. Table X gives the guarantee approximation bound as a function of L. Type: positive integer.
Xs	Vector of horizontal coordinates the bins. Type: vector of integers.
Ys	Vector of vertical coordinates the bins. Type: vector of integers.
W1	Vector of weights of the bin at the positions specified by Xs and Ys. Type: vector of doubles.
W2	Vector of weights of the bin at the positions specified by Xs and Ys. Type: vector of doubles.
Ws	Matrix of weights of the bin at the positions specified by Xs and Ys. Type: matrix of doubles.
name	Name of the parameter to set and/or get. Type: string.
value	Value to set the corresponding parameter specified by name. Type: double.

Details

The public methods of this class are:

The Solver class can be controlled by the list of parameters given in the following table, which can be set with the setParam(name, value) method. A detailed description of each parameter is given below.

Parameter Name	Possible Values	Default Value
Method	exact, approx	approx
Model	bipartite, mincostflow	mincostflow
Algorithm	fullmodel, colgen	colgen
Verbosity	silent, info, debug	info
TimeLimit	Any positive integer smaller than INTMAX	INTMAX
OptTolerance	Any value in [10^{-9}, 10^{-1}]	10^{-6}

• Method: set which method to use for computing the exact distance between a pair of histograms. The options for this parameter are:

  • exact: Compute the exact KW distance. This method is only helpful for small and sparse spatial maps.

  • approx: Compute an approximation KW distance which depends on the parameter L. This is the default value.

• Model: set which network model to use for computing the exact distance between a pair of histograms. The options for this parameter are:

  • bipartite: Build a complete bipartite graph. This method is only helpful for small and sparse spatial maps.

  • mincostflow: Build an uncapacitated network flow. This is, in general, smaller than the bipartite model, except for very sparse histograms.

• Algorithm: set which algorithm to use to compute an approximate distance between a pair of histograms, which depends on the parameter L. The options for this parameter are:

  • fullmodel: Build a complete network model and solve the corresponding problem.

  • colgen: Build the network model incrementally while computing the KW distance. It is the recommended method for very large dense spatial maps. On medium and small spatial maps, the fullmodel could be faster.

  The default value is set to colgen.

• Verbosity: set the level of verbosity of the logs. Possible values are silent, info, debug. The last is more verbose than the other two. The default value is set to info.

• TimeLimit: set the time limit for computing the distance between a pair of spatial maps. Min values: INTMAX. The default value is set to INTMAX.

• OptTolerance: Optimality tolerance on negative reduced cost variables to enter the basis. Min value: 10^{-9}, max value: 10^{-1}. The default value is set to 10^{-6}.

Methods

compareExact(Xs, Ys, W1, W2):

compute the exact distance between the two vector of weights W1 and W2, on the convex hull of the points defined by the two vectors Xs and Ys. The algorithm used by the solver is controlled by the parameter ExactMethod (see below). This method returns a single value (double), which is the KW-distance between W1 and W2.

compareExact(Xs, Ys, W1, Ws):

compute the exact distances between the vector of weights W1 and each of the vector of weights in Ws, on the convex hull of the points defined by the two vectors Xs and Ys. The algorithm used by the solver is controlled by the parameter ExactMethod (see below). This method returns a vector of double of the same size of Ws, representing the distance of W1 to every element of Ws.

compareExact(Xs, Ys, Ws):

compute a symmetric matrix of pairwise exact distances between all the possible pairs of the vector listed in Ws. The algorithm used by the solver is controlled by the parameter ExactMethod (see below).

compareApprox(Xs, Ys, W1, W2, L):

compute the approximate distance between the two vector of weights W1 and W2, on the convex hull of the points defined by the two vectors Xs and Ys. The parameter ApproxMethod (see below) controls the algorithm used by the solver. This method returns a single value (double), which is the KW-distance between W1 and W2.

compareApprox(Xs, Ys, W1, Ws, L):

compute the approximate distances between the vector of weights W1 and each of the vector of weights in Ws, on the convex hull of the points defined by the two vectors Xs and Ys. The parameter ApproxMethod (see below) controls the algorithm used by the solver. This method returns a vector of double of the same size of Ws, representing the distance of W1 to every element of Ws.

compareApprox(Xs, Ys, Ws, L):

compute a symmetric matrix of pairwise approximate distances (which depends on the value of L) between all the possible pairs of the vector listed in Ws. The parameter ApproxMethod (see below) controls the algorithm used by the solver.

runtime():

return the runtime in seconds to the last call to one of the compare methods. It reports the runtime of the execution of the Network Simplex algorithm.

preprocesstime():

return the preprocessing time in seconds to the last call to one of the compare methods. It reports the execution time to set up the main data structures and to compute the convex hull of all the input histograms.

setParam(name, value):

set the parameter name to the new value. Every parameter has a default value. See below for the existing parameters.

getParam(name):

return the current value of the parameter name.

See Also

See also compareOneToOne, compareOneToMany, compareAll, focusArea, and Histogram2D.

SpatialKWD documentation built on Dec. 9, 2022, 5:08 p.m.