Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2006-12-29
2009-11-10
Rones, Charles (Department: 2164)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
07617194
ABSTRACT:
A method and system for ranking importance of vertices of a directed graph based on links between the vertices and some prior knowledge of importance of the vertices is provided. A ranking system inputs an indication of the vertices along with an indication of the links between the vertices as the directed graph. The ranking system generates a transition-probability matrix that represents the probability of transitioning from vertex to vertex. The ranking system then generates a ranking of the vertices based on the links between the vertices represented by the stationary distribution of the transition-probability matrix that is minimally perturbed to satisfy the prior knowledge, which may be a partial ranking of the vertices.
REFERENCES:
patent: 6285999 (2001-09-01), Page
patent: 6654742 (2003-11-01), Kobayashi et al.
patent: 6839682 (2005-01-01), Blume et al.
patent: 7024404 (2006-04-01), Gerasoulis et al.
patent: 7026029 (2006-04-01), Kamvar et al.
patent: 7089252 (2006-08-01), Tomlin et al.
patent: 7343374 (2008-03-01), Berkhin
patent: 7464075 (2008-12-01), McSherry et al.
patent: 2004/0024752 (2004-02-01), Manber et al.
patent: 2004/0111412 (2004-06-01), Broder
patent: 2005/0071465 (2005-03-01), Zeng et al.
patent: 2005/0216533 (2005-09-01), Berkhin
patent: 2005/0256860 (2005-11-01), Eiron et al.
patent: 2006/0020607 (2006-01-01), Patterson
patent: 2006/0059119 (2006-03-01), Canright et al.
patent: 2006/0074910 (2006-04-01), Yun et al.
patent: 2006/0248059 (2006-11-01), Chi et al.
patent: 2008/0010281 (2008-01-01), Berkhin et al.
patent: 2008/0114750 (2008-05-01), Saxena et al.
Adamic, Leda A. and Bernardo A. Huberman, “Power-Law Distribution of the World Wide Web,” Technical Comment, Science, vol. 287, Mar. 24, 2000, p. 2115a.
Arasu, Arvind et al., “PageRank Computation and the Structure of the Web: Experiments and Algorithms,” 5 pages.
Boyd, Stephen et al., “Chapter 11—Interior-point methods,” Convex Optimization, © Cambridge University Press 2004, pp. 561-622.
Brinkmeier, Michael, “PageRank Revisited,” ACM Transactions on Internet Technology, vol. 6, No. 3, Aug. 2006, © 2006 ACM, pp. 282-301.
Gyongyi, Zoltan, Hector Garcia-Molina and Jan Pedersen, “Combating Web Spam with TrustRank,” Proceedings of the 30th VLDB Conference, Toronto, Canada, 2004, pp. 576-587.
Kamvar, Sepandar D. et al., “Exploiting the Block Structure of the Web for Computing PageRank,” 2003, 13 pages.
Meila, Marina and Jianbo Shi, “Learning Segmentation by Random Walks,” NIPS, 2001, 7 pages.
Ng, Andrew Y., Alice X. Zheng and Michael I. Jordan, “Link Analysis, Eigenvectors and Stability,” IJCAI, 2001, 8 pages.
Page, L. et al., “The PageRank Citation Ranking: Bringing Order to the Web,” Jan. 29, 1998, Stanford University Technical Report, pp. 1-17.
Qin, Tao, Tie-Yan Liu and Wei-Ying Ma, “Supervised Ranking for Directed Graphs,” 21 pages.
Sobek, Markus, “Additional Factors Influencing PageRank,” eFactory, © 2002/2003 eFactory GmbH & Co. KG Internet-Agentur, 7 pages, http://pr.efactory.de/e-further-factors.shtml [last accessed Nov. 16, 2006].
Zhou, Dengyong et al., “Ranking on Data Manifolds,” 2004, 8 pages.
Peer Review for “Supervised Ranking for Directed Graphs,” authors Qin Liu et al.
Liu Tie-Yan
Ma Wei-Ying
Qin Tao
Microsoft Corporation
Mueller Kurt
Perkins Coie LLP
Rones Charles
LandOfFree
Supervised ranking of vertices of a directed graph does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Supervised ranking of vertices of a directed graph, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Supervised ranking of vertices of a directed graph will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4055762