stream lib

Keterangan

Pustaka Java untuk meringkas data dalam aliran yang tidak memungkinkan untuk menyimpan semua peristiwa. Lebih khusus lagi, ada kelas untuk memperkirakan: kardinalitas (yaitu menghitung sesuatu); menetapkan keanggotaan; elemen dan frekuensi top-k. Salah satu fitur yang sangat berguna adalah penduga kardinalitas dengan konfigurasi yang kompatibel dapat digabungkan dengan aman.

Kelas-kelas ini dapat digunakan secara langsung dalam proyek JVM atau dengan skrip shell yang disediakan dan pengalihan Unix IO lama yang bagus.

Ide-ide di sini tidak orisinal bagi kami. Kami telah berupaya untuk menciptakan implementasi yang bermanfaat dengan mengulangi literatur akademis yang ada. Oleh karena itu perpustakaan ini sangat bergantung pada karya orang lain. Silakan baca bagian Sumber dan Referensi.

Contoh

 $ echo -e "foonfoonbar" | ./bin/topk
item count error
---- ----- -----
 foo     2     0
 bar     1     0

Item count: 3


$ echo -e "foonfoonbar" | ./bin/cardinality
Item Count Cardinality Estimate
---------- --------------------
         3                    2

Artefak Maven

< dependency >
  < groupId >com.clearspring.analytics</ groupId >
  < artifactId >stream</ artifactId >
  < version >2.9.5</ version >
</ dependency >

Bangunan

Dengan asumsi Anda telah menginstal dan mengkonfigurasi Apache Maven:

 mvn package

Dan Anda harus sudah siap.

Tempat Orang Nongkrong

Milis: http://groups.google.com/group/stream-lib-user

Sumber

Kode keanggotaan yang ditetapkan adalah implementasi Bloom Filter dari Apache Cassandra sekitar bulan Desember 2009. Perubahan di sini minimal dan bertujuan untuk pengujian dan penggunaan independen. Header Apache Software Foundation telah dipertahankan pada file ini. Selain itu, kami juga menyertakan murmurhash.

Kami terinspirasi untuk menggunakan kode ini melalui postingan Jonathan Ellis Semua yang ingin Anda ketahui tentang menulis filter mekar.

Referensi

Ada referensi javadoc untuk makalah tertentu. Ini adalah hal-hal yang menurut kami paling relevan selama penelitian kami.

Kardinalitas

• Min Cai, Jianping Pan, Yu K. Kwok, dan Kai Hwang. Pengukuran matriks lalu lintas yang cepat dan akurat menggunakan penghitungan kardinalitas adaptif. Dalam MineNet '05: Proceedings of the 2005 ACM SIGCOMM workshop on Mining network data, halaman 205–206, New York, NY, USA, 2005. ACM.

• Ahmed Metwally, Divyakant Agrawal, dan Amr E. Abbadi. Mengapa menggunakan logaritmik jika kita bisa menggunakan linear?: Menuju penghitungan lalu lintas penelusuran yang efektif dan berbeda. Dalam EDBT '08: Proceedings of the 11th international conference on Extending database technology, halaman 618–629, New York, NY, USA, 2008. ACM.

• Nikos Ntarmos, Peter Triantafillou, dan Gerhard Weikum. Menghitung secara luas: Estimasi kardinalitas yang efisien dalam jaringan data Skala Internet. Dalam ICDE '06: Proceedings of the 22nd International Conference on Data Engineering, halaman 40+, Washington, DC, AS, 2006. IEEE Computer Society.

• Marianne Durand dan Philippe Flajolet. LogLog menghitung kardinalitas besar. Dalam ESA03, volume 2832 LNCS, halaman 605–617, 2003.

• Kyu Y. Whang, Brad T. Vander Zanden, dan Howard M. Taylor. Algoritme penghitungan probabilistik waktu linier untuk aplikasi database. ACM Trans. Sistem Basis Data, 15(2):208–229, 1990.

• Moses Charikar, Kevin Chen, dan Martin F. Colton. Menemukan item yang sering muncul dalam aliran data. Dalam ICALP '02: Prosiding Kolokium Internasional ke-29 tentang Automata, Bahasa dan Pemrograman, halaman 693–703, London, Inggris, 2002. Springer-Verlag.

• Stefan Heule, Marc Nunkesser, Alex Hall. HyperLogLog dalam Praktek: Rekayasa Algoritma dari Algoritma Estimasi Kardinalitas yang Canggih. Prosiding Konferensi EDBT 2013, ACM, Genoa, Italia

Atas-K

• Graham Cormode dan S. Muthukrishnan. Ringkasan aliran data yang ditingkatkan: Sketsa Count-Min dan penerapannya. halaman 29–38.

2004. 10.1016/j.jalgor.2003.12.001 http://dl.acm.org/itation.cfm?id=1073718

• Cheqing Jin, Weining Qian, Chaofeng Sha, Jeffrey X. Yu, dan Aoying Zhou. Mempertahankan item yang sering digunakan secara dinamis melalui aliran data. Dalam CIKM '03: Prosiding konferensi internasional kedua belas tentang Manajemen Informasi dan Pengetahuan, halaman 287–294, New York, NY, AS, 2003. ACM. 10.1145/956863.956918 http://dl.acm.org/itation.cfm?id=956918

• Ahmed Metwally, Divyakant Agrawal, dan Amr Abbadi. Komputasi yang efisien atas elemen frequent dan top-k dalam aliran data. halaman 398–412. 2005. 10.1007/978-3-540-30570-5_27 http://link.springer.com/chapter/10.1007/978-3-540-30570-5_27

Frekuensi

• Graham Cormode dan S. Muthukrishnan. Ringkasan aliran data yang ditingkatkan: Sketsa Count-Min dan penerapannya. 2004. 10.1016/j.jalgor.2003.12.001 http://dl.acm.org/itation.cfm?id=1073718