[prev] 18 [next]

Exercise 2: Page-level SIMC Query Cost

Consider a SIMC-indexed database with the following properties
  • all pages are B = 8192 bytes
  • page descriptors have m = 4096 bits ( = 512 bytes)
  • total records r = 102,400,   records/page c = 100
  • false match probability pF = 1/1000
  • 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.