25 Women to Read Before You Die
 
 

Special Offers see all

Enter to WIN a $100 Credit

Subscribe to PowellsBooks.news
for a chance to win.
Privacy Policy

Visit our stores


    Recently Viewed clear list


    Lists | September 2, 2015

    Joy Williams: IMG Eight Essential Attributes of the Short Story and One Way It Differs from the Novel



    1) There should be a clean clear surface with much disturbance below. 2) An anagogical level. 3) Sentences that can stand strikingly alone. 4) An... Continue »
    1. $21.00 Sale Hardcover add to wish list

    spacer
Qualifying orders ship free.
$61.75
New Hardcover
Ships in 1 to 3 days
Add to Wishlist
available for shipping or prepaid pickup only
Available for In-store Pickup
in 7 to 12 days
Qty Store Section
1 Remote Warehouse Software Engineering- Algorithms

Numerical Algorithms for Personalized Search in Self-Organizing Information Networks

by

Numerical Algorithms for Personalized Search in Self-Organizing Information Networks Cover

 

Synopses & Reviews

Publisher Comments:

This book lays out the theoretical groundwork for personalized search and reputation management, both on the Web and in peer-to-peer and social networks. Representing much of the foundational research in this field, the book develops scalable algorithms that exploit the graphlike properties underlying personalized search and reputation management, and delves into realistic scenarios regarding Web-scale data.

Sep Kamvar focuses on eigenvector-based techniques in Web search, introducing a personalized variant of Google's PageRank algorithm, and he outlines algorithms--such as the now-famous quadratic extrapolation technique--that speed up computation, making personalized PageRank feasible. Kamvar suggests that Power Method-related techniques ultimately should be the basis for improving the PageRank algorithm, and he presents algorithms that exploit the convergence behavior of individual components of the PageRank vector. Kamvar then extends the ideas of reputation management and personalized search to distributed networks like peer-to-peer and social networks. He highlights locality and computational considerations related to the structure of the network, and considers such unique issues as malicious peers. He describes the EigenTrust algorithm and applies various PageRank concepts to P2P settings. Discussion chapters summarizing results conclude the book's two main sections.

Clear and thorough, this book provides an authoritative look at central innovations in search for all of those interested in the subject.

Synopsis:

"The writing style is extremely clear, and the book is accessible to readers both within and outside of the field."--Chen Greif, University of British Columbia

"The clarity of presentation makes this book accessible to a broad audience. The scholarship is thorough and sound, and the experimental results are presented in a precise and detailed fashion."--Taher Haveliwala, QForge Labs

"Kamvar helped establish a foundation for P2P search and this book provides an authoritative record and source for his excellent work in this area."--Andrew Tomkins, Google

Synopsis:

This book lays out the theoretical groundwork for personalized search and reputation management, both on the Web and in peer-to-peer and social networks. Representing much of the foundational research in this field, the book develops scalable algorithms that exploit the graphlike properties underlying personalized search and reputation management, and delves into realistic scenarios regarding Web-scale data.

Sep Kamvar focuses on eigenvector-based techniques in Web search, introducing a personalized variant of Google's PageRank algorithm, and he outlines algorithms--such as the now-famous quadratic extrapolation technique--that speed up computation, making personalized PageRank feasible. Kamvar suggests that Power Method-related techniques ultimately should be the basis for improving the PageRank algorithm, and he presents algorithms that exploit the convergence behavior of individual components of the PageRank vector. Kamvar then extends the ideas of reputation management and personalized search to distributed networks like peer-to-peer and social networks. He highlights locality and computational considerations related to the structure of the network, and considers such unique issues as malicious peers. He describes the EigenTrust algorithm and applies various PageRank concepts to P2P settings. Discussion chapters summarizing results conclude the book's two main sections.

Clear and thorough, this book provides an authoritative look at central innovations in search for all of those interested in the subject.

About the Author

Sep Kamvar is a consulting assistant professor of computational mathematics at Stanford University. From 2003 to 2007, he was the engineering lead for personalization at Google. He is the founder and former CEO of Kaltix, a personalized search engine acquired by Google in 2003.

Table of Contents

Tables ix

Figures xi

Acknowledgments xv

Chapter 1: Introduction 1

1.1 World Wide Web 1

1.2 P2P Networks 2

1.3 Contributions 2

PART I: WORLD WIDE WEB 5

Chapter 2: PageRank 7

2.1 PageRank Basics 7

2.2 Notation and Mathematical Preliminaries 9

2.3 Power Method 10

2.3.1 Formulation 10

2.3.2 Operation Count 12

2.3.3 Convergence 12

2.4 Experimental Setup 13

2.5 Related Work 13

2.5.1 Fast Eigenvector Computation 13

2.5.2 PageRank 14

Chapter 3: The Second Eigenvalue of the Google Matrix 15

3.1 Introduction 15

3.2 Theorems 15

3.3 Proof of Theorem 1 15

3.4 Proof of Theorem 2 17

3.5 Implications 18

3.6 Theorems Used 19

Chapter 4: The Condition Number of the PageRank Problem 20

4.1 Theorem 6 20

4.2 Proof of Theorem 6 20

4.3 Implications 21

Chapter 5: Extrapolation Algorithms 23

5.1 Introduction 23

5.2 Aitken Extrapolation 23

5.2.1 Formulation 23

5.2.2 Operation Count 25

5.2.3 Experimental Results 26

5.2.4 Discussion 26

5.3 Quadratic Extrapolation 27

5.3.1 Formulation 27

5.3.2 Operation Count 30

5.3.3 Experimental Results 30

5.3.4 Discussion 34

5.4 Power Extrapolation 35

5.4.1 Simple Power Extrapolation 35

5.4.2 A2 Extrapolation 35

5.4.3 Ad Extrapolation 37

5.5 Measures of Convergence 40

Chapter 6: Adaptive PageRank 42

6.1 Introduction 42

6.2 Distribution of Convergence Rates 42

6.3 Adaptive PageRank Algorithm 44

6.3.1 Algorithm Intuition 45

6.3.2 Filter-based Adaptive PageRank 46

6.4 Experimental Results 48

6.5 Extensions 48

6.5.1 Further Reducing Redundant Computation 48

6.5.2 Using the Matrix Ordering from the Previous Computation 50

6.6 Discussion 50

Chapter 7: BlockRank 51

7.1 Block Structure of the Web 51

7.1.1 Block Sizes 54

7.1.2 The GeoCities Effect 55

7.2 BlockRank Algorithm 55

7.2.1 Overview of BlockRank Algorithm 56

7.2.2 Computing Local PageRanks 57

7.2.3 Estimating the Relative Importance of Each Block 60

7.2.4 Approximating Global PageRank Using Local PageRank and BlockRank 61

7.2.5 Using This Estimate as a Start Vector 62

7.3 Advantages of BlockRank 63

7.4 Experimental Results 64

7.5 Discussion 67

7.6 Personalized PageRank 67

7.6.1 Inducing Random Jump Probabilities over Pages 68

7.6.2 Using "Better" Local PageRanks 68

7.6.3 Experiments 69

7.6.4 Topic-Sensitive PageRank 70

7.6.5 Pure BlockRank 71

PART II: P2P NETWORKS 73

Chapter 8: Query-Cycle Simulator 75

8.1 Challenges in Empirical Evaluation of P2P Algorithms 75

8.2 The Query-Cycle Model 75

8.3 Basic Properties 76

8.3.1 Network Topology 76

8.3.2 Joining the Network 76

8.3.3 Query Propagation 76

8.4 Peer-Level Properties 77

8.5 Content Distribution Model 78

8.5.1 Data Volume 78

8.5.2 Content Type 78

8.6 Peer Behavior Model 80

8.6.1 Uptime and Session Duration 80

8.6.2 Query Activity 81

8.6.3 Queries 81

8.6.4 Query Responses 81

8.6.5 Downloads 82

8.7 Network Parameters 82

8.7.1 Topology 82

8.7.2 Bandwidth 82

8.8 Discussion 83

Chapter 9: EigenTrust 84

9.1 Design Considerations 84

9.2 Reputation Systems 85

9.3 EigenTrust 86

9.3.1 Normalizing Local Trust Values 86

9.3.2 Aggregating Local Trust Values 87

9.3.3 Probabilistic Interpretation 87

9.3.4 Basic EigenTrust 87

9.3.5 Practical Issues 88

9.3.6 Distributed EigenTrust 89

9.3.7 Algorithm Complexity 90

9.4 Secure EigenTrust 91

9.4.1 Algorithm Description 92

9.4.2 Discussion 93

9.5 Using Global Trust Values 94

9.6 Experiments 95

9.6.1 Load Distribution in a Trust-based Network 95

9.6.2 Threat Models 98

9.7 Related Work 106

9.8 Discussion 106

Chapter 10: Adaptive P2P Topologies 108

10.1 Introduction 108

10.2 Interaction Topologies 109

10.3 Adaptive P2P Topologies 109

10.3.1 Local Trust Scores 109

10.3.2 Protocol 110

10.3.3 Practical Issues 112

10.4 Empirical Results 115

10.4.1 Malicious Peers Move to Fringe 115

10.4.2 Freeriders Move to Fringe 118

10.4.3 Active Peers Are Rewarded 119

10.4.4 Efficient Topology 120

10.5 Threat Scenarios 126

10.5.1 Threat Model A 126

10.5.2 Threat Model B 128

10.5.3 Threat Model C 130

10.6 Related Work 131

10.7 Discussion 132

Chapter 11: Conclusion 133

Bibliography 135

Product Details

ISBN:
9780691145037
Author:
Kamvar, Sep
Publisher:
Princeton University Press
Subject:
Computer Science
Subject:
Programming - Algorithms
Subject:
General
Subject:
Algorithms
Subject:
Internet searching - Mathematics
Subject:
Mathematics
Subject:
Applied Science and Engineering
Subject:
Personal Computers-General
Copyright:
Publication Date:
20100927
Binding:
Electronic book text in proprietary or open standard format
Language:
English
Illustrations:
55 line illus. 11 tables.
Pages:
160
Dimensions:
9 x 6 in 13 oz

Related Subjects

Computers and Internet » Computers Reference » General
Computers and Internet » Personal Computers » General
Computers and Internet » Software Engineering » Algorithms
History and Social Science » Economics » General
Science and Mathematics » Mathematics » Computer
Science and Mathematics » Mathematics » General

Numerical Algorithms for Personalized Search in Self-Organizing Information Networks New Hardcover
0 stars - 0 reviews
$61.75 In Stock
Product details 160 pages Princeton University Press - English 9780691145037 Reviews:
"Synopsis" by , "The writing style is extremely clear, and the book is accessible to readers both within and outside of the field."--Chen Greif, University of British Columbia

"The clarity of presentation makes this book accessible to a broad audience. The scholarship is thorough and sound, and the experimental results are presented in a precise and detailed fashion."--Taher Haveliwala, QForge Labs

"Kamvar helped establish a foundation for P2P search and this book provides an authoritative record and source for his excellent work in this area."--Andrew Tomkins, Google

"Synopsis" by , This book lays out the theoretical groundwork for personalized search and reputation management, both on the Web and in peer-to-peer and social networks. Representing much of the foundational research in this field, the book develops scalable algorithms that exploit the graphlike properties underlying personalized search and reputation management, and delves into realistic scenarios regarding Web-scale data.

Sep Kamvar focuses on eigenvector-based techniques in Web search, introducing a personalized variant of Google's PageRank algorithm, and he outlines algorithms--such as the now-famous quadratic extrapolation technique--that speed up computation, making personalized PageRank feasible. Kamvar suggests that Power Method-related techniques ultimately should be the basis for improving the PageRank algorithm, and he presents algorithms that exploit the convergence behavior of individual components of the PageRank vector. Kamvar then extends the ideas of reputation management and personalized search to distributed networks like peer-to-peer and social networks. He highlights locality and computational considerations related to the structure of the network, and considers such unique issues as malicious peers. He describes the EigenTrust algorithm and applies various PageRank concepts to P2P settings. Discussion chapters summarizing results conclude the book's two main sections.

Clear and thorough, this book provides an authoritative look at central innovations in search for all of those interested in the subject.

spacer
spacer
  • back to top

FOLLOW US ON...

       
Powell's City of Books is an independent bookstore in Portland, Oregon, that fills a whole city block with more than a million new, used, and out of print books. Shop those shelves — plus literally millions more books, DVDs, and gifts — here at Powells.com.