Algoritma untuk 'k' nomor paling sering terjadi

19

Saya telah mencari algoritma yang paling efisien (streaming ??) yang memberitahu saya elemen 'k' paling sering terjadi dalam aliran data di setiap titik waktu. Posting ini: "Alur dan taklukkan" algoritma aliran data membuat saya tertarik padanya.

Misalnya, anggap ada angka: (4,3,5,1,6,2,4,3,3,8,9,1) dan saya meminta 3 nomor yang paling sering muncul (katakanlah), maka saya harus dapatkan (3,4,1) sebagai jawabannya.

Saya mencoba mencari online, tetapi tidak dapat menemukan tempat yang memberikan pendekatan dan mengatakan itu yang terbaik. Solusi sepele akan menggunakan tumpukan atau pohon biner seimbang, tapi saya pikir ada cara yang lebih baik dan saya ingin tahu apakah itu didokumentasikan di suatu tempat.

Sunting: Saya mencari sebuah algoritma yang selalu memberikan jawaban yang benar sebagai lawan dari algoritma appromixation (banyak yang muncul dalam hasil pencarian) yang mengandalkan distribusi data dalam beberapa cara atau lainnya

ds.algorithms online-algorithms data-streams dhruvbird
sumber
Sebenarnya ada tiga jenis algoritma: tepat, perkiraan, dan "tergantung data". Anda mengesampingkan jenis terakhir, tetapi apakah perkiraan algoritma yang TIDAK bergantung pada distribusi data diizinkan? seperti yang saya sebutkan, jika tidak, Anda dalam masalah karena batas bawah yang diketahui untuk masalah ini dalam pengaturan aliran.
Suresh Venkat
1
Saya ingin tahu apakah algoritma yang menggunakan memori terbatas (algoritma streaming) dapat benar-benar melakukan apa yang saya inginkan dan tampaknya tidak bisa seperti yang Anda tunjukkan. Juga apakah algoritma tepat non-streaming diketahui yang memecahkan masalah dalam O (n) dijamin waktu terburuk, yang disebutkan di sini (dikutip oleh kertas oleh Cormode dan Hadjileftheriou dari tautan yang Anda berikan): citeseerx.ist.psu. edu / viewdoc / ringkasan? doi = 10.1.1.106.7889
dhruvbird

Jawaban:

20

k=1o(n)

n/k

kk

Suresh Venkat
sumber
1
+1. Saya pikir> 50% dari algoritma waktu adalah yang terkenal (algoritma elemen mayoritas) seperti yang Anda sebutkan
dhruvbird
2
Terima kasih!! Makalah yang ditulis oleh Cormode dan Hadjileftheriou yang Anda sebutkan mengutip makalah ini: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.10.10.7889 yang memiliki teknik yang sama dengan yang saya pikirkan. Itu memelihara 2 daftar tertaut; satu dengan frekuensi dan di dalamnya daftar lain dari semua elemen dengan frekuensi yang sama.
dhruvbird
dapatkah Anda menguraikan algoritma lebih dari 50 persen? dan teka-teki google? Saya tidak bisa mengikuti alasan ceroboh ini karena Anda baru saja menyentuhnya dan tidak sepenuhnya mengeluarkan "trik terkenal". Terima kasih.
Berikut tautannya: userweb.cs.utexas.edu/users/misra/scannedPdf.dir/…
Suresh Venkat
Ini adalah komentar (tidak cukup reputasi) pada tautan Suresh Venkat userweb.cs.utexas.edu/users/misra/scannedPdf.dir/… : Sepertinya algoritme yang disajikan di sana memerlukan pass kedua melalui data, yang tidak diperbolehkan sini. Bahkan, saya tidak melihat bagaimana algoritma satu-pass dengan persyaratan ruang O (1) dapat ada.
TonyK
2

Saya juga merekomendasikan membaca bagian 8.1.3 "Penelusuran Pola-Sering dalam Aliran Data" dari buku berikut:

Jiawei Han, Micheline Kamber. Penambangan Data --- Konsep dan Teknik, Edisi Kedua, Penerbit Morgan Kaufmann , 2006.

Memperkenalkan suatu algoritma, yang dikenal sebagai Lossy Menghitung , yang mendekati sering item (item yang dukungan atas beberapa min_support ) dengan presisi sewenang-wenang.

Bukan apa yang Anda inginkan, tetapi saya pikir itu mungkin membantu.

MS Dousti
sumber
mungkin Anda dapat membantu saya dalam pertanyaan saya di sini
Ben