Memory versus error trade-offs in binary-valued retrieval problems

Question-answering systems have been studied from the viewpoint of achieving drastic savings of storage with a small error tolerance. A system is called elastic if a drastic memory saving may be achieved by tolerating a low level of indefiniteness of the answer. A necessary condition for the system to be elastic is that the query sets exhibit diverging redundancy. In the binary-valued retrieval problems discussed by P. Elias and R.A. Flower (1975), a system that admits the set of all binary questions regarding an arbitrary binary data with the highest redundance has been shown to be inelastic. On the other hand, a system that admits the exact match question set regarding an arbitrary binary data with the second highest redundancy is found to be elastic.