This paper proposed a Fast Outlier Detection algorithm Over Uncertain Data Streams (FOD_OUDS). Firstly，an index inspired by hierarchical ideas was designed to manage uncertain data stream，and some storage information was added for the leaf nodes in the index structure，so that the newly inflowed data points can directly perform batch filtering by using the intermediate result information when the data is updated，thereby achieving the purpose of reducing the calculation cost. Secondly，by analyzing the recursive rules of outlier probability values in calculation，a novel outlier probability value solution scheme was presented，which can avoid as much as possible the calculating cost of nearest neighbor set，reduce the processing cost of a large number of inliers，thus speeding up processing. At last，a large amount of experiments show that the FOD_OUDS algorithm can effectively improve the detection efficiency.