A survey of real-time approximate nearest neighbor query over streaming data for fog computing

Abstract Real-time approximate nearest neighbor (ANN) query over streaming data in fog computing environment is the fundamental problem of real-time analysis of big data. As the fog computing paradigm needs to provide real-time and low latency services, and traditional streaming data ANN query technology cannot be directly applied. Exploring the basic theory, querying framework and technology of real-time ANN query over streaming data for fog computing becomes one of the current research hotspots. This paper summarizes the related ANN query technology based on random hash, learning-to-hash and synopses, analyzes the problems and challenges of real-time ANN query in resource-limited fog computing environment, and finally discusses in detail the basic theory and method of the query, the dimension reduction and encoding method based on learning-to-hash, the generating synopses method for ANN query over streaming data from Internet of Thing, and the future related research directions of ANN query framework and others. Additionally, we propose a Dynamic Adaptive Quantization (DAQ) method for learning-to-hash. Experiments show that DAQ outperformed other quantization methods.