PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Tytuł artykułu

Accelerating PageRank computations

Treść / Zawartość
Identyfikatory
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
Different methods for computing PageRank vectors are analysed. Particularly, we note the opposite behavior of the power method and the Monte Carlo method. Further, a method of reducing the number of iterations of the power method is suggested.
Słowa kluczowe
Rocznik
Strony
259--274
Opis fizyczny
Bibliogr. 26 poz., il.
Twórcy
autor
  • Institute of Computer Science, Polish Academy of Sciences Ordona 21, 01-237 Warszawa, Poland
Bibliografia
  • Avrachenkov, K., Litvak, N., Nemirovsky, D. and Osipova, N. (2007) Monte Carlo methods in PageRank computation: When one iteration is sufficient. SIAM Journal of Numerical Analysis, 45(2), 890-904.
  • Barrett, R., Berry, M., Chan, T.F., Demmel, J., Donato, J.,Dongarra, J., Eijkhout, V., Pozo, R., Romine, C. and van der Vorst, H. (1994) Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods. SIAM, Philadelphia, PA.
  • Boldi, P. (2005) TotalRank: Ranking without damping. In: Poster Proc. of the 14-th International Conference on the World Wide Web WWW05. ACM, New York, 898-899.
  • Boldi,P., Posenato,R., Santini,M. and Vigna, S. (2008) Traps and pitfalls of topic-biased PageRank. In: W. Aiello, A. Broder, J. Janssen, and E. Milios, eds., Proc. WAW 2006. 4-th Workshop on Algorithms and Models for the Web-Graph, LNCS 4936, Springer, 107-116.
  • Brin, S. and Page, L. (1998) The anatomy of a large-scale hypertextualWeb search engine. In: Proc. 7-th International World-Wide Web Conference, WWW 1998. ACM, New York.
  • Chung, F. (2007) The heat kernel as the PageRank of a graph. PNAS, 105(50), 19735-19740.
  • Constantine,P.G. and Gleich,D.F. (2009) Random Alpha PageRank. Internet Mathematics, 6(2), 189-236.
  • Dean, J. and Ghemawat, S. (2008) MapReduce: simplified data processing on large clusters. Communications of the ACM, 51 (1), 107-113.
  • DelCorso, G.M., Gulli, A. and Romani, F. (2005) Fast PageRank computation via a sparse linear system. Internet Mathematics, 2(3), 251-273.
  • Fagin, R., Kumar, R. and Sivakumar, D. (2004) Comparing top k lists. SIAM Journal on Discrete Mathematics, 17(1), 134 - 160.
  • Fogaras, D. and Rácz, B. (2004) Towards scaling fully personalized PageRank. In: S. Leonardi, ed., Proc. of the 3rd Workshop on Algorithms and Models for the Web-Graph (WAW 2004), LNCS 3243, Springer, 105-117.
  • Gleich, D. and Zhukov, L. (2005) Scalable Computing for Power Law Graphs: Experience with Parallel PageRank. In: SuperComputing, S.C./05.ACM, New York.
  • Golub, G.H. and van Loan, Ch.F. (1996) Matrix Computation. Third edition. Hindustan Book Agency, New Delhi, India.
  • Haveliwala,T. (1999) Efficient Computation of PageRank. Technical Report 1999-31, Stanford InfoLab, http://ilpubs.stanford.edu:8090/386/.
  • Haveliwala, T.H. and Kamvar, S.D. (2003) The Second Eigenvalue of the Google Matrix. Technical report, Stanford University.
  • Kamvar, S.D., Haveliwala,T.H. and Golub,G.H. (2004) Adaptive methods for the computation of PageRank. Linear Algebra and its Applications, 386, 51-65.
  • Kamvar, S.D., Haveliwala,T.H., Manning,C.D. and Golub,G.H. (2003) Exploiting the block structure of the Web for computing PageRank. Technical report, Stanford University.
  • Lam, Ch and Warren, J. (2009) Hadoop in Action, Manning.
  • Langville, A.N. and Meyer, C.D. (2006a) Google’s PageRank and Beyond: The Science of Search Engine Rankings. Princeton University Press.
  • Langville, A.N. and Meyer, C.D. (2006b) Information Retrieval and Web Search. In: L. Hogben, R. Brualdi, A. Greenbaum, and R. Mathias, eds., Handbook of Linear Algebra, chapter 63, 63-1, CRC Press.
  • Meyer, C.D. (2000) Matrix Analysis and Applied Linear Algebra. SIAM, Philadelphia.
  • Page, L., Brin, S., Motwani, R. and Winograd, T. (1998) The PageRank Citation Ranking: Bringing Order to the Web. Technical report, Stanford Digital Library Technologies Project.
  • Singitham, P.K.C., Mahabhashyam, M.S. and Raghavan, P. (2004) Efficiency- quality tradeoffs for vector score aggregation. In: M.A. Nascimento, M.T. Özsu, D. Kossmann, R.J. Miller, J.A. Blakeley, and K.B. Schiefer, eds., Proc. of the 30-th International Conf. on Very Large Data Bases, 30, 624-635, Morgan Kaufmann, Toronto, Canada.
  • Stewart, W.J. (1994) Introduction to the Numerical Solution of Markov Chains. Princeton University Press, Princeton.
  • Thorson, K. (2004) Modeling the Web and the computation of PageRank. Undergraduate thesis, Hollins University.
  • Vigna, S. (2010) Spectral ranking. ArXiv e-prints (0912.0238).
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-BATC-0008-0003
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.