Системен дизайн на 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
Очевидно не мога да гласувам за затваряне на въпрос, за който някой друг е предложил награда, но за мен този въпрос изглежда извън темата/твърде широк: има много технологии и области на изследване, свързани с тази тема, и няма начин отговорът може да ги капсулира по друг начин, освен чрез свързване към някакъв по-подходящ ресурс, като например учебник или специален уебсайт. За да перифразираме едно от насоките в центъра за помощ: ако можете да си представите цяла кариера или бизнес план въз основа на намирането на отговора, въпросът вероятно е твърде широк.   -  person IMSoP    schedule 17.05.2014

Отговори (2)


arrow_upward
5
arrow_downward

Ами... намирането на най-добрите К термини всъщност не е голям проблем. Една от ключовите идеи в тези области е идеята за „поточна обработка“, т.е. да се извърши операцията с едно преминаване на данните и да се жертва известна точност, за да се получи вероятностен отговор. Следователно приемете, че получавате поток от данни като следния:

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 е малък, това всъщност не е голям проблем. Но щом попаднете в областта на регистрационните файлове за търсене с милиарди или трилиони уникални търсения, потреблението на пространство започва да се превръща в проблем.

И така, хората излязоха с идеята за „броене-скици“ (можете да прочетете повече тук: отчитане на мин. страница със скици в wikipedia). Тук поддържате хеш таблица 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 е очакваната стойност на израза, а броят е броят пъти, в които 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