tag:blogger.com,1999:blog-10303035.post3341157563941978078..comments2024-02-04T23:20:04.066+03:00Comments on Алёна C++: Фильтр БлумаAlenahttp://www.blogger.com/profile/09389124127364799922noreply@blogger.comBlogger20125tag:blogger.com,1999:blog-10303035.post-22546197221248942142011-03-09T15:32:36.347+03:002011-03-09T15:32:36.347+03:00Алена, один комментарий, скорее интересный для хар...Алена, один комментарий, скорее интересный для хардкорных ораклоидов и вообще DBA-шников. <br /><br />Тут в посте был пример, что фильтры блума используются в Google BigTable, - а вот тут по ссылке есть пример того, как используются они в Oracle Database.<br /><br />http://antognini.ch/papers/BloomFilters20080620.pdfAnonymoushttps://www.blogger.com/profile/00263598279369013894noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-28866285504108611242010-08-24T13:01:47.011+04:002010-08-24T13:01:47.011+04:00Ал
ёна, вы скорее ПОРОЖДАЕТЕ велосипеды, чем борет...Ал<br />ёна, вы скорее ПОРОЖДАЕТЕ велосипеды, чем боретесь с ними такими постами....Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-10303035.post-76089107029751747462010-08-12T12:36:18.478+04:002010-08-12T12:36:18.478+04:00Пост в принципе правильный, в плане велосипедизма,...Пост в принципе правильный, в плане велосипедизма, но только практически не добавляет новой информации. Мне вот очень интересно получить максимально быструю реализацию фильтра Блума на Си (не C++). Есть претенденты на эту роль?Peter A. Kurishevhttps://www.blogger.com/profile/06981634651594858218noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-76700876751405963262010-07-30T12:23:02.042+04:002010-07-30T12:23:02.042+04:00Здравствуйте, а не знаете ли вы где найти реализац...<i>Здравствуйте, а не знаете ли вы где найти реализацию фильтра на каком-либо языке?</i><br /><br />Вот, например: http://code.google.com/p/bloom/<br /><br />Погуглите, их полно...Alenahttps://www.blogger.com/profile/09389124127364799922noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-6980054807790232282010-07-29T23:32:19.408+04:002010-07-29T23:32:19.408+04:00Здравствуйте, а не знаете ли вы где найти реализац...Здравствуйте, а не знаете ли вы где найти реализацию фильтра на каком-либо языке?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-10303035.post-61168144830233828712010-07-28T13:05:46.579+04:002010-07-28T13:05:46.579+04:00А если в битовом массиве хранить вместо булевского...А если в битовом массиве хранить вместо булевского флажка ссылку на интрузивный список с элементами, получаем обычную хеш-таблицу.<br /><br />Если совместить несколько хеш-функций и ссылки вместо битов, то получается что-то отдалённо похожее на кукушкин хеш. http://blog.gamedeff.com/?p=62_winniehttps://www.blogger.com/profile/04382725998308329157noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-14584254025325408072010-07-28T02:19:05.801+04:002010-07-28T02:19:05.801+04:00_winnie
Вставка в множество за время порядка n?
...<b>_winnie</b><br /><br /><i>Вставка в множество за время порядка n?</i><br /><br />Ненененене.<br />Время добавления элемента в фильтр Блума фиксировано и равно O(k), где k - количество хеш-функций. Более того, это все еще и параллелится хорошо.<br /><br />То, что ты зацитировал, означает следующее. Ты должен примерно знать какое число элементов у тебя будет в фильтре и выбирать размер фильтра исходя из этой величины.Alenahttps://www.blogger.com/profile/09389124127364799922noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-83576499192619926522010-07-28T02:00:05.560+04:002010-07-28T02:00:05.560+04:00Из ссылки на википедию:
Как следствие, заметим, чт...Из ссылки на википедию:<br /><i>Как следствие, заметим, что для того, чтобы фильтр Блума поддерживал заданную ограниченную вероятность ложного срабатывания, размер битового массива должен быть линейно-пропорционален числу вставленных элементов.</i><br /><br />Вставка в множество за время порядка n?_winniehttps://www.blogger.com/profile/04382725998308329157noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-80263392629454571192010-07-28T00:35:37.129+04:002010-07-28T00:35:37.129+04:00sin
Предлагаю осветить еще консистентное хэширова...<b>sin</b><br /><br /><i>Предлагаю осветить еще консистентное хэширование (consistent hashing)</i><br /><br />Уже! Правда, не я. :-) Вот отличный обзор: http://www.jprogers.info/2009/11/consistent-hashing.htmlAlenahttps://www.blogger.com/profile/09389124127364799922noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-40321817315250896902010-07-28T00:21:22.904+04:002010-07-28T00:21:22.904+04:00Arsen
Алена, спасибо!
пожалуйста :-)
А можно н...<b>Arsen</b><br /><br /><i>Алена, спасибо! </i><br /><br />пожалуйста :-)<br /><br /><i>А можно немножко разжевать для тех кто в танке? </i><br /><br />да без проблем<br /><br /><i>Совсем не ясно как должны выглядеть используемые в алгоритме хеш-функции.. </i><br /><br />В учебных материалах обычно приводят примеры хеш-функций типа таких: "значение хеш-функции от строки равно длине строки". Это плохая функция, но наглядная. Пример хеш-функции из реального мира: <a href="http://en.wikipedia.org/wiki/MurmurHash" rel="nofollow">MurmurHash</a><br /><br /><i>Если размер массива m, а k - количество функций, правильно ли я понимаю, что i-ая функция осуществляет отображение в i-ый элемент массива?</i><br /><br />Нет. Вот как на приведенной у меня картинке:<br />h1(x)=1<br />h2(x)=5<br />h3(x)=13<br /><br />h1(y)=4<br />h2(y)=11<br />h3(y)=16<br /><br />h1(z)=3<br />h2(z)=5<br />h3(z)=11<br /><br /><i>Если ответом на мой вопрос является что-то в духе "хеш-функция может быть какая угодно", что вполне естественно, то совсем непонятно каким, все-таки, условиям она должна соответствовать и какие ограничения на нее наложены. Ведь, если никаких условий не наложить, то можно и здесь очередной велосипед наворотить с квадратными колесами))</i><br /><br />Про хеш-функции вообще есть в Википедии: <a href="http://en.wikipedia.org/wiki/Hash_function" rel="nofollow">Hash function</a><br /><br />Вот советы по выбору хеш-функций для фильтра Блума:<a href="http://0pointer.de/blog/projects/bloom.html" rel="nofollow"> A Few Notes on Bloom Filters</a>Alenahttps://www.blogger.com/profile/09389124127364799922noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-80594172823435906112010-07-27T23:55:15.454+04:002010-07-27T23:55:15.454+04:00Вот неплохая статья про блум фильтры с имплементац...Вот неплохая статья про блум фильтры с имплементацией на Scala: http://www.codecommit.com/blog/scala/bloom-filters-in-scala.dm3https://www.blogger.com/profile/15366444510753413450noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-3745139350242263592010-07-27T22:33:17.160+04:002010-07-27T22:33:17.160+04:002Ivan: в статье на википедии есть формулы оценки в...2Ivan: в <a href="http://en.wikipedia.org/wiki/Bloom_filter" rel="nofollow">статье на википедии</a> есть формулы оценки вероятностиAlex Otthttps://www.blogger.com/profile/13001951608173211050noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-53402603082007999442010-07-27T22:29:53.409+04:002010-07-27T22:29:53.409+04:00Интересный фильтр, интересно какова вероятность ош...Интересный фильтр, интересно какова вероятность ошибки? можеIvanhttps://www.blogger.com/profile/12162670656597520218noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-2115460254477432582010-07-27T19:51:00.410+04:002010-07-27T19:51:00.410+04:00Предлагаю осветить еще консистентное хэширование (...Предлагаю осветить еще консистентное хэширование (consistent hashing)sinhttps://www.blogger.com/profile/15995109017394706546noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-17909852759634283262010-07-27T19:36:14.603+04:002010-07-27T19:36:14.603+04:00Алена, спасибо! А можно немножко разжевать для тех...Алена, спасибо! А можно немножко разжевать для тех кто в танке? Совсем не ясно как должны выглядеть используемые в алгоритме хеш-функции.. Если размер массива m, а k - количество функций, правильно ли я понимаю, что i-ая функция осуществляет отображение в i-ый элемент массива? Если ответом на мой вопрос является что-то в духе "хеш-функция может быть какая угодно", что вполне естественно, то совсем непонятно каким, все-таки, условиям она должна соответствовать и какие ограничения на нее наложены. Ведь, если никаких условий не наложить, то можно и здесь очередной велосипед наворотить с квадратными колесами)) Может быть кто-нибудь может поделиться примером?arsenmukhttps://www.blogger.com/profile/17274550329093309296noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-88843094249393963462010-07-27T15:55:34.848+04:002010-07-27T15:55:34.848+04:00soonts
Правда непонятно как такие хэши генерироват...<b>soonts</b><br /><i>Правда непонятно как такие хэши генерировать.<br />Для hashmap достаточно шоб у разных элементов были разные хэши, а тут нужно много равновероятно установленных значащих бит.</i><br /><br />В Википедии со странички фильтра Блума есть ссылки на какие-то эпичные труды по поводу выбора хэш-функций для него. Но я их не читала.<br /><br /><i>P.S. Это soonts. OpenID опять не работает у тебя. Это уже далеко не в первый раз. Или пинай тех.поддержку google,</i> <br /><br />Их постоянно пинают. Это известная проблема, что у них OpenID отваливается.<br /><br /><i>или мигрируй нафик.</i><br /><br />лучше вы к нам :-)Alenahttps://www.blogger.com/profile/09389124127364799922noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-24434647778371202572010-07-27T15:38:05.626+04:002010-07-27T15:38:05.626+04:00Прикольно, не знал.
Правда непонятно как такие хэ...Прикольно, не знал.<br /><br />Правда непонятно как такие хэши генерировать.<br />Для hashmap достаточно шоб у разных элементов были разные хэши, а тут нужно много равновероятно установленных значащих бит.<br /><br />P.S. Это soonts. OpenID опять не работает у тебя. Это уже далеко не в первый раз. Или пинай тех.поддержку google, или мигрируй нафик.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-10303035.post-12190054190527776692010-07-27T13:38:32.082+04:002010-07-27T13:38:32.082+04:00Алёна, спасибо за ваш очень познавательный блог! О...Алёна, спасибо за ваш очень познавательный блог! Обычно описания алгоритмов скатываются в УГ. У вас их читать интересно. Ждём оставшиеся части велосипеда!Alexanderhttps://www.blogger.com/profile/08478945473702799787noreply@blogger.comtag:blogger.com,1999:blog-10303035.post-89331744653544584132010-07-27T13:11:44.896+04:002010-07-27T13:11:44.896+04:00На самом деле довольно много очаровательных своей ...На самом деле довольно много очаровательных своей простотой решений основаны на допущении ложных срабатываний. Тот же самый алгоритм Рабина-Карпа поиска подстроки.<br /><br />Самому подобное в нужный момент придумать никогда не удавалось...Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-10303035.post-2263270907191563822010-07-27T13:03:14.198+04:002010-07-27T13:03:14.198+04:00Кстати, вот этот блог может быть достаточно интере...Кстати, <a href="http://horicky.blogspot.com" rel="nofollow">вот этот блог</a> может быть достаточно интересен - человек часто пишет про основы нагруженных систем, поисковых систем и т.п.Alex Otthttps://www.blogger.com/profile/13001951608173211050noreply@blogger.com