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

Đá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.

In this paper trade-offs among certain computational factors in hash coding are analyzed. The paradigm problem considered is that of testing a series of messages one-by-one for membership in a given set of messages. Two new hash-coding methods are examined and compared with a particular conventional hash-coding method. The computational factors considered are the size of the hash area (space), the time required to identify a message as a nonmember of the given set (reject time), and an allowable error frequency.

The new methods are intended to reduce the amount of space required to contain the hash-coded information from that associated with conventional methods. The reduction in space is accomplished by exploiting the possibility that a small fraction of errors of commission may be tolerable in some applications, in particular, applications in which a large amount of data is involved and a core resident hash area is consequently not feasible using conventional methods.

In such applications, it is envisaged that overall performance could be improved by using a smaller core resident hash area in conjunction with the new methods and, when necessary, by using some secondary and perhaps time-consuming test to "catch" the small fraction of errors associated with the new methods. An example is discussed which illustrates possible areas of application for the new methods.

Analysis of the paradigm problem demonstrates that allowing a small number of test messages to be falsely identified as members of the given set will permit a much smaller hash area to be used without increasing reject time.

KEY WORDS AND PHRASES: hash coding, hash addressing, scatter storage, searching, storage layout, retrieval trade-offs, retrieval efficiency, storage efficiency CR CATEGORIES: 3.73, 3.74, 3.79

This section is missing here.

Introduction