  The closest pair of points problem or closest pair problem (CPP) is an
important problem in computational geometry where we have to find a pair of
points from a set of points in metric space with the smallest distance between
them. This problem arises in a number of applications, such as but not limited
to clustering, graph partitioning, image processing, patterns identification,
and intrusion detection. For example, in air-traffic control, we must monitor
aircrafts that come too close together, since this may potentially indicate a
possible collision. Numerous algorithms have been presented for solving the
CPP. The algorithms that are employed in practice have a worst case quadratic
run time complexity. In this article we present an elegant approximation
algorithm for the CPP called MSPP: Mining Similar Pairs of Points. It is faster
than currently best known algorithms while maintaining a very good accuracy.
The proposed algorithm also detects a set of closely similar pairs of points in
Euclidean and Pearson metric spaces and can be adapted in numerous real world
applications, such as clustering, dimension reduction, constructing and
analyzing gene/transcript co-expression network, among others.
