Patent ID: 7702640
Filing Date: 2010-04-20
Classification: G06F

Abstract:
1. A system, comprising: a plurality of computing nodes configured to implement a plurality of replicated index data structures each replicated index data structure configured to map ones of a plurality of input values to one or more corresponding data items, each of said computing nodes comprising at least one computer system having at least a processor, and wherein the computing nodes are configured to communicate with one another via a network; wherein each of said plurality of index data structures includes a respective plurality of index nodes arranged hierarchically and each index data structure having an associated tag value, wherein each of said data items corresponds to a respective one of said index nodes, and wherein for each given one of the index nodes for which there exists a corresponding given one of said data items, each tag value associated with each ancestor of said given index node is a prefix of input value that maps to said given data item; wherein each given one of said index data structures is configured as an unbalanced data structure and is further configured such that for each particular index node within said given index data structure, membership of the particular index node within a particular hierarchical subgroup of said given index data structure is dependent upon the tag value associated with the particular index node and is independent of a number of index nodes within the particular hierarchical subgroup; wherein for each given one of said index data structures, each of said plurality of index nodes included within said given index data structure is associated with a respective fingerprint value, wherein for a given one of said index nodes, said respective fingerprint value is indicative of a hash value computed according to a hash algorithm, wherein said hash value is computed as a function of ones of said plurality of index nodes that are hierarchical descendants of said given index node; wherein each given one of said index data structures is stratified among a plurality of index tree data structures, wherein a root node of said given index data structure corresponds to a root node of a first one of said plurality of index tree data structures, wherein each of a plurality of leaf nodes of said first index tree data structure corresponds to a root node of a respective one of said index tree data structures, and wherein at least two of said plurality of index tree data structures are stored on different ones of said plurality of computing nodes; wherein in response to receiving a request to access a given input value, a given one of said plurality of index data structures is configured to select a given one of said index nodes of said given index data structure and to compare a tag value associated with said given index node with said given input value to determine whether said tag value is a prefix of said given input value; and wherein in response to determining that said tag value is a prefix of said given input value, said given index data structure is further configured to determine whether a corresponding tag value of any descendant of said given index node exactly matches or is a prefix of said given input value, wherein in response to determining that a corresponding tag value of a given descendant of said given index node exactly matches or is a proper prefix of said given input value, said given index data structure is further configured to select said given descendant for further traversal.