Data Structures and Algorithms Lecture Notes

27 April 2011 • Hashing In Practice

---

Outline

• Bloom filters.
• Distributed hash tables.

Naughty-Word Blocking

• When blocking web pages with naughty words, it’s important to err on the side of caution.
  • Sometimes block pages with no naughty words (minimize false positives).
  • Never leave unblocked a page with naughty words (no false negatives).
• Provide an algorithm that answers the question “Is this word naughty?”

Conditions

• Every naughty word must return “yes” (no false negatives).
• Occasionally a good word may return “yes” (some false positives).
  • For some definition of “occasionally.”
• The word file may be preprocessed.
• The word file changes, but infrequently (daily or weekly, say).
• Make the solution fast and small.

Possible Solutions

• Three candiate data structures are sorted arrays, balanced binary search trees, and hash tables.
• Choosing by time:
  • A sorted array or a balanced binary tree answers questions exactly with O(log n) work.
  • A hash table answers questions exactly with constant work on average but with O(n) work in the worst case.

Chosing By Space

• An array (sorted or not) takes the least space.
• Unused buckets make a hash table less space efficient than an array.
  • And good performance needs large scatter tables.
• A bst is less space efficient than an array due to pointer overhead.
  • And is probably less space efficient than a hash table.

Choosing by Compression

• Storing a few million words is expensive in space.
• Compressing word lists is relatively easy.
  • All three data structures can exploit a compressed word list.
• Which data structure itself can acheive the most compression?
  • And at what run-time cost?

Compressing Hash Tables

• The problem lets “yes” answers be wrong occasionally.
  • “No” answers must always be right.
• Hashing has no false negatives, but may have false positives.
  • A word in the table will always be found.
  • A word not in the table may sometimes be found.

Collisions

• A collision may cause a false positive.
• But false positives are acceptable at some low occurrence rate.
• And so collisions don’t need to be resolved, or even checked for.
• Words don’t need to be stored in the hash table.
  • Just their presence in a bucket.
  • That takes one bit.

Bloom Filters

• A Bloom filter is a hash table with one-bit buckets.

  bool table[N] = { false }
  
  void add(k)
    table[h(k)] = true
  
  bool find(k)
    return table[h(k)]
  
  unsigned hash(k)
    return ( /* whatever */ ) % N
  

Space Analysis.

• /usr/share/dict/american-english has 98,568 words in 931,467 bytes.
• bzip2 compresses this down to 333,414 bytes or 2.6×10⁶ bits.
  • Stored in an array, it can be accessed with three-byte indices.

  

Space Analysis..

• An array requires 98,568×3 ≈ 300,000 + 333,414 ≈ 600,000 bytes.
• A bst requires two more pointers per node, an extra 600,000 bytes, for a total of around 1.2×10⁶ bytes.
• A Bloom filter can use 1 byte per word for a total of around 100,000 bytes.
  • The load factor 1/8 ≈ 0.13 should provide good performance.

Filtering Example

• Take american-english as the naughty-word list (≈98,500 words).
• Darwin’s Origin of the Species has 11,410 unique words.
  • 3,848 words don’t appear in american-english (are not naughty).
  • The remaining 11,410 - 3,848 = 7,562 words are in american-english (are naughty).

Experiment

Bloom Filtering

• Store american-english in a Bloom filter with around 800,000 buckets.
  • The load factor is 0.12 measured vs 0.13 calculated.
• Run each unique word in Spieces through the Bloom filter.
  • There were 3,409 words not found in the Bloom filter (and so not naughty).
• There were 3,848 - 3,409 = 439 false positives, almost one out of every nine words.
• See the code.

More Filtering Results

		load		false
buckets		factor		positives
1,300,000		0.07		317	8%
1,200,000		0.07		295	7%
1,100,000		0.09		337	8%
1,000,000		0.09		368	9%
900,000		0.10		393	10%
800,000		0.12		439	11%
700,000		0.13		538	14%
600,000		0.15		571	15%
500,000		0.17		669	17%

Improving Bloom Filters

• Bloom filter false positives (collisions) can may be reduced by increasing the hash-table size.
  • As with regular hash tables.
• Bloom filters also allow a special-case improvement: use more hash functions.
  • More 1s make arbitrary collisions more likely.
  • A specific collision pattern, however, is less likely.

Multiple Hash Functions

	Colliding over one bit.
	Colliding over a bit pattern.

Order-k Bloom Filters

• An order-k Bloom filter is a Bloom filter with k > 0 hash functions.

  void add(w)
    table[h1(w)] = ... = table[hk(w)] = true
  
  bool find(k)
    return 
      table[h1(w)] ∧ ... ∧ table[hk(w)]
  

Order-k Results

• Same set-up, 800,000 buckets.

  		load		false
  order		factor		positives
  1		0.12		439	11%
  2		0.21		162	4%
  3		0.31		98	3%
  4		0.38		82	2%
  5		0.45		79	2%

• An order-7 filter with 1.5M buckets has no false positives.

Some Of The Internet

Content Addressing

• Suppose each computation could be addressed by the content it makes available via the network?
  • Send a request to the computation holding The Last Samurai.
• Locating and addressing are dealt with in one fell swoop.

Peer-to-Peer Networks

• Peer-to-peer networks concern themselves with content distribution.
  • As opposed to data management or data analysis.

Hash Addressing

• Finding things is still a problem.
  • Not centralized (mostly) but not efficient either.
• Hash-based addressing works in other cases; why not here?
• Determine a file’s likely address from its name or other attributes.

Hash Functions

• A hash function is a function mapping a large binary number to a small binary number.
  • “Large” = 2²⁰ bits or more.
  • “Small” = 2⁷ bits or less.
• Good hash functions are random, uniform, uncorrelated, and efficient.
• Good hash functions do exist and are relatively easy to find.

Distributed Hash Functions

• To distribute a hash function h():
  • Chop h()’s range (the key space) into pieces.
  • Hash node n’s address and assign the associated piece to n.
  • Form small networks of predecessor-successor nodes for searching.
    • “Small” usually means logarithmic in the key-space size.

Lookup

• To find file f in a distributed hash table:
  • Hash f to get a key.
  • Map the key to the associated node.
  • Follow the predecessor-successor network until found, or not.

Chord

• Assume N = 2^m files and nodes and an m-bit key range.
• Nodes are arranged circularly based on increasing key value.
• A file f hashing to key k is stored at node n associated with key k' such that
  • k' ≥ k with wrap-around.
  • k' is the smallest such node-key value.

Chord Networks

• Each node has a key formed by hashing its address and other information.
• A node n’s successor is the node with the smallest key larger than n’s key.
  • n’s predecessor is the node having n as its successor.
• Nodes are arranged circularly based on increasing key value.

Chord Network Example

Chord Look-Up

• Hash file f to key k and map it to a node.
• While unsuccessful, send the query to the sucessor node.
  • Out of data node maps may lead to unsuccessful searches.
• Fail when the query dies or recirculates to the original node.
• This is an expensive linear-cost look-up.

Chord Neighbors

• Each node n with key k has m neighbors.
  • Neighbor 0 ≤ r < m of n has key k + 2^r mod N.
    • Map missing keys as was done for files.
  • The neighbor 0 is the successor.
• Neighbor list is called the finger table.
  • Each step through the finger table reduces the key space by half.

Chord Network Example

Finger-Table Look-Up

• Hash file f to key k and map it to a node.
• If unsuccessful, search the finger table for the smallest node at least k and forward the request.
  • Repeate until the search grounds out or is cancelled.
• Each look-up step reduces the search space by half for log expected time (with high probability).

Leaving Chord

• When node n leaves:
  • Its files move to n’s successor (neighbor 0).
  • Finger tables pointing to n are shifted to n’s successor.

Joining Chord

• When node n joins:
  • n initializes its finger table.
  • n recovers files from its successor.
  • Apropriate finger table entries to n’s successor are shifted to n.

Content-Addressable Network

• The content-addressable network (CAN) uses a d-dimensional key space.
• A node hashes into a zone and manages all files hashing to the zone.
• Two nodes hashing to the same zone spilt the zone.
  • The two nodes become neighbors.
• Each node’s routing table has its boundry-sharing neighbors.

CAN Example

CAN Look-Up

• A search proceeds from the requester to the responder via the shortest path between them.
• The search path is O(dn^1/d) for a d-dimentional key space.

  

References

• Space/Time Trade-offs in Hash Coding with Allowable Errors by Burton Bloom, Communications of the ACM, July 1970.
• A Survey of Peer-to-Peer Content Distribution Technologies by Stephanos Androutsellis-Theotokis and Diomidis Spinellis in ACM Computing Surveys, December, 2004.

Credits

• Jan 2005 Map of the Internet by matthewjetthall under an AT Creative Commons license.

---

This page last modified on 2010 May 22.