[prev] 48 [next]

Hashing and pmr (cont)

Multi-attribute hashing parameters:
  • file size = b = 2d pages   ⇒   use d-bit hash values
  • relation has n attributes:   a1, a2, ...an
  • attribute ai has hash function hi
  • attribute ai contributes di bits (to the combined hash value)
  • total bits d = ∑i=1n di
  • a choice vector (cv) specifies for all k ...
    bit j from hi(ai) contributes bit k in combined hash value