Stanford InfoLab Publication Server

Scaling Personalized Web Search

Jeh, Glen and Widom, Jennifer (2002) Scaling Personalized Web Search. Technical Report. Stanford.




Recent web search techniques augment traditional text matching with a global notion of ``importance'' based on the linkage structure of the web, such as in Google's "PageRank" algorithm. For more refined searches, this global notion of importance can be specialized to create personalized views of importance--for example, importance scores can be biased according to a user-specified set of initially-interesting pages. Computing and storing all possible personalized views in advance is impractical, as is computing personalized views at query time, since the computation of each view requires an iterative computation over the web graph. We present new graph-theoretical results, and a new technique based on these results, that encode personalized views as "partial vectors". Partial vectors are shared across multiple personalized views, and their computation and storage costs scale well with the number of views. Our approach enables incremental computation, so that the construction of personalized views from partial vectors is practical at query time. We present efficient dynamic programming algorithms for computing partial vectors, an algorithm for constructing personalized views from partial vectors, and experimental results demonstrating the effectiveness and scalability of our techniques.

Item Type:Techreport (Technical Report)
Uncontrolled Keywords:PageRank, web search
Subjects:Computer Science > Databases and the Web
Related URLs:Project Homepage
ID Code:530
Deposited By:Import Account
Deposited On:21 Feb 2002 16:00
Last Modified:25 Dec 2008 09:34

Download statistics

Repository Staff Only: item control page