Tính toán trực tuyến hiệu quả không gian cho các tóm tắt phân vị
Tóm tắt
Một tóm tắt phân vị xấp xỉ ∈ của một chuỗi
Chúng tôi trình bày một thuật toán trực tuyến mới để tính toán các tóm tắt phân vị xấp xỉ ∈ của các chuỗi dữ liệu rất lớn. Thuật toán này có yêu cầu không gian trong trường hợp tồi tệ nhất là
Cuối cùng, các giới hạn không gian thực tế thu được trên dữ liệu thử nghiệm tốt hơn đáng kể so với các đảm bảo trường hợp tồi tệ nhất của thuật toán của chúng tôi cũng như các yêu cầu không gian quan sát được của các thuật toán trước đó.
Từ khóa
Tài liệu tham khảo
Rakesh Agrawal and Arun Swami . A one-pass space-efficient algorithm for finding quantiles . Proc. 7th Int. Conf. Management of Data, COMAD , 28-30 December 1995 . Rakesh Agrawal and Arun Swami. A one-pass space-efficient algorithm for finding quantiles. Proc. 7th Int. Conf. Management of Data, COMAD, 28-30 December 1995.
I. Pohl . A minimum storage algorithm for computing the median. IBM Research Report RC 2701, November 1969 . I. Pohl. A minimum storage algorithm for computing the median. IBM Research Report RC 2701, November 1969.
Viswanath Poosala , Venkatesh Ganti , and Yannis E. Ioannidis . Approximate query answering using histograms . Bulletin of the IEEE Technical Committee on Data Engineering , 22 ( 4 ): 6 - 15 , December 1999 . Viswanath Poosala, Venkatesh Ganti, and Yannis E. Ioannidis. Approximate query answering using histograms. Bulletin of the IEEE Technical Committee on Data Engineering, 22(4):6-15, December 1999.