Яндекс Лабс в Palo Alto набирает С++ developers

[Интеррапт]

пример конечно не очень хороший но достаточно для того чтоб показать что количество нодов будет меньше чем символов в наборе поисковых запросов.

Пример очень плохой. Потому что вы нарисовали дерево Хаффмана, но вы не нарисовали сами данные, которые этим деревом кодироваться будут. Дерево только алгоритм кодирования символов содержит, но не содержит сами данные, которые этим деревом будут кодироваться.

Ну мне показалось что это префиксное дерево а не дерево Хоффмана

Возможно. Я больше по описанию ориентировался. Что там нарисовано - я не совсем понял.

[Tarasik]

Отлично, вам нужно 8 нодов, в которых 8 символов, и еще 7 ссылок между ними = 7 * 4 = 28 байт. Сильная компрессия получилась?

Я вам больше скажу - надо еще флажок для того, чтоб показать является ли нода концом слова и int или даже long для того чтоб показать сколько раз эта буква встречается. Так же и обычего дерево Хафмана не сжимает если текст короткий потому что надо сохранять дерево вместе с последовательностью битов чтоб правильно восстановить.
Но для запросов которые встречаются по http://www.google.com/trends/hottrends 200000+ раз экономия получается значительная. Так для Maveriсs нам понадобится ветка длиной 8 нод которой мы зашифруем 200000+ запросов (1600000 юникод символов). Конечно менее встечаемые поиски не будут кодироваться так эффективно но экономия все равно будет. Вобщем памяти хватит.

[Интеррапт]

Каким образом это разумно позволит запроцессить файл с млрд запросов?

Ес-но, если время подсчета некритично (ну типа мы раз в несколько часов обрабатываем эти млрд запросов), то есть намного более простые способы, особенно для таких вещей как поисковые термины, где мы можем позволить себе некоторые "вольности", т.к. в случае небольшой ошибки - ничего страшного не случится. Как вариант - lossy counting алгоритм, который позволяет приблизительно прикинуть частоту встречаемости элементов, причем в один проход по потоку.

[Tarasik]

пример конечно не очень хороший но достаточно для того чтоб показать что количество нодов будет меньше чем символов в наборе поисковых запросов.

Пример очень плохой. Потому что вы нарисовали дерево Хаффмана, но вы не нарисовали сами данные, которые этим деревом кодироваться будут. Дерево только алгоритм кодирования символов содержит, но не содержит сами данные, которые этим деревом будут кодироваться.

Ну мне показалось что это префиксное дерево а не дерево Хоффмана

Возможно. Я больше по описанию ориентировался. Что там нарисовано - я не совсем понял.

Да, я пытаюсь зашифровать список поисковых запросов "расширенным" префиксным деревом. Расширенным потому что в каждой ноде нужно хранить только один символ и флаг является ли эта нода листом (концом слова). Этого достаточно чтоб 1) восстановить список фраз без потерь 2) найти самую встречающуюся фразу за один проход по дереву.
Ах, да. Если дерево кодировать live по мере того как поступают запросы то будет совсем быстро - быстро обновили дерево и так же быстро можно из него прочитать. То есть буквально достаточно быстро чтоб полностью и абсолютно точно гуглмугл вам возвращал список по мере как вы печатаете.
Но даже если препарировать сырые логи - будет быстрей чем эти сортировки или МР с той же точностью. Но медленнее чем семплирование, зато точно как аптеке.

[crypto5]

Отлично, вам нужно 8 нодов, в которых 8 символов, и еще 7 ссылок между ними = 7 * 4 = 28 байт. Сильная компрессия получилась?

Конечно менее встечаемые поиски не будут кодироваться так эффективно но экономия все равно будет.

Ну да, и если вдруг окажется что таких запросов миллиард вся ваша схема накрылась медным тазом.

[Tarasik]

Отлично, вам нужно 8 нодов, в которых 8 символов, и еще 7 ссылок между ними = 7 * 4 = 28 байт. Сильная компрессия получилась?

Конечно менее встечаемые поиски не будут кодироваться так эффективно но экономия все равно будет.

Ну да, и если вдруг окажется что таких запросов миллиард вся ваша схема накрылась медным тазом.

Миллиард уникальных запросов ? Хахаха. Человечество не такое умное. Мы все мыслим (научены мыслить) достаточно шаблонно, иначе сингулярности не стоило бы ожидать.

[crypto5]

Отлично, вам нужно 8 нодов, в которых 8 символов, и еще 7 ссылок между ними = 7 * 4 = 28 байт. Сильная компрессия получилась?

Конечно менее встечаемые поиски не будут кодироваться так эффективно но экономия все равно будет.

Ну да, и если вдруг окажется что таких запросов миллиард вся ваша схема накрылась медным тазом.

Миллиард уникальных запросов ? Хахаха. Человечество не такое умное. Мы все мыслим (научены мыслить) достаточно шаблонно, иначе сингулярности не стоило бы ожидать.

Оказывается умное: "15% of the searches we see everyday we’ve never seen before" http://www.google.com/competition/howgo ... works.html
При этом они кажется 2 миллиарда запросов каждый день обрабатывают, т.е. за неделю легко набирается миллиард новых уникальных запросов

[Tarasik]

Отлично, вам нужно 8 нодов, в которых 8 символов, и еще 7 ссылок между ними = 7 * 4 = 28 байт. Сильная компрессия получилась?

Конечно менее встечаемые поиски не будут кодироваться так эффективно но экономия все равно будет.

Ну да, и если вдруг окажется что таких запросов миллиард вся ваша схема накрылась медным тазом.

ХОтя даже если миллиард уникальных запросов то нам понадобится дерево из нод количеством равным количеству сумме количества символов в миллиарде запросов. Ну грубо 10 миллиардов. По 5 байтов на нод. 50 гигабайт. У меня на работе поместится - как раз 64 гб памяти.

[crypto5]

Отлично, вам нужно 8 нодов, в которых 8 символов, и еще 7 ссылок между ними = 7 * 4 = 28 байт. Сильная компрессия получилась?

Конечно менее встечаемые поиски не будут кодироваться так эффективно но экономия все равно будет.

Ну да, и если вдруг окажется что таких запросов миллиард вся ваша схема накрылась медным тазом.

ХОтя даже если миллиард уникальных запросов то нам понадобится дерево из нод количеством равным количеству сумме количества символов в миллиарде запросов. Ну грубо 10 миллиардов. По 5 байтов на нод. 50 гигабайт. У меня на работе поместится - как раз 64 гб памяти.

У вас только указатель на нод на 64битной архитектуре 8 байт будет занимать, какие 5 байтов?

[Леонид Ильич Брежнев]

Вы сама беспомощность ))
Вот тут 20 миллионов запросов, можете к каждому запросу пределать стоо раз случайный префикс и суфикс и получится 2 млрд запросов, и с ними играйтесь http://www.gregsadetsky.com/aol-data/

О, спасибо огромное. Это то что надо для эксперимента.

[Tarasik]

При этом они кажется 2 миллиарда запросов каждый день обрабатывают, т.е. за неделю легко набирается миллиард новых уникальных запросов

Задача изначально была про миллиард записей вообще. Из них 15% уникальных - ну чтож, зато остальные хорошо сжимаются в дереве. При чем я сомневаюсь что эти 15% будут хоть немного близко к самым часто встречающимся, Джастин Бибер (не к ночи вспомнил) как был так и будет вверху, так что их может быть надо заносить в отдельное дерево.

[Tarasik]

Вы сама беспомощность ))
Вот тут 20 миллионов запросов, можете к каждому запросу пределать стоо раз случайный префикс и суфикс и получится 2 млрд запросов, и с ними играйтесь http://www.gregsadetsky.com/aol-data/

О, спасибо огромное. Это то что надо для эксперимента.

Оттудова не качает, если скачает то скажите как у вас это получилось и\или залейте на торрент дорогой Леонид Ильич.

[crypto5]

При этом они кажется 2 миллиарда запросов каждый день обрабатывают, т.е. за неделю легко набирается миллиард новых уникальных запросов

Задача изначально была про миллиард записей вообще. Из них 15% уникальных - ну чтож, зато остальные хорошо сжимаются в дереве. При чем я сомневаюсь что эти 15% будут хоть немного близко к самым часто встречающимся, Джастин Бибер (не к ночи вспомнил) как был так и будет вверху, так что их может быть надо заносить в отдельное дерево.

Задача кажется была про "миллиарды".

[crypto5]

Вы сама беспомощность ))
Вот тут 20 миллионов запросов, можете к каждому запросу пределать стоо раз случайный префикс и суфикс и получится 2 млрд запросов, и с ними играйтесь http://www.gregsadetsky.com/aol-data/

О, спасибо огромное. Это то что надо для эксперимента.

Оттудова не качает, если скачает то скажите как у вас это получилось и\или залейте на торрент дорогой Леонид Ильич.

Я отсюда кажется скачал: http://www.infochimps.com/datasets/aol-search-data

[Tarasik]

Отлично, вам нужно 8 нодов, в которых 8 символов, и еще 7 ссылок между ними = 7 * 4 = 28 байт. Сильная компрессия получилась?

Конечно менее встечаемые поиски не будут кодироваться так эффективно но экономия все равно будет.

Ну да, и если вдруг окажется что таких запросов миллиард вся ваша схема накрылась медным тазом.

ХОтя даже если миллиард уникальных запросов то нам понадобится дерево из нод количеством равным количеству сумме количества символов в миллиарде запросов. Ну грубо 10 миллиардов. По 5 байтов на нод. 50 гигабайт. У меня на работе поместится - как раз 64 гб памяти.

У вас только указатель на нод на 64битной архитектуре 8 байт будет занимать, какие 5 байтов?

Хорошо, 256 Гб. Тоже не так страшно. А как вы собрались это сортировать, считать count и брать топ от них на одном компьютере ? МР тоже займет неплохо времени для этого.

[crypto5]

Конечно менее встечаемые поиски не будут кодироваться так эффективно но экономия все равно будет.

Ну да, и если вдруг окажется что таких запросов миллиард вся ваша схема накрылась медным тазом.

ХОтя даже если миллиард уникальных запросов то нам понадобится дерево из нод количеством равным количеству сумме количества символов в миллиарде запросов. Ну грубо 10 миллиардов. По 5 байтов на нод. 50 гигабайт. У меня на работе поместится - как раз 64 гб памяти.

У вас только указатель на нод на 64битной архитектуре 8 байт будет занимать, какие 5 байтов?

Хорошо, 256 Гб.

Можете набросать формат вашего нода в виде C структуры, которая займет 25 байт?

Тоже не так страшно. А как вы собрались это сортировать, считать count и брать топ от них на одном компьютере ? МР тоже займет неплохо времени для этого.

Я как то недавно 100ГБбайтные файлы на своем лаптопе сортировал, часа 2-3 на файл уходит. Это на старом лаптопе с 8ГБ РАМ, он сортирует блоки по 8БГ а потом их сливает. Если компьютер будет с 256ГБ, то наверное даже быстрее будет.
При этом у линукса сейчас sort многопоточный, а вам еще нужно будет попотеть что бы хорошо масштабируемое concurrent trie заимплементить.

[Интеррапт]

Зачем все эти сложности? Чем lossy counting алгоритм плох, чтобы найти эти самые top 10? На миллиардах записях даст отличную точность.

[crypto5]

Зачем все эти сложности? Чем lossy counting алгоритм плох, чтобы найти эти самые top 10? На миллиардах записях даст отличную точность.

Ну это уже две разные задачи, отличная точность и 100% точный результат.

[Леонид Ильич Брежнев]

Вы сама беспомощность ))
Вот тут 20 миллионов запросов, можете к каждому запросу пределать стоо раз случайный префикс и суфикс и получится 2 млрд запросов, и с ними играйтесь http://www.gregsadetsky.com/aol-data/

О, спасибо огромное. Это то что надо для эксперимента.

Оттудова не качает, если скачает то скажите как у вас это получилось и\или залейте на торрент дорогой Леонид Ильич.

Я хотел в университете скачать, так что не проверил сразу. Но да, не качается.
По второму линку все много лучше. Hачалось. 27 минут ETA.

[crypto5]

На самом деле мне кажется если разбить датасет скажем на 1000 частей, и в каждом точно посчитать топ 10к запросов, а потом слить результаты, то 10 запросов посчитаются с 100% точностью.

[Интеррапт]

Зачем все эти сложности? Чем lossy counting алгоритм плох, чтобы найти эти самые top 10? На миллиардах записях даст отличную точность.

Ну это уже две разные задачи, отличная точность и 100% точный результат.

А где там было в задаче про "отличную точность"? Может я чего-то пропустил? Berlaga вон сказал, что там вообще про sampling ответ ожидался. А lossy counting по точности sampling порвет как тузик грелку и на большом кол-ве записей (ес-но если не предполагать, что все записи встречаются с приблизительно одинаковой частотой) - выдаст именно те самые искомые top 10 скорее всего с точностью близкой к тем самым 100%. А что еще нужно для поисковых терминов?

[Интеррапт]

На самом деле мне кажется если разбить датасет скажем на 1000 частей, и в каждом точно посчитать топ 10к запросов, а потом слить результаты, то 10 запросов посчитаются с 100% точностью.

Обоснование есть по поводу "100% точности"?

[Леонид Ильич Брежнев]

На самом деле мне кажется если разбить датасет скажем на 1000 частей, и в каждом точно посчитать топ 10к запросов, а потом слить результаты, то 10 запросов посчитаются с 100% точностью.

Это была моя идея 5 страниц назад.

[crypto5]

На самом деле мне кажется если разбить датасет скажем на 1000 частей, и в каждом точно посчитать топ 10к запросов, а потом слить результаты, то 10 запросов посчитаются с 100% точностью.

Обоснование есть по поводу "100% точности"?

Лень сейчас думать, но думаю можно такие цифры подобрать что это будет работать.

[crypto5]

Зачем все эти сложности? Чем lossy counting алгоритм плох, чтобы найти эти самые top 10? На миллиардах записях даст отличную точность.

Ну это уже две разные задачи, отличная точность и 100% точный результат.

А где там было в задаче про "отличную точность"? Может я чего-то пропустил? Berlaga вон сказал, что там вообще про sampling ответ ожидался. А lossy counting по точности sampling порвет как тузик грелку и на большом кол-ве записей (ес-но если не предполагать, что все записи встречаются с приблизительно одинаковой частотой) - выдаст именно те самые искомые top 10 скорее всего с точностью близкой к тем самым 100%. А что еще нужно для поисковых терминов?

Берлага нам рассказал о том что у интервьюера было спрятано в кармане. Про точность в изначальном условии задачи я ничего не утверждал.
Мы с Тарасиком обсуждали точную оценку.