stream lib
1.0.0
Java-библиотека для суммирования данных в потоки, для которых невозможно хранить все события. Более конкретно, существуют классы для оценки: мощности (т.е. подсчета вещей); установить членство; элементы top-k и частота. Одна особенно полезная функция заключается в том, что средства оценки мощности с совместимыми конфигурациями можно безопасно объединять.
Эти классы можно использовать непосредственно в проекте JVM или с предоставленными сценариями оболочки и старым добрым перенаправлением ввода-вывода Unix.
Идеи здесь не оригинальны для нас. Мы постарались создать полезные реализации, перебирая существующую научную литературу. Таким образом, эта библиотека во многом зависит от работы других. Пожалуйста, прочтите разделы «Источники» и «Справочная информация».
$ 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
< dependency >
< groupId >com.clearspring.analytics</ groupId >
< artifactId >stream</ artifactId >
< version >2.9.5</ version >
</ dependency >Предполагая, что у вас установлен и настроен Apache Maven:
mvn package
И у вас должно быть все готово.
Список рассылки: http://groups.google.com/group/stream-lib-user.
Установленный код членства представляет собой реализацию фильтра Блума из Apache Cassandra примерно в декабре 2009 года. Изменения здесь минимальны и предназначены для тестирования и независимого использования. В этих файлах были сохранены заголовки Apache Software Foundation. В качестве расширения мы также включаем мурмурхэш.
На использование этого кода нас вдохновил пост Джонатана Эллиса «Все, что вы когда-либо хотели знать о написании фильтров Блума».
Существуют ссылки в javadoc на конкретные документы. Это были те, которые мы сочли наиболее актуальными в ходе нашего исследования.
Мин Цай, Цзяньпин Пан, Ю К. Квок и Кай Хван. Быстрое и точное измерение матрицы трафика с использованием адаптивного подсчета мощности. В MineNet '05: Материалы семинара ACM SIGCOMM 2005 г. по данным горнодобывающей сети, страницы 205–206, Нью-Йорк, Нью-Йорк, США, 2005. ACM.
Ахмед Метвалли, Дивьякант Агравал и Амр Э. Аббади. Зачем идти логарифмически, если можно пойти линейно?: На пути к эффективному раздельному подсчету поискового трафика. В EDBT '08: Материалы 11-й международной конференции по расширению технологий баз данных, страницы 618–629, Нью-Йорк, Нью-Йорк, США, 2008. ACM.
Никос Нтармос, Питер Триантафиллу и Герхард Вейкум. Подсчет в целом: эффективная оценка мощности в сетях передачи данных в масштабе Интернета. В ICDE '06: Материалы 22-й Международной конференции по инженерии данных, страницы 40+, Вашингтон, округ Колумбия, США, 2006. Компьютерное общество IEEE.
Марианна Дюран и Филипп Флажоле. LogLog-подсчет больших мощностей. В ESA03, том 2832 LNCS, страницы 605–617, 2003 г.
Кю Ю. Ванг, Брэд Т. Вандер Занден и Говард М. Тейлор. Алгоритм вероятностного подсчета с линейным временем для приложений баз данных. АКМ Транс. Система баз данных, 15(2):208–229, 1990.
Моисей Чарикар, Кевин Чен и Мартин Ф. Колтон. Поиск часто встречающихся элементов в потоках данных. В ICALP '02: Материалы 29-го Международного коллоквиума по автоматам, языкам и программированию, страницы 693–703, Лондон, Великобритания, 2002. Springer-Verlag.
Стефан Хойле, Марк Нункессер, Алекс Холл. HyperLogLog на практике: алгоритмическая разработка современного алгоритма оценки мощности. Материалы конференции EDBT 2013, ACM, Генуя, Италия.
Чецин Цзинь, Вэйнин Цянь, Чаофэн Ша, Джеффри С. Ю и Аоин Чжоу. Динамическое обслуживание часто встречающихся элементов в потоке данных. В CIKM '03: Материалы двенадцатой международной конференции по управлению информацией и знаниями, страницы 287–294, Нью-Йорк, Нью-Йорк, США, 2003. ACM. 10.1145/956863.956918 http://dl.acm.org/citation.cfm?id=956918
Ахмед Метвалли, Дивьякант Агравал и Амр Аббади. Эффективное вычисление частых и топ-k элементов в потоках данных. страницы 398–412. 2005. 10.1007/978-3-540-30570-5_27 http://link.springer.com/chapter/10.1007/978-3-540-30570-5_27.
