Space/Time Trade-offs in Hash Coding with Allowable Errors

Burton H. Bloom, 1970, Communications of the ACM

About this paperEnglish中文日本語beside Englishbeside 中文beside 日本語

This paper is under a licence that does not allow it to be reproduced, so what is here is its front matter and a short abstract. Read it at the publisher's page.

Đánh đổi Không gian/Thời gian trong Mã hóa Băm với Các Lỗi Cho phép

BURTON H. BLOOM

Computer Usage Company, Newton Upper Falls, Mass.

Trong bài báo này, các sự đánh đổi giữa một số yếu tố tính toán nhất định trong mã hóa băm được phân tích. Bài toán mô hình được xem xét là kiểm tra một chuỗi thông điệp lần lượt từng thông điệp một để xác định việc thuộc về một tập thông điệp đã cho. Hai phương pháp mã hóa băm mới được khảo sát và so sánh với một phương pháp mã hóa băm quy ước cụ thể. Các yếu tố tính toán được xem xét là kích thước của vùng băm (không gian), thời gian cần thiết để xác định một thông điệp là không phải thành viên của tập đã cho (thời gian loại bỏ), và một tần suất lỗi cho phép.

Các phương pháp mới nhằm giảm lượng không gian cần thiết để chứa thông tin được mã hóa băm so với lượng không gian tương ứng với các phương pháp quy ước. Việc giảm không gian đạt được bằng cách khai thác khả năng rằng một phần nhỏ các lỗi do chấp nhận nhầm có thể được chấp nhận trong một số ứng dụng, đặc biệt là các ứng dụng trong đó một lượng lớn dữ liệu có liên quan và do đó một vùng băm thường trú trong bộ nhớ lõi là không khả thi khi sử dụng các phương pháp quy ước.

Trong các ứng dụng như vậy, người ta dự kiến rằng hiệu năng tổng thể có thể được cải thiện bằng cách sử dụng một vùng băm thường trú trong bộ nhớ lõi nhỏ hơn kết hợp với các phương pháp mới và, khi cần thiết, bằng cách sử dụng một số phép kiểm tra phụ có thể tốn thời gian để "bắt" phần nhỏ các lỗi liên quan đến các phương pháp mới. Một ví dụ được thảo luận nhằm minh họa các lĩnh vực ứng dụng khả dĩ của các phương pháp mới.

References

  1. Batson, A. The organization of symbol tables. Comm. ACM 8, 2 (Feb. 1965), 111–112.
  2. Maurer, W. D. An improved hash code for scatter storage. Comm. ACM 11, 1 (Jan. 1968), 35–38.
  3. Morris, R. Scatter storage techniques. Comm. ACM 11, 1 (Jan. 1968), 38–44. | TABLE I. SUMMARY OF EXPECTED PERFORMANCE OF HYPHENATION APPLICATION OF HASH CODING USING METHOD 2 FOR VARIOUS VALUES OF ALLOWABLE FRACTION OF ERRORS | | | | --- | --- | --- | | P = Allowable Fraction of Errors | N = Size of Hash Area (Bits) | Disk Accesses Saved | | $\frac{1}{2}$ | 72,800 | 45.0% | | $\frac{1}{4}$ | 145,600 | 67.5% | | $\frac{1}{8}$ | 218,400 | 78.7% | | $\frac{1}{16}$ | 291,200 | 84.4% | | $\frac{1}{32}$ | 364,000 |
  4. 2% | | $\frac{1}{64}$ | 509,800 |
  5. 5% |

Read off the page by a vision model reading the page images using olmOCR-2-7B-1025-FP8. Translated into Tiếng Việt by gpt-5, against glossary version 7. Translated from the English.