Системный дизайн Google Trends?

Я пытаюсь понять дизайн системы для Google Trends (или любой другой такой крупномасштабной функции тренда, как Twitter).

Задачи:

  • Необходимость обработки большого количества данных для расчета тренда.

  • Поддержка фильтрации - по времени, региону, категории и т.д.

  • Нужен способ хранения для архивирования/автономной обработки. Для поддержки фильтрации может потребоваться многомерное хранилище.

Это мое предположение (у меня нет практического опыта использования технологий MapReduce/NoSQL)

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

А также ведение списка поисков по отметке времени, региону поиска, категории и т. д.

Пример:

Поиск Kurt Cobain термина:

Kurt-> (Time stamp, Region of search origin, category ,etc.)

Cobain-> (Time stamp, Region of search origin, category ,etc.)

Вопрос:

  • Как они эффективно вычисляют частоту поискового запроса?

  • Другими словами, учитывая большой набор данных, как они находят 10 наиболее часто встречающихся элементов распределенным масштабируемым образом?


algorithm trend system
person mithya    schedule 27.09.2013    source источник
comment
Также необходимо учитывать коэффициент временного затухания   -  person Atul Gupta    schedule 13.05.2014
comment
Я думаю, что с помощью специальных структур данных, которые структурированы таким образом, чтобы ускорить поиск тенденций, данные упорядочиваются таким образом, чтобы предварительно обработать их для всех открытых функций для миллионов пользователей в Интернете.   -  person Khaled.K    schedule 15.05.2014
comment
По-видимому, я не могу проголосовать за закрытие вопроса, за который кто-то другой предложил награду, но мне этот вопрос кажется не по теме/слишком широким: существует много технологий и областей исследований, связанных с этой темой, и нет возможности answer может инкапсулировать их иначе, чем путем ссылки на какой-либо более подходящий ресурс, такой как учебник или специальный веб-сайт. Перефразируя одно из указаний в справочном центре: если вы можете представить всю карьеру или бизнес-план, основанный на поиске ответа, вопрос, вероятно, слишком широк.   -  person IMSoP    schedule 17.05.2014

Ответы (2)


arrow_upward
5
arrow_downward

Ну... найти лучшие K терминов на самом деле не большая проблема. Одной из ключевых идей в этой области была идея «потоковой обработки», то есть выполнения операции за один проход данных и жертвования некоторой точностью для получения вероятностного ответа. Таким образом, предположим, что вы получаете поток данных, подобный следующему:

A B K A C A B B C D F G A B F H I B A C F I U X A C

То, что вы хотите, это лучшие K предметов. Наивно было бы поддерживать счетчик для каждого элемента и в конце сортировать по количеству каждого элемента. Это занимает O(U) места и O(max(U*log(U), N)) времени, где U — количество уникальных элементов, а N — количество элементов в списке.

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

Так появилась идея «счетных зарисовок» (подробнее можно прочитать здесь: подсчитать минимальную страницу эскиза в Википедии). Здесь вы поддерживаете хеш-таблицу A длиной n и создаете два хэша для каждого элемента:

h1(x) = 0 ... n-1 с равномерной вероятностью

h2(x) = 0/1 каждого с вероятностью 0,5

Затем вы делаете A[h1[x]] += h2[x]. Ключевым наблюдением является то, что, поскольку каждое значение случайным образом хешируется до +/-1, E[ A[h1[x]] * h2[x] ] = count(x), где E — ожидаемое значение выражения, а count — количество раз, когда x появляется в потоке.

Конечно, проблема с этим подходом заключается в том, что каждая оценка по-прежнему имеет большую дисперсию, но с этим можно справиться, поддерживая большой набор хэш-счетчиков и беря среднее или минимальное значение из каждого набора.

С помощью этой структуры данных эскиза вы можете получить приблизительную частоту каждого элемента. Теперь вы просто ведете список из 10 элементов с самыми высокими оценками частоты до сих пор, и в конце у вас будет свой список.

person Subhasis Das    schedule 20.05.2014

arrow_upward
1
arrow_downward

Как именно это делает та или иная частная компания, скорее всего, в открытом доступе нет, а как оценивать эффективность такой системы - на усмотрение проектировщика (будь то вы или Google или кто угодно)

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

Также ознакомьтесь с некоторыми конференциями по большим данным и веб-наукам, такими как KDD или WSDM. , а также документы, выпущенные Google Research

Как спроектировать такую ​​систему сложно, правильного ответа нет, но инструменты и исследования доступны, чтобы вы могли начать.

person glxc    schedule 17.05.2014