Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2008-03-04
2008-03-04
Wong, Don (Department: 2163)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
10413645
ABSTRACT:
Nodes of a web graph are distributed over a cluster of computers. Tables distributed over the computers map source (destination) locations to lists of destination (source) locations. To accommodate traversing hyperlinks forward, a table maps the location of a web page “X” to locations of all the web pages “X” links to. To accommodate traversing hyperlinks backward, a table maps the location of a web page “Y” to locations of all web pages that link to Y. URLs identifying web pages are mapped to fixed-sized checksums, reducing the storage required for each node, while providing a way to map a URL to a node. Mapping is chosen to preserve information about the web server component of the URL. Nodes can then be partitioned across the machines in the cluster such that nodes corresponding to URLs on the same web server are assigned to the same machine in the cluster.
REFERENCES:
patent: 6098081 (2000-08-01), Heidorn et al.
patent: 6112203 (2000-08-01), Bharat et al.
patent: 6301614 (2001-10-01), Najork et al.
patent: 6505191 (2003-01-01), Baclawski
patent: 6601066 (2003-07-01), Davis-Hall
patent: 7032168 (2006-04-01), Gerace et al.
patent: 2002/0103824 (2002-08-01), Koppolu et al.
patent: 2002/0133697 (2002-09-01), Royer et al.
Adler, M. et al., “Towards Compressing Web Graphs”,CMPSCI Technical Report, 2000, 5 pages.
Arasu, A. et al., “PageRank Computation and the Structure of the Web: Experiments and Algorithms”,Technical Report, IBM Almaden Research Center, Nov. 2001, 3 pages.
Bharat, K. et al., “Improved Algorithms for Topic Distillation in a Hyperlinked Environment”,21stACM SIGIR Conference on Research and Development in Information Retrieval, 1998, 5 pages.
Bharat, K. et al., “The Connectivity Server: fast access to linkage information on the Web”,Computer Networks and ISDN Systems, 1998, 30, 469-477.
Brin, S. et al., “The Anatomy of a large-scale hypertextual Web search engine”,computer Networks and ISDN Systems, 1998, 30, 107-117.
Chen, Y-Y. et al., “I/O-Efficient Techniques for Computing Pagerank”,CIKM, 2002, 5 pages.
Cormen, T.H. et al., “Introduction to Algorithms”,MIT Press/McGraw-Hill, 1990, 337-344.
Ding, C. et al., “PageRank, HITS and a Unified Framework for Link Analysis”,Lawrence Berkeley National Laboratory, Nov. 2001, 1-12.
Haveliwala, T. H. et al., “Efficient Computation of PageRank”, Oct. 18, 1999, 1-15.
Kleinberg, J.M. “Authoritative Sources in a Hyperlinked Environment”,Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 1998, 1-31.
“The PageRank Citation Ranking: Bringing Order to the Web”, Jan. 29, 1998, 1-17.
Randall, K.H. et al., “The Link Database: Fast Access to Graphs of the Web”,SRC Research Report, www.research.compaq.com/SRC, Nov. 16, 2001, 1-16.
Adler, M. et al., “Towards Compressing Web Graphs”,CMPSCI Technical Report, 2000, 5 pages.
Arasu, A. et al., “PageRank Computation and the Structure of the Web: Experiments and Algorithms”,Technical Report, IBM Almaden Research Center, Nov. 2001, 3 pages.
Bharat, K. et al., “Improved Algorithms for Topic Distillation in an Hyperlinked Environment”,21stACM SIGIR Conference on Research and Development in Information Retrieval, 1998, 5 pages.
Bharat, K. et al., “The Connectivity Server: fast access to linkage information on the Web”,Computer Networks and ISDN Systems, 1998, 30, 469-477.
Brin, S. et al., “The Anatomy of a large-scale hypertextual Web search engine”,computer Networks and ISDN Systems, 1998, 30, 107-117.
Chen, Y-Y. et al., “I/O-Efficient Techniques for Computing Pagerank”,CIKM, 2002, 5 pages.
Cormen, T.H. et al., “Introduction to Algorithms”,MIT Press/McGraw-Hill, 1990, 337-344.
Ding, C. et al., “PageRank, HITS and a Unified Framework for Link Analysis”,Lawrence Berkeley National Laboratory, Nov. 2001, 1-12.
Haveliwala, T.H. et al., “Efficient Computation of PageRank”, Oct. 18, 1999, 1-15.
Kleinberg, J.M. “Authoritative Sources in a Hyperlinked Environment”,Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, 1998, 1-31.
Lempel, R. et al., “The Stochastic Approach for Link-Structure Analysis (SALSA) and the TKC Effect”,Department of Computer Science, The Technion, 1-39, Jun. 18, 1998.
“The PageRank Citation Ranking: Bringing Order to the Web”, Jan. 29, 1998, 1-17.
Randall, K.H. et al., “The Link Database: Fast Access to Graphs of the Web”,SRC Research Report, www.research.compaq.com/SRC, Nov. 16, 2001, 1-16.
Suel, T. et al., “Compressing the Graph Structure of the Web”, pp. 1-10, 2001.
Brown Sheree N
Wong Don
Woodcock & Washburn LLP
LandOfFree
System and method for maintaining a distributed database of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for maintaining a distributed database of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for maintaining a distributed database of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3947275