Abstract: An accurate and stable approach to image anomaly detection is to query the K-nearest neighbours of the image features from normal examples and estimate the anomaly score, relying on Approximate Nearest Neighbour Search (ANNS) indices. ANNS query operation has high computational cost on large datasets, unpractical for low-latency and high-throughput scenarios. Based on locality sensitive Hashing and Bloom filters, an Approximated Membership Query (AMQ) based approach is proposed to predict anomalies by approximate membership of features. AMQ can address the performance bottleneck of search-based methods, given its lower complexity and better compatibility with single-instruction multiple-data parallelism than ANNS. Experimental results on MVTec-AD show that the accuracy of AMQ-based method is just decreased about 1% in comparison with ANNS-based methods, while the inference latency, the throughput and the memory footprint are significantly improved, close to the efficiency of end-to-end deep learning anomaly detection models.