[prev] 21 [next]

Exercise 3: Bit-sliced SIMC Query Cost

Consider a SIMC-indexed database with the following properties
  • all pages are B = 8192 bytes
  • r = 102,400,   c = 100,   b = 1024
  • page descriptors have m = 4096 bits ( = 512 bytes)
  • bit-slices have b = 1024 bits ( = 128 bytes)
  • false match probability pF = 1/1000
  • query descriptor has k = 10 bits set to 1
  • answer set has 1000 tuples from 100 pages
  • 90% of false matches occur on data pages with true match
  • 10% of false matches are distributed 1 per page
Calculate the total number of pages read in answering the query.