We propose a novel method for detecting outliers based on the leave-one-out density. The leave-one-out density of a datum is defined as a ratio of the number of data inside a region to the volume of the region after the datum is removed from an original data set. We propose an efficient algorithm that evaluates the leave-one-out density of each datum on a set of regions around the datum by using binary decision diagrams. The time complexity of the proposed method is near linear with respect to the size of a data set, while the outlier detection accuracy is still comparable to other methods. Experimental results show the usefulness of the proposed method. © 2014 Springer International Publishing.