Filtering Food Databases by Logaritmic Indeces on Quantity Constraints

Abstract

In this article we introduce the IMEE (May I Eat with Index Mask) algorithm, which we developed in the framework of the eFilter project. The goal of this project was to build up an information system, which can filter a food list by health data. The new algorithm has to decide whether the user may or may not eat a given food. To be able to do so we have to know the users health profile on eating. This profile contains constraints. We have to filter the potentially big food database according these constraints. The first algorithm in this article is the straightforward one. To speed up this algorithm we introduce an indexing mechanism, which enables us to use bitmap indexing. Bitmap indexing pays off if we have lots of records and the indexed entity has only a few possible values. The introduced method can turn a constraint into an index by indexing only those foods which contain less or equal ingredients than a value on the logarithmic scale. Unfortunately, this was we can introduce only a less or more strict condition than the original one. We assign to the generic N < ingredient content ≤ M constraint the more strict one 2^ceiling(log₂(N)) < ingredient content ≤ 2^floor(log₂(M)), we call this the greatest specific mask. The IMEE algorithm works as follows: it closes up all constraints for each food ingredient, and then computes the greatest specific masks for each such constraint, and then filters those foods from the databases which fulfil all greatest contained constraints.