Tính toán trực tuyến hiệu quả không gian cho các tóm tắt phân vị

SIGMOD Record - Tập 30 Số 2 - Trang 58-66 - 2001
Michael B. Greenwald1, Sanjeev Khanna1
1Computer & Information Science Department, University of Pennsylvania, 200 South 33rd Street, Philadelphia, PA

Tóm tắt

Một tóm tắt phân vị xấp xỉ ∈ của một chuỗi N phần tử là một cấu trúc dữ liệu có thể trả lời các truy vấn về phân vị đối với chuỗi với độ chính xác là ∈ N . 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à Ο (1÷∈ log(∈ N )). Kết quả này tốt hơn so với kết quả tốt nhất trước đây là Ο (1÷∈ log 2 (∈ N )). Hơn nữa, trái ngược với các thuật toán xác định trước đây, thuật toán của chúng tôi không yêu cầu kiến thức a priori về độ dài của chuỗi đầu vào. 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.

10.5555/645923.673650

10.1145/276304.276343

10.5555/645923.673669

10.1016/0166-5316(96)00043-0

10.1145/4372.4378

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.

10.1145/276304.276342

10.1145/304182.304204

10.1016/0304-3975(80)90061-4

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.

10.1145/233269.233342

Thông tin
Thông tin xuất bản

SIGMOD Record

Tập 30 Số 2

58-66

Thông tin tác giả