The DOI matches its Crossref record; 12 of the 12 references it cites were found in a registry or an index.
Fast hash table lookup using extended bloom filter: an aid to network processing
Open accessAbstract
Hash tables are fundamental components of several network processing algorithms and applications, including route lookup, packet classification, per-flow state management and network monitoring. These applications, which typically occur in the data-path of high-speed routers, must process and forward packets with little or no buffer, making it important to maintain wire-speed throughout. A poorly designed hash table can critically affect the worst-case throughput of an application, since the number of memory accesses required for each lookup can vary. Hence, high throughput applications require hash tables with more predictable worst-case lookup performance. While published papers often assume that hash table lookups take constant time, there is significant variation in the number of items that must be accessed in a typical hash table search, leading to search times that vary by a factor of four or more.We present a novel hash table data structure and lookup algorithm which improves the performance over a naive hash table by reducing the number of memory accesses needed for the most time-consuming lookups. This allows designers to achieve higher lookup performance for a given memory bandwidth, without requiring large amounts of buffering in front of the lookup engine. Our algorithm extends the multiple-hashing Bloom Filter data structure to support exact matches and exploits recent advances in embedded memory technology. Through a combination of analysis and simulations we show that our algorithm is significantly faster than a naive hash table using the same amount of memory, hence it can support better throughput for router applications that use hash tables.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Rayward-Smith, V. J. (1991) · Journal of the Operational Research Society · doi:10.1057/jors.1991.155 · Cited by 16,821
Space/time trade-offs in hash coding with allowable errors
Bloom, B. H. (1970) · Communications of the ACM · doi:10.1145/362686.362692 · Cited by 7,492
Bro: a system for detecting network intruders in real-time
Paxson, V. (1999) · Computer Networks · doi:10.1016/s1389-1286(99)00112-7 · Cited by 2,636
Universal classes of hash functions
Carter, J. L., & Wegman, M. N. (1979) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(79)90044-8 · Cited by 2,519
Summary cache: a scalable wide-area Web cache sharing protocol
Fan, L., Cao, P., Almeida, J., & Broder, A. Z. (2000) · IEEE/ACM Transactions on Networking · doi:10.1109/90.851975 · Cited by 1,811
(2004) · IEEE Security & Privacy Magazine · doi:10.1109/msp.2004.9 · Cited by 1,518
Packet classification using tuple space search
Srinivasan, V., Suri, S., & Varghese, G. (1999) · Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication · doi:10.1145/316188.316216 · Cited by 495
Deep packet inspection using parallel bloom filters
Dharmapurikar, S., Krishnamurthy, P., Sproull, T. S., & Lockwood, J. W. (2004) · IEEE Micro · doi:10.1109/mm.2004.1268997 · Cited by 435
Self-citationEstan, C., Keys, K., Moore, D., & Varghese, G. (2004) · Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications · doi:10.1145/1015467.1015495 · Cited by 351
Longest prefix matching using bloom filters
Dharmapurikar, S., Krishnamurthy, P., & Taylor, D. E. (2003) · Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications · doi:10.1145/863955.863979 · Cited by 215
Self-citation
Cited by
Cuckoo Filter: Practically Better Than Bloom
Fan, B., Andersen, D. G., Kaminsky, M., & Mitzenmacher, M. D. (2014) · Proceedings of the 10th ACM International on Conference on emerging Networking Experiments and Technologies · doi:10.1145/2674005.2674994 · Cited by 737
Theory and Practice of Bloom Filters for Distributed Systems
Tarkoma, S., Rothenberg, C. E., & Lagerspetz, E. (2012) · IEEE Communications Surveys & Tutorials · doi:10.1109/surv.2011.031611.00024 · Cited by 518
Big data: From beginning to future
Yaqoob, I., Hashem, I. A. T., Gani, A., Mokhtar, S., Ahmed, E., Anuar, N. B., & Vasilakos, A. V. (2016) · International Journal of Information Management · doi:10.1016/j.ijinfomgt.2016.07.009 · Cited by 410
Can WhatsApp benefit from debunked fact-checked stories to reduce misinformation?
Reis, J. C. S., Melo, P., Garimella, K., & Benevenuto, F. (2020) · Harvard Kennedy School Misinformation Review · doi:10.37016/mr-2020-035 · Cited by 46
Metadata
- Authors
- Song, H., Dharmapurikar, S., Turner, J., & Lockwood, J.
- Venue
- Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications
- Publisher
- ACM
- Published
- 2005-08-22
- Pages
- 181-192
- OpenAlex
- W2125770033
- Cited by
- 328
- References
- 12
- FWCI
- 14.76
- Type
- conference paper
- Language
- en
- Open access
- bronze
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
How to cite
Cite CoChat for the checks on this page, and the paper for its own findings.
- This page
- CoChat. (2026). Citation check: Fast hash table lookup using extended bloom filter: an aid to network processing. https://app.cochat.ai/papers/10.1145/1080091.1080114
- The paper
- Song, H., Dharmapurikar, S., Turner, J., & Lockwood, J. (2005). Fast hash table lookup using extended bloom filter: an aid to network processing. Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications. https://doi.org/10.1145/1080091.1080114
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.