Trova l'URL in alto k per l'ultimo giorno, o l'ultima ora o l'ultimo minuto?

Question

Alla domanda originale viene fornito il file contenente l'URL da 5 GB visitato lo scorso giorno, trovare il primo k URL frequente. Il problema può essere risolto utilizzando la mappa hash per contare le occorrenze dell'URL distinto e trovare il top k con l'aiuto di heap minimo, prendendo un tempo O (n log k).

Ora sto pensando a cosa succederebbe se l'input fosse un flusso di dati online illimitato (invece di file statici), quindi come posso conoscere l'URL in alto k dell'ultimo giorno?

Oppure c'è qualche miglioramento che posso apportare al sistema che mi consente di ottenere l'URL k principale per ultimo minuto e l'ultimo giorno e le ultime ore in modo dinamico?

Qualsiasi suggerimento sarà apprezzato !!

Answer 1

Se si è disposti ad accontentarsi di una risposta probabilistica che potrebbe contenere alcune voci errate, si dovrebbe assolutamente esaminare la struttura di dati count-min sketch. È stato progettato in modo specifico per stimare gli elementi frequenti in un flusso utilizzando la minor quantità possibile di memoria e la maggior parte delle implementazioni supportano un'approssimazione efficiente in termini di tempo e spazio degli elementi k superiori di un flusso. Inoltre, la struttura ti consente di ottimizzare l'utilizzo dello spazio, che lo rende ideale per situazioni come queste. IIRC Google utilizza questo per determinare le loro query di ricerca più frequenti.

Ci sono several implementations of this data structure disponibili online.

Spero che questo aiuti!