![image](http://habrastorage.org/getpro/habr/post_images/359/364/8f7/3593648f778ed48e64b46274f9d24461.jpg)
Какова вероятность популярности новой веб-страницы?
3. Алгоритм
3.1 Система
Во-первых, давайте опишем общую систему предлагаемого алгоритма. Согласно предыдущим исследованиям в данной области [7, 16, 20], мы задаём единый источник расчета стоимости индексирования по всем страницам. Другими словами, принимаем во внимание фиксированное время
![](http://habrastorage.org/files/c99/4a0/fc9/c994a0fc978a49dabff6b8d748ec3b72.jpg)
![](http://habrastorage.org/files/c99/4a0/fc9/c994a0fc978a49dabff6b8d748ec3b72.jpg)
3.2 Метрика
Была предложена [12] следующая метрика для измерения эффективности алгоритма. Полезность страницы
![](http://habrastorage.org/files/2b0/90e/39a/2b090e39a13b476b829b81e3c9228e75.jpg)
![](http://habrastorage.org/files/53e/517/415/53e51741587a443c84b1172e43bf5ded.jpg)
![](http://habrastorage.org/files/cc0/3a6/a10/cc03a6a102c14f58ae13f4c36aa9500c.jpg)
Важно также отметить, что число кликов по странице выдачи зависит от ряда причин, включая особенности пользовательского поведения и систему ранжирования, а не только от алгоритма индексации. Поэтому не всегда очевидно как интерпретировать изменение в количестве кликов при изменении политики индексации. Так, например, меняется ли количество кликов только из-за изменения политики индексации страниц, либо зависит ещё и от метода ранжирования и тогда это количество может быть разным при применении разных одинаково хороших политик индексации? На самом деле, мы считаем, что разумней в данном случае обращаться к пользовательским логам, которые мы можем получить из данных тулбара и выбрать количество посещений как основной ориентир, который заменит нам показатель кликов — этого будет достаточно для измерения эффективности индексации. Таким образом, полезность
![](http://habrastorage.org/files/2b0/90e/39a/2b090e39a13b476b829b81e3c9228e75.jpg)
![](http://habrastorage.org/files/53e/517/415/53e51741587a443c84b1172e43bf5ded.jpg)
Как это будет показано в разделе 4.1, мы оцениваем успешность алгоритма на базе данных, собранных за один месяц. Таким образом, пусть T = 1 месяц, а
![](http://habrastorage.org/files/d4c/27f/b3e/d4c27fb3e5984e649e43bf962a07da8a.jpg)
3.3 Стратегия индексации
Как мы условились в разделе 3.1, каждые
![](http://habrastorage.org/files/c99/4a0/fc9/c994a0fc978a49dabff6b8d748ec3b72.jpg)
Для этого мы примем во внимание динамику изменения популярности следующим образом. В [12] было показано, что полезность
![](http://habrastorage.org/files/417/729/f05/417729f05685418698db0c03a94f714a.jpg)
![](http://habrastorage.org/files/6f9/f03/900/6f9f039002a6434eb697cfe34d20692e.jpg)
Таким образом, эта полезность может быть апроксимирована при помощи
![](http://habrastorage.org/files/74d/373/c51/74d373c51120413fa546ce8c062d3529.jpg)
![](http://habrastorage.org/files/ed7/dcf/da8/ed7dcfda817f49d29eaf9c65beee5499.jpg)
![](http://habrastorage.org/files/cb8/440/de8/cb8440de89274e378173cf1d2c8a51fe.jpg)
Мы можем видеть, что при
![](http://habrastorage.org/files/ae9/d39/03a/ae9d3903a0404126a4648ce80f167935.jpg)
![](http://habrastorage.org/files/f5f/831/29b/f5f83129b4cf4f55aa25951323f09f58.jpg)
![](http://habrastorage.org/files/cb8/440/de8/cb8440de89274e378173cf1d2c8a51fe.jpg)
Для каждой страницы u мы предсказываем параметры
![](http://habrastorage.org/files/ed7/dcf/da8/ed7dcfda817f49d29eaf9c65beee5499.jpg)
![](http://habrastorage.org/files/cb8/440/de8/cb8440de89274e378173cf1d2c8a51fe.jpg)
![](http://habrastorage.org/files/c99/4a0/fc9/c994a0fc978a49dabff6b8d748ec3b72.jpg)
![](http://habrastorage.org/files/c99/4a0/fc9/c994a0fc978a49dabff6b8d748ec3b72.jpg)
![](http://habrastorage.org/files/6e7/b13/083/6e7b130832574df3933eaa1bf8887df4.jpg)
![](http://habrastorage.org/files/6f9/f03/900/6f9f039002a6434eb697cfe34d20692e.jpg)
Время, когда страница была обнаружена для простоты апроксимируется со временем, когда она была создана. Поэтому мы допускаем, что первое посещение этой страницы, зафиксированное в пользовательских логах тулбара близко ко времени создания страницы.
3.4 Ожидаемая популярность страницы
В этом разделе мы рассмотрим метод прогнозирования параметров
![](http://habrastorage.org/files/ed7/dcf/da8/ed7dcfda817f49d29eaf9c65beee5499.jpg)
![](http://habrastorage.org/files/cb8/440/de8/cb8440de89274e378173cf1d2c8a51fe.jpg)
![](http://habrastorage.org/files/ed7/dcf/da8/ed7dcfda817f49d29eaf9c65beee5499.jpg)
![](http://habrastorage.org/files/ed7/dcf/da8/ed7dcfda817f49d29eaf9c65beee5499.jpg)
![](http://habrastorage.org/files/ed7/dcf/da8/ed7dcfda817f49d29eaf9c65beee5499.jpg)
![](http://habrastorage.org/files/7fd/002/f11/7fd002f11405449db28acf59e3dbec10.jpg)
Мы также определяем спад популярности
![](http://habrastorage.org/files/cb8/440/de8/cb8440de89274e378173cf1d2c8a51fe.jpg)
![](http://habrastorage.org/files/05b/5b6/f2e/05b5b6f2ea7746a293f7cd92ad9c97e6.jpg)
![](http://habrastorage.org/files/05b/5b6/f2e/05b5b6f2ea7746a293f7cd92ad9c97e6.jpg)
![](http://habrastorage.org/files/094/390/f9b/094390f9b29f4a6689a78b7bde5f8fe0.jpg)
![](http://habrastorage.org/files/bd9/ba1/da5/bd9ba1da52a6496c885e8840d66706e5.jpg)
![](http://habrastorage.org/files/58e/759/95a/58e75995a31f4838a8e3d7aac37ca2c3.jpg)
![](http://habrastorage.org/files/c68/235/7a7/c682357a75c948509fa48dcbae90e818.jpg)
![](http://habrastorage.org/files/a95/adf/9a1/a95adf9a1aa949ee90d1753f8e110fe8.jpg)
![](http://habrastorage.org/files/22d/200/d8a/22d200d8aba0481fbd09d1c61188dbad.jpg)
![](http://habrastorage.org/files/3c9/bfc/9e6/3c9bfc9e6a0b46cfa4a638dffa467ae7.jpg)
![](http://habrastorage.org/files/cb8/440/de8/cb8440de89274e378173cf1d2c8a51fe.jpg)
![](http://habrastorage.org/files/01b/281/096/01b281096193477aacff2ee667e91c0f.jpg)
Таким образом, прогнозируемая польза от индексации страницы u с задержкой
![](http://habrastorage.org/files/6f9/f03/900/6f9f039002a6434eb697cfe34d20692e.jpg)
![](http://habrastorage.org/files/282/cf5/ea4/282cf5ea4a504952b8aefa10cafeb191.jpg)
Список литературы
1. Abiteboul, S., Preda, M., Cobena, C.: Adaptive on-line page importance compu-
tation. In: Proc. WWW Conference (2003)
2. Abramson, M., Aha, D.: What’s in a URL? Genre classification from URLs. In:
Conference on Artificial Intelligence, pp. 262-263 (2012)
3. Bai, X., Cambazoglu, B.B., Junqueira, F.P.: Discovering urls through user feed-
back. In: Proc. CIKM Conference, pp. 77-86 (2011)
4. Baykan, E., Henzinger, M., Marian, L., Weber, I.: A comprehensive study of fea-
tures and algorithms for url-based topic classification. ACM Trans. Web (2011)
5. Baykan, E., Henzinger, M., Weber, I.: Eficient discovery of authoritative resources.
ACM Trans. Web (2013)
6. Cho, J., Schonfeld, U.: Rankmass crawler: a crawler with high personalized pager-
ank coverage guarantee. In: Proc. VLDB (2007)
7. Edwards, J., McCurley, K.S., Tomlin, J .A.: Adaptive model for optimizing perfor-
mance of an incremental web crawler. In: Proc. WWW Conference (2001)
8. Fetterly, D., Craswell, N., Vinay, V.: The impact of crawl policy on web search
effectiveness. In: Proc. SICIR Conference, pp. 580-587 (2009)
9. Hastie, T., Tibshirani, R., Friedman, J .H.: The elements of statistical learning:
data mining, inference, and prediction: with 200 full-color illustrations. Springer,
New York (2001)
10. Kan, M.Y.: Web page classification without the web page. In: Proc. WWW Con-
ference, pp. 262-263 (2004)
11. Kumar, R., Lang, K., Marlow, C., Tomkins, A.: Eficient discovery of authoritative
resources. Data Engineering (2008)
12. Lefortier, D., Ostroumova, L., Samosvat, E., Serdyukov, P.: Timely crawling of high-
quality ephemeral new content. In: Proc. CIKM Conference, pp. 745-750 (2011)
13. Lei, T., Cai, R., Yang, J.M., Ke, Y., Fan, X., Zhang, L.: A pattern tree-
based approach to learning url normalization rules. In: Proc. WWW Conference,
pp. 611-620 (2010)
14. Liu, M., Cai, R., Zhang, M., Zhang, L.: User browsing behavior-driven web crawl-
ing. In: Proc. CIKM Conference, pp. 87-92 (2011)
15. Olston, C., Najork, M.: Web crawling. Foundations and Trends in Information
Retrieval 4(3), 175-246 (2010)
16. Pandey, S., Olston, C.: User-centric web crawling. In: Proc. WWW Conference
2005
17. Pandiy, S., Olston, C.: Crawl ordering by search impact. In: Proc. WSDM Con-
ference (2008)
18. Radinsky, K., Svore, K., Dumais, S., Teevan, J., Bocharov, A., Horvitz, E.: Model-
ing and predicting behavioral dynamics on the web. In: Proc. WWW Conference,
pp. 599-608 (2012)
19. Tsur, O., Rappoport, A.: What’s in a hashtag?: content based prediction of
the spread of ideas in microblogging communities. In: Proc. WSDM Conference,
pp. 643-652 (2012)
20. Wolf, J.L., Squillante, M.S., Yu, P.S., Sethuraman, J., Ozsen, L.: Optimal crawling
strategies for web search engines. In: Proc. WWW Conference (2002)
Этот и другие переводы вы можете найти в блоге компании ALTWEb Group на Хабре. Аналитический отдел компании проводит исследования и обзоры текущих проблем поиска и использует полученные знания при разработке собственных продуктов, таких например, как не имеющий на данный момент отечественных (почти) или зарубежных (совсем) аналогов продукт для повышения ранжирования сайта на базе поведенческих факторов: SERPClick. Благодарим за предоставленный перевод. Подпишитесь на наш блог, если хотите всегда быть в курсе!
Источник: habrahabr.ru/company/altweb/blog/239453/
Обсуждение