Non-fiction: Method for node ranking in a linked database (US Patent 6,285,999)

Overview

The patent "Method for node ranking in a linked database" describes a technique for assigning an importance score to items connected by links, most prominently web pages. The method captures the observation that a link from one page to another can be treated as a recommendation, and that recommendations from important pages should count more. The result, commonly known as PageRank, produces a global, query-independent measure of authority that can be combined with traditional information retrieval signals to order search results.

Core Idea

The database is modeled as a directed graph in which each node is a document and each edge is a link from one document to another. Each node is assigned a real-valued rank that depends on the ranks of nodes linking to it. To prevent rank from accumulating unfairly in cycles or dead ends, the method incorporates a damping component: a portion of rank flows through inbound links in proportion to the linking page’s rank and its number of outgoing links, while a baseline fraction distributes uniformly across all nodes. This yields a probability distribution interpretable as the likelihood that a random navigation process visits each node.

Handling Dangling Nodes and Normalization

Some nodes have no outgoing links. Without special treatment, rank would vanish into these sinks. The method detects such dangling nodes and redistributes their contribution evenly across the graph at each iteration. The system repeatedly recomputes ranks from an initial assignment (often uniform) until convergence, producing a normalized vector that sums to one. The convergence process can be implemented as iterative propagation or as multiplication by a sparse transition matrix with damping, with stopping criteria based on change thresholds.

Weighting and Variations

While the basic flow divides a linking page’s rank equally among its outlinks, the patent contemplates weighting edges or nodes. Weights can reflect factors such as link counts, link attributes, or document-specific qualities. Rank may be scaled or transformed (for example, logarithmically) before being combined with other signals. The method applies beyond web pages to any linked corpus, including citations, directories, or other relational datasets.

System Architecture and Efficiency

The patent outlines a system that crawls documents, extracts links to build the graph, computes ranks offline using iterative methods suited to very large sparse matrices, and stores the resulting scores. Efficient computation is achieved by exploiting sparsity, batching updates, and handling dangling-node redistribution without explicitly connecting all pairs. Ranks can be recalculated periodically or incrementally as the graph changes.

Use in Searching

To answer a user query, the system retrieves documents matching the query terms using standard indexing. It then orders the results by combining query-dependent relevance (such as text matching) with the precomputed rank. The combination can be additive or multiplicative, with tunable coefficients. This blend elevates documents that are both textually relevant and authoritative in the link structure, improving precision on competitive queries and stabilizing rankings against simple keyword stuffing.

Benefits and Properties

The approach provides a global, query-independent measure of importance that resists local manipulation, since boosting rank requires endorsements from already important nodes. The damping factor guarantees a unique stationary distribution and ensures convergence. By propagating influence through the link graph, the method captures implicit human judgments embedded in linking behavior, enabling higher-quality search rankings and more useful navigation across large linked datasets.

Claims Scope

The claims cover computing a rank vector over a linked database via iterative propagation with damping, handling dangling nodes, storing the scores, and using them to rank documents in response to queries. They also cover variations in weighting, scaling, and combining the rank with other relevance measures within an information retrieval system.