  We consider the testing and estimation of change-points, locations where the
distribution abruptly changes, in a sequence of multivariate or non-Euclidean
observations. We study a nonparametric framework that utilizes similarity
information among observations, which can be applied to various data types as
long as an informative similarity measure on the sample space can be defined.
The existing approach along this line has low power and/or biased estimates for
change-points under some common scenarios. We address these problems by
considering new tests based on similarity information. Simulation studies show
that the new approaches exhibit substantial improvements in detecting and
estimating change-points. In addition, under some mild conditions, the new test
statistics are asymptotically distribution free under the null hypothesis of no
change. Analytic p-value approximations to the significance of the new test
statistics for the single change-point alternative and changed interval
alternative are derived, making the new approaches easy off-the-shelf tools for
large datasets. The new approaches are illustrated in an analysis of New York
taxi data.
