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

У меня есть много файлов журналов посещений веб-страниц, где каждое посещение связано с идентификатором пользователя и меткой времени. Мне нужно определить самую популярную (то есть наиболее часто посещаемую) трехстраничную последовательность из всех. Файлы журнала слишком велики для одновременного хранения в основной памяти.

Пример файла журнала:

User ID  Page ID
A          1
A          2
A          3
B          2
B          3
C          1
B          4
A          4

Соответствующие результаты:

A : 1-2-3 , 2-3-4
B : 2-3-4
2-3-4 - самая популярная последовательность из трех страниц

Моя идея состоит в том, чтобы использовать две хеш-таблицы. Первый хеширует идентификатор пользователя и сохраняет его последовательность; второй хэширует трехстраничные последовательности и сохраняет количество раз, когда каждая из них появляется. Это занимает O (n) пространства и O (n) времени.

Однако, поскольку мне приходится использовать две хэш-таблицы, память не может хранить все сразу, и мне приходится использовать диск. Очень часто обращаться к диску неэффективно.

Как я могу сделать это лучше?

13
задан Pops 30 December 2011 в 19:27
поделиться