Method and apparatus for identifying a data sequence related to a given data sequence

A computer-implemented method of facilitating retrieval of a target data sequence related to a key data sequence, comprising:

• (a) receiving a key data sequence comprising a sequence of data;
• (b) for a first datum in said key data sequence, locating a corresponding cell in a root block;
• (c) retrieving from said cell an identifier of a virtual block comprising one or more nodes;
• (d) locating a node in said virtual block corresponding to a next datum in said key data sequence;
• (e) retrieving from said node an identifier of a next block, wherein said next block is one of another virtual block and a leaf;
• (f) repeating (d)-(f) until said next block is a leaf;
• and
• (g) if said node from which said identifier of said leaf was retrieved corresponds to the last datum in said key data sequence, retrieving said target data sequence from said leaf.

A computer readable storage medium storing instructions that, when executed by a computer, cause the computer to perform a method of facilitating retrieval of a target data sequence related to a key data sequence, the method comprising:

• (a) receiving a key data sequence comprising a sequence of data;
• (b) for a first datum in said key data sequence, locating a corresponding cell in a root block;
• (c) retrieving from said cell an identifier of a virtual block comprising one or more nodes;
• (d) locating a node in said virtual block corresponding to a next datum in said key data sequence;
• (e) retrieving from said node an identifier of a next block, wherein said next block is one of another virtual block and a leaf;
• (f) repeating (d)-(f) until said next block is a leaf;
• and
• (g) if said node from which said identifier of said leaf was retrieved corresponds to the last datum in said key data sequence, retrieving said target data sequence from said leaf.

A computer readable storage medium containing a data structure configured to facilitate the retrieval of a target data sequence related to a key data sequence, the data structure comprising:

• a root comprising one cell for each possible value of a first datum in the key data sequence, including a first cell corresponding to said first datum;
• one or more virtual blocks, wherein each said virtual block comprises one or more nodes and each said node is configured to identify one of:
• another of said one or more virtual blocks;
• and
• a leaf;
• and
• one or more leaves containing data sequences, including a first leaf containing the target data sequence;
• wherein nodes of one of said virtual blocks are interleaved, in the data structure, with nodes of another of said virtual blocks.

An apparatus for determining whether a first target data sequence corresponding to a first key data sequence is available, comprising:

• a root block comprising one entry for each possible value of a first datum of said first key data sequence;
• a set of virtual blocks, wherein each of said virtual blocks comprises one or more nodes, and each node comprises:
• a first reference configured to identify said virtual block comprising said node;
• and
• a second reference configured to identify either another virtual block or a leaf;
• and
• a set of leaves, wherein each of said leaves is configured to store a target data sequence corresponding to a first key data sequence;
• and
• a processor configured to traverse, from a first entry in said root block corresponding to said first datum, nodes within a subset of said virtual blocks corresponding to subsequent data in said first key data sequence, via said second references, to determine whether one of said leaves contains said first target data sequence.