Distance-based outlier detection is an important data mining technique that finds abnormal data objects according to some distance function. However, when this technique is applied to high-dimensional categorical data, a traditional simple matching dissimilarity measure does not provide an adequate model. In this article, we employ a new common- neighbor-based distance function to measure the proximity between a pair of data points. Experiments show that better outlier mining results can be achieved when the new distance function is utilized rather than a conventional simple matching dissimilarity measure.