{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,13]],"date-time":"2026-10-13T18:53:10Z","timestamp":1791917590879,"version":"4.3.4"},"reference-count":3,"publisher":"Association for Computing Machinery (ACM)","issue":"7","license":[{"start":{"date-parts":[[1970,7,1]],"date-time":"1970-07-01T00:00:00Z","timestamp":15638400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Commun. ACM"],"published-print":{"date-parts":[[1970,7]]},"abstract":"<jats:p>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.<\/jats:p>\n                  <jats:p>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.<\/jats:p>\n                  <jats:p>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 \u201ccatch\u201d the small fraction of errors associated with the new methods. An example is discussed which illustrates possible areas of application for the new methods.<\/jats:p>\n                  <jats:p>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.<\/jats:p>","DOI":"10.1145\/362686.362692","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T07:34:59Z","timestamp":1027755299000},"page":"422-426","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5732,"title":["Space\/time trade-offs in hash coding with allowable errors"],"prefix":"10.1145","volume":"13","author":[{"given":"Burton H.","family":"Bloom","sequence":"first","affiliation":[{"name":"Computer Usage Company, Newton Upper Falls, MA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[1970,7]]},"reference":[{"key":"e_1_2_1_1_2","doi-asserted-by":"publisher","DOI":"10.1145\/363744.363776"},{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/362851.362880"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/362851.362882"}],"container-title":["Communications of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/362686.362692","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/362686.362692","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T19:44:15Z","timestamp":1750275855000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/362686.362692"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1970,7]]},"references-count":3,"journal-issue":{"issue":"7","published-print":{"date-parts":[[1970,7]]}},"alternative-id":["10.1145\/362686.362692"],"URL":"https:\/\/doi.org\/10.1145\/362686.362692","relation":{},"ISSN":["0001-0782","1557-7317"],"issn-type":[{"value":"0001-0782","type":"print"},{"value":"1557-7317","type":"electronic"}],"subject":[],"published":{"date-parts":[[1970,7]]},"assertion":[{"value":"1970-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}