Применение алгоритма PageRank для задачи ранжирования в BFT системах
Аннотация
Одной из тенденций в области распределенных систем является повышение интереса к таким распределенным системам, в которых узлы функционируют не только в ненадежной среде, но и в условиях отсутствия доверия между участниками самой системы. К таким, в частности, относятся системы, работающие на основе алгоритмов Byzantine Fault Tolerance (BFT). Эта тенденция имеет место и для поисковых систем. Стандартной задачей, решаемой поисковыми системами, является задача ранжирования результатов запросов. Для неё существуют несколько распространенных решений, которые применяются как в традиционных, так и в распределенных поисковых системах. Однако ориентация на BFT вводит ряд ограничений, которые затрудняют их применение. Алгоритм PageRank является одним из наиболее широко распространенных алгоритмов решения задачи ранжирования при организации поиска и рекомендаций в Web, задачах библиометрии, электронной коммерции, биологии и других. Он позволяет проводить оценку значимости объекта, основываясь на оценках его соседей, с которыми он имеет связи. Существуют исследования, посвященные адаптации данного алгоритма для некоторых типов распределенных систем. В рамках настоящего исследования решается проблема ранжирования результатов поиска в распределенной поисковой системе, работающей по BFT-алгоритму консенсуса. Предлагается вариант алгоритма ранжирования PageRank для распределенных BFT-систем, рассматриваются существующие модификации PageRank для распределенных систем, обсуждаются требования, предъявляемые к алгоритмам для работы в BFT-среде, исследуются параметры систем. В конце приводятся результаты эксперимента.
Скачивания
Литература
2. The PageRank Citation Ranking: Bringing Order to the Web / L. Page и др. // Stanford InfoLab – 1999. – С. 1–17. – URL.
3. Gleich, D. F. PageRank Beyond the Web / David F. Gleich // Society for Industrial and Applied Mathematics – 2015. – С. 321–363.
4. Gravano, L. The Efficacy of GlOSS for the Text Database Discovery Problem / L. Gravano, H. Garcia-Molina, A. Tomasic // Stanford InfoLab – 1993. – С. 1–39. – URL.
5. YaCy Decentralized Web Search. – URL.
6. The Community-Powered Search Engine. – 2017. – С. 1–39. – URL.
7. Castro, M. Practical Byzantine Fault Tolerance / M. Castro, B. Liskov // Laboratory for Computer Science, Massachusetts Institute of Technology, 545 Technology Square, Cambridge. – 1999. – С. 1–14.
8. Sankaralingam, K. Distributed Pagerank for P2P Systems / K. Sankaralingam, S. Sethumadhavan, J. C. Browne // High Performance Distributed Computing, 2003. Proceedings. 12th IEEE International Symposium on High Performance Distributed Computing. – 2003. – С. 1–11.
9. Bahmani, B. Fast personalized pagerank on mapreduce / B. Bahmani, K. Chakrabarti, D. Xin // In Proc. of ACM SIGMOD Conference. – 2011. – С. 973-984.
10. Sarma, A. D. Fast Distributed PageRank Computation / A. D. Sarma и др.l // Theoretical Computer Science, volume 561. – 2015. – С. 113-121.
- Авторы сохраняют за собой авторские права и предоставляют журналу право первой публикации работы, которая по истечении 6 месяцев после публикации автоматически лицензируется на условиях Creative Commons Attribution License , которая позволяет другим распространять данную работу с обязательным сохранением ссылок на авторов оригинальной работы и оригинальную публикацию в этом журнале.
- Авторы имеют право размещать их работу в сети Интернет (например в институтском хранилище или персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу (См. The Effect of Open Access).
