Most data repositories contain attributes that are missing data. It is important to derive techniques to access these databases efficiently. Known indexing techniques for multi-dimensional data search like grid files, R-Trees and all its variants, break down in terms of performance when the indexed attributes contain missing data. We adapt bitmap indexes and VA-files for indexing databases with missing data that scale well in the presence of high data set dimensionality.