Asonov Scheme

• Lengthy preprocesing of the database, then constant time queries.

  • Without preprocessing, need to touch every record on every query.

• Added assumption: records are numbered 1..N

• Actually query processing grows in size with every query, so need to re-preprocess quite often.