Eine Lösung wäre ein 'sparse Array'.
Als Implementierung könntest du eine Hashmap nehmen, ein Datenstruktur, um sehr schnell zu einem Schlüssel ein bestimmtes Datum zu speichern bzw. suchen. Als Schlüssel verwendest Du deinen mehrdimensionalen Index. Natürlich wird die Anwendung etwas langsamer, aber der Faktor ist nicht so hoch.
Hier ist so eine Hashmap.