Maybe I misunderstood your problem, but how about a relational DB model with:

- FEATURES table (~400k rows), primary key: Feature_ID

- SAMPLES table (tens of thousands), primary key: Sample_ID

- OCCURRENCE table (what you observed), with the fields Feature_ID, Sample_ID, Occurrence_Count.

This is pretty much a standard solution well proven in data warehousing...