Произвольный доступ к большому двоичному файлу

У меня есть большой двоичный файл (12 ГБ), из которого я хочу собрать на лету двоичный файл меньшего размера (16 КБ) . Предположим, что файл находится на диске, и байты меньшего файла распределены в большом двоичном файле случайным образом. Как это сделать лучше и быстрее всего? До сих пор мне не удавалось сделать лучше, чем примерно три минуты.

То, что я пробовал, и которые имеют более или менее одинаковую производительность:

1. Преобразование файла в формат HDF5 и использование интерфейса C ( медленно).
2. Написание небольшой программы на C для fseek () через файл (медленно).

Как я могу получить произвольный доступ к этим данным действительно быстро ?

Я хочу получить меньше чем пара секунд на запрос.