Export Citations
Space/time trade-offs in hash coding with allowable errors
This alert has been successfully added and will be sent to:
You will be notified whenever a record that you have chosen has been cited.
To manage your alert preferences, click on the button below.
Manage my AlertsPleaselog in to your account
Abstract
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.
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.
Cited By
View all- Wen JPei SYan CXie KLiang W(2025)Extensible Bloom Filters: Adaptive Strategies for Scalability and Efficiency in Network and Distributed Systems to Handle Increased DataTsinghua Science and Technology10.26599/TST.2024.901016030:4(1846-1864)Online publication date: Aug-2025
- Qiu LZhang KWang XYi BGao FQu YHuang M(2025)ParallelC-Store: A committee structure-based reliable parallel storage mechanism for permissioned blockchain shardingJournal of Network and Computer Applications10.1016/j.jnca.2025.104171239(104171)Online publication date: Jul-2025
- Shahrouz JAnaloui M(2025)Privacy-aware revocation in VANETs with a Blockchain using accumulatorVehicular Communications10.1016/j.vehcom.2025.10091853(100918)Online publication date: Jun-2025
- Show More Cited By
Recommendations
The use of quadratic residue research
Some of the problems of simulating discrete event systems, particularly computer systems, on a conventional digital computer are dealt with. The systems are assumed to be described as a network of interconnected sequential processes. Briefly reviewed ...
Information & Contributors
Information
Published In
Communications of the ACM Volume 13, Issue 7
July 1970
70 pages
ISSN:0001-0782
EISSN:1557-7317
DOI:10.1145/362686
- Editor:
- M. Stuart Lynn
IBM Scientific Center, Houston, TX
Copyright © 1970 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from[email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 July 1970
Published in CACM Volume13,Issue7
Permissions
Request permissions for this article.
Check for updates
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations5,557Total Citations
- 20,953Total Downloads
- Downloads (Last 12 months)3,520
- Downloads (Last 6 weeks)360
Reflects downloads up to 25 Apr 2025
Other Metrics
Citations
Cited By
View all- Wen JPei SYan CXie KLiang W(2025)Extensible Bloom Filters: Adaptive Strategies for Scalability and Efficiency in Network and Distributed Systems to Handle Increased DataTsinghua Science and Technology10.26599/TST.2024.901016030:4(1846-1864)Online publication date: Aug-2025
- Qiu LZhang KWang XYi BGao FQu YHuang M(2025)ParallelC-Store: A committee structure-based reliable parallel storage mechanism for permissioned blockchain shardingJournal of Network and Computer Applications10.1016/j.jnca.2025.104171239(104171)Online publication date: Jul-2025
- Shahrouz JAnaloui M(2025)Privacy-aware revocation in VANETs with a Blockchain using accumulatorVehicular Communications10.1016/j.vehcom.2025.10091853(100918)Online publication date: Jun-2025
- Zhang LTian RWu QRezaeibagha F(2025)BA-AMST: A blockchain-assisted anonymous and multi-keyword searchable-traceable data sharing system in Industrial Internet of ThingsEngineering Science and Technology, an International Journal10.1016/j.jestch.2025.10205566(102055)Online publication date: Jun-2025
- Zhu TWang JXiao YGao YZhou YWeng J(2025)Fully-incremental public key encryption with adjustable timed-release keyword searchInformation Sciences10.1016/j.ins.2025.121887702(121887)Online publication date: Jun-2025
- Ji SDu YHuang HSun YLiu JShu Y(2025)PipeFilter: Parallelizable and Space-Efficient Filter for Approximate Membership QueryIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2025.354388137:5(2816-2830)Online publication date: May-2025
- Hassan MVliegen JPicek SMentens N(2025)Designing Hardware-Friendly Hash Functions for Network Security Using Cartesian Genetic ProgrammingApplications of Evolutionary Computation10.1007/978-3-031-90062-4_14(221-237)Online publication date: 17-Apr-2025
- Lee HPark D(2025)MultigrainFuture Generation Computer Systems10.1016/j.future.2025.107762167:COnline publication date: 11-Apr-2025
- Qiu LYi BWang XGao FZhang KQu YHuang M(2025)GPartition-storeFuture Generation Computer Systems10.1016/j.future.2025.107731166:COnline publication date: 11-Apr-2025
- Fu YYe QDu RHu H(2025)Secure bi-attribute indexComputers and Security10.1016/j.cose.2025.104369152:COnline publication date: 11-Apr-2025
- Show More Cited By
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
Figures
Tables
Media
Affiliations
Burton H.Bloom
Computer Usage Company, Newton Upper Falls, MA