在非常大的文件中查找最常见的三项序列

Question

我有许多网页访问日志文件,其中每次访问都与用户ID和时间戳相关联.我需要确定最受欢迎(即最常访问)的三页序列.日志文件太大,无法立即保存在主内存中.

示例日志文件:

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

相应的结果:

答:1-2-3,2-3-4
B:2-3-4
2-3-4是最受欢迎的三页序列

我的想法是使用两个哈希表.用户ID的第一个哈希并存储其序列; 第二个散列三页序列并存储每个序列出现的次数.这需要O(n)空间和O(n)时间.

但是,由于我必须使用两个哈希表,因此内存不能同时保存所有内容,而且我必须使用磁盘.经常访问磁盘效率不高.

我怎么能做得更好？

Answer 1

如果您想快速获得近似结果，请按照您的预期使用哈希表，但向每个哈希表添加一个有限大小的队列以删除最近最少使用的条目。

如果您想要准确的结果，请使用外部排序过程按用户 ID 对日志进行排序，然后组合每 3 个连续条目并再次排序，这次是按页面 ID。

更新（按时间戳排序）

可能需要一些预处理才能正确使用日志文件的时间戳：

• 如果日志文件已按时间戳排序，则无需进行预处理。
• 如果有多个日志文件（可能来自独立进程），并且每个文件都已按时间戳排序，请打开所有这些文件并使用合并排序来读取它们。
• 如果文件几乎按时间戳排序（就好像多个独立进程将日志写入单个文件），请使用二进制堆以正确的顺序获取数据。
• 如果文件未按时间戳排序（这在实践中不太可能），请使用按时间戳进行外部排序。

Update2（改进近似方法）

对于随机分布的数据，使用 LRU 队列的近似方法应该会产生相当好的结果。但网页访问在一天中的不同时间可能有不同的模式，或者在周末可能会有所不同。对于此类数据，原始方法可能会给出较差的结果。为了改善这一点，可以使用分层 LRU 队列。

将 LRU 队列划分为 log(N) 个较小的队列。大小为 N/2、N/4，...最大的一个应包含任何元素，下一个 - 仅包含元素，至少出现 2 次，下一个 - 至少出现 4 次，...如果从某个子元素中删除元素-queue，它被添加到另一个队列中，因此在被完全删除之前，它存在于层次结构较低的所有子队列中。这样的优先级队列仍然具有 O(1) 复杂度，但可以更好地近似最流行的页面。