Imputation of missing data is important in many
areas, such as reducing non-response bias in surveys and
maintaining medical documentation. Nearest neighbour (NN)
imputation algorithms replace the missing values within any
particular observation by taking copies of the corresponding
known values from the most similar observation found in the
dataset. However, when NN algorithms are executed against large
multivariate datasets the poor
performance (program execution
speed) of these algorithms can present major practical problems.
We argue that these problems
have not been sufficiently
addressed, and we present a fast NN imputation algorithm that
can employ any method for meas
uring the similarity between
observations. The algorithm has b
een designed for the imputation
of missing values in large multivar
iate datasets that contain many
different missingness patterns with large proportions of missing
data. The ideas underpinning th
e algorithm are explained in
detail, and experiments are described which show that the
algorithm delivers very good perf
ormance when it is used for
imputation in both segmented and non-segmented datasets
containing several million rows