US7019674B2 — Content-based information retrieval architecture

Claim 1

Independent Claim 177 words

A content-based information retrieval architecture comprising: a hashing module that receives an input value and generates a plurality of hashed values from the input value; a first table storing a plurality of encoded values, each hashed value generated from the input value corresponding to a location in the table of an encoded value; a second table storing a plurality of lookup values; and a third table storing a plurality of associated input values in a lookup set, each such input value associated with a lookup value in the second table, where the first table is constructed so that the encoded values, obtained from the hashed values generated from an input value, encode an output value such that the output value cannot be recovered from any single encoded value and such that the output value selects a lookup value in the second table and an associated input value in the third table, thereby identifying the input value as being in the lookup set if the input value is same as the associated input value in the third table.

Claim 2

Dependent Claim 177 words

A content-based information retrieval architecture comprising: a hashing module that receives an input value and generates a plurality of hashed values from the input value; a first table storing a plurality of encoded values, each hashed value generated from the input value corresponding to a location in the table of an encoded value; a second table storing a plurality of lookup values; and a third table storing a plurality of associated input values in a lookup set, each such input value associated with a lookup value in the second table, where the first table is constructed so that the encoded values, obtained from the hashed values generated from an input value, encode an output value such that the output value cannot be recovered from any single encoded value and such that the output value selects a lookup value in the second table and an associated input value in the third table, thereby identifying the input value as being in the lookup set if the input value is same as the associated input value in the third table.

Claim 3

Dependent Claim 37 words

The information retrieval architecture of claim 1 wherein the encoded values in the first table encode the output value such that the output value is recovered by combining the encoded values by performing a bit-wise XOR operation.

Claim 4

Dependent Claim 49 words

The information retrieval architecture of claim 1 wherein the lookup values are stored at unique addresses in the second table and wherein the first table of encoded values is constructed so that the output value encoded by the plurality of encoded values is an address in the second table.

Claim 5

Dependent Claim 49 words

The information retrieval architecture of claim 1 wherein the first table is constructed so that the second table has a size that is smaller than the first table and so that the width of the first table is at least log(n) where n is the number of lookup values.

Claim 6

Dependent Claim 34 words

The information retrieval architecture of claim 1 wherein the first table is segmented into a plurality of banks, each bank associated with one of the plurality of hash values generated by the hashing module.

Claim 7

Dependent Claim 26 words

The information retrieval architecture of claim 1 wherein the hashing module and the first table are pipelined into different stages from the second and third tables.

Claim 8

Dependent Claim 41 words

The information retrieval architecture of claim 1 further comprising a filtering module which receives input values and forwards the input value to the hashing module only if the input value is not a member of a filtered set of input values.

Claim 9

Dependent Claim 32 words

The information retrieval architecture of claim 7 wherein the filtered set of input values are those input values that are not recognized as being members of the lookup set of input values.

Claim 10

Dependent Claim 31 words

The information retrieval architecture of claim 7 wherein the filtered set of input values are those input values selected so as to facilitate construction of the first table of encoded values.

Claim 11

Dependent Claim 59 words

The information retrieval architecture of claim 9 wherein the filtered set of input values comprises at least one input value such that, when the hashing module generates a plurality of hashed values from the one input value, the hashed vlaues generated from the one input value correspond to not one singleton location in the first table of encoded values.

Claim 12

Dependent Claim 31 words

The information retrieval architecture of claim 7 wherein at least one input value is remapped by the filtering module into another input value that is then forwarded to the hashing module.

Claim 13

Dependent Claim 54 words

The information retrieval architecture of claim 7 wherein at least one input value, that is recognized as not being in the lookup set because the associated input value in the third table is not same as the one input value, is added to the filtered set of input values used by the filtering module.

Claim 14

Dependent Claim 32 words

The information retrieval architecture of claim 1 wherein the first table is used to perform indexing into the second table and third table while the third table is used to perform filtering.

Claim 15

Dependent Claim 129 words

A network router comprising at least one filter to perform a lookup on information in a packet header, the further thither comprising: a hashing module that receives the information in the packet header and generates a plurality of hashed values from the information in the packet header; and a first table storing a plurality of encoded values, each hashed value generated from the information in the packet header corresponding to a location in the first table of an encoded value, the table constructed so that the encoded values obtained from the information in the packet header encode an output value such that the output value cannot be recovered from any single encoded value and such that the output value is used to select forwarding information for the packet header.

Claim 16

Dependent Claim 129 words

A network router comprising at least one filter to perform a lookup on information in a packet header, the further thither comprising: a hashing module that receives the information in the packet header and generates a plurality of hashed values from the information in the packet header; and a first table storing a plurality of encoded values, each hashed value generated from the information in the packet header corresponding to a location in the first table of an encoded value, the table constructed so that the encoded values obtained from the information in the packet header encode an output value such that the output value cannot be recovered from any single encoded value and such that the output value is used to select forwarding information for the packet header.

Claim 17

Dependent Claim 36 words

The network router of claim 14 wherein the encoded values in the first table encode the output value such that the output value is recovered by combining the encoded values by performing a bit-wise XOR operation.

Claim 18

Dependent Claim 20 words

The network router of claim 14 wherein the information in the packet header is a prefix of a pre-specified length.

Claim 19

Dependent Claim 25 words

The network router of claim 16 further comprising one or more additional filters for prefixes of different pre-specified lengths, each filter performing lookups in parallel.

Claim 20

Dependent Claim 38 words

The network router of claim 17 further comprising an update filter for each filter, the update filter comprising a version of the first table that can be updated offline and swapped for the first table in the filters.

Claim 21

Dependent Claim 35 words

The network router of claim 17 further comprising a priority encoder that receives results from each filter and selects forwarding information based on the results from the filter handling a prefix of a longest length.

Claim 22

Dependent Claim 33 words

The network router of claim 14 wherein the first table is segmented into a plurality of banks, each bank associated with one of the plurality of hash values generated by the hashing module.

Claim 23

Dependent Claim 19 words

The network router of claim 14 wherein the hashing module and the first table are pipelined into different stages.

Claim 24

Dependent Claim 41 words

The network router of claim 16 further comprising a filtering module which receives the prefix in the packet header and forwards the prefix to the hashing module only if the prefix is not a member of a filtered set of prefixes.

Claim 25

Dependent Claim 28 words

The network router of claim 22 wherein the filtered set of prefixes are those prefixes that are not recognized as being members of a lockup set of prefixes.

Claim 26

Dependent Claim 28 words

The network router of claim 22 wherein the filtered set of prefixes are those prefixes selected so as to facilitate construction of the first table of encoded values.

Claim 27

Dependent Claim 54 words

The network router of claim 24 wherein the filtered set of prefixes comprises at least one prefix such that, when the hashing module generates a plurality of hashed values from the one prefix, the hashed values generated from the one prefix correspond to not one singleton location in the first table of encoded values.

Claim 28

Dependent Claim 28 words

The network router of claim 22 wherein at least one prefix is remapped by the filtering module into another prefix that is then forwarded to the hashing module.

Claim 29

Dependent Claim 23 words

The network router of claim 19 further comprising a second table storing the forwarding information as a forwarding value associated with each prefix.

Claim 30

Dependent Claim 14 words

The network router of claim 27 wherein each filter has an associated second table.

Claim 31

Dependent Claim 34 words

The network router of claim 27 wherein the priority encoder selects the filter handling the prefix of a longest length and then retrieves the forwarding information from a second table shared by the filters.

Claim 32

Dependent Claim 85 words

The network router of claim 27 further comprising a third table storing a plurality of associated prefixes in a lookup set, each such associated prefix associated with a forwarding value in the second table, where the output value selects a forwarding value in the second table and an associated prefix from the third table, thereby identifying the prefix in the packet header as being in the lookup set if the prefix in the packet header is same as the associated prefix in the third table.

Claim 33

Dependent Claim 51 words

The network router of claim 30 wherein the first table in the filters is constructed so that the second table has a size that is smaller than the first table and so that the width of the first table is at least log(n) where n is the number of forwarding values.

Claim 34

Dependent Claim 85 words

The network router of claim 30 further comprising a filtering module which receives the prefix in the packet header and forwards the prefix to the hashing module only if the prefix is not a member of a filtered set of prefixes, wherein at least one prefix, that is recognized as not being in the lookup set because the associated prefixes in the third table is not same as the one input value, is added to the filtered set of prefixes used by the filtering module.

Claim 35

Dependent Claim 107 words

A content-based information retrieval architecture comprising: a hashing module that receives an input value and generates a plurality of hashed values from the input value; a table storing a plurality of encoded values, each hashed value generated from the input value corresponding to a location in the table of an encoded value, the table segmented into a plurality of banks, each bank associated with one of the plurality of hash values generated by the hashing module, and the table constructed so that the encoded values obtained from the input value encode an output value such that the output value cannot be recovered from any single encoded value.

Claim 36

Dependent Claim 107 words

A content-based information retrieval architecture comprising: a hashing module that receives an input value and generates a plurality of hashed values from the input value; a table storing a plurality of encoded values, each hashed value generated from the input value corresponding to a location in the table of an encoded value, the table segmented into a plurality of banks, each bank associated with one of the plurality of hash values generated by the hashing module, and the table constructed so that the encoded values obtained from the input value encode an output value such that the output value cannot be recovered from any single encoded value.

Claim 37

Dependent Claim 33 words

The information retrieval architecture of claim 33 wherein the encoded values encode the output value such that the output value is recovered by combining the encoded values by performing a bit-wise XOR operation.

Claim 38

Dependent Claim 15 words

The information retrieval architecture of claim 33 wherein the table is stored in non-multi-ported memory.

Claim 39

Dependent Claim 111 words

A content-based information retrieval architecture comprising: a hashing unit that receives an input value and generates a plurality of hashed values from the input value; a memory unit that stores a table of encoded values, each hashed value generated from the input value corresponding to a location in the table of an encoded value; and a logic unit that recovers an output value from the encoded values, where the encoded values obtained from the input value encode the output value such that the output value cannot be recovered from any single encoded value, and where the hashing unit and the memory unit and the logic unit are pipelined into different stages.

Claim 40

Dependent Claim 111 words

A content-based information retrieval architecture comprising: a hashing unit that receives an input value and generates a plurality of hashed values from the input value; a memory unit that stores a table of encoded values, each hashed value generated from the input value corresponding to a location in the table of an encoded value; and a logic unit that recovers an output value from the encoded values, where the encoded values obtained from the input value encode the output value such that the output value cannot be recovered from any single encoded value, and where the hashing unit and the memory unit and the logic unit are pipelined into different stages.

Claim 41

Dependent Claim 33 words

The information retrieval architecture of claim 36 wherein the encoded values encode the output value such that the output value is recovered by combining the encoded values by performing a bit-wise XOR operation.

Claim 42

Dependent Claim 116 words

A content-based information retrieval architecture comprising: a filtering module that receives an input value and forwards the input value only if the input value is not a member of a filtered set of input values; a hashing module that receives the forwarded input value and generates a plurality of hashed values from the forwarded input value; and a table storing a plurality of encoded values, each hashed value generated from the forwarded input value corresponding to a location in the table of an encoded value, the table constructed so that the encoded values obtained from the forwarded input value encode an output value such that the output value cannot be recovered from any single encoded value.

Claim 43

Dependent Claim 116 words

A content-based information retrieval architecture comprising: a filtering module that receives an input value and forwards the input value only if the input value is not a member of a filtered set of input values; a hashing module that receives the forwarded input value and generates a plurality of hashed values from the forwarded input value; and a table storing a plurality of encoded values, each hashed value generated from the forwarded input value corresponding to a location in the table of an encoded value, the table constructed so that the encoded values obtained from the forwarded input value encode an output value such that the output value cannot be recovered from any single encoded value.

Claim 44

Dependent Claim 43 words

The information retrieval architecture of claim 38 wherein the filtered set of input values are those input values that are not recognized as being members of a lookup set of input values with associated output values encoded in the table of encoded values.

Claim 45

Dependent Claim 30 words

The information retrieval architecture of claim 38 wherein the filtered set of input values are those input values selected so as to facilitate construction of the table of encoded values.

Claim 46

Dependent Claim 58 words

The information retrieval architecture of claim 40 wherein the filtered set of input values comprises at least one input value such that, when the hashing module generates a plurality of hashed values from the one input value, the hashed values generated from the one input value correspond to not one singleton location in the table of encoded values.

Claim 47

Dependent Claim 31 words

The information retrieval architecture of claim 38 wherein at least one input value is remapped by the filtering module into another input value that is then forwarded to the hashing module.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	2009-03-27	2009-09-26	2010-03-28	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	2013-03-27	2013-09-26	2014-03-28	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	2017-03-27	2017-09-26	2018-03-28	$7700.00	Window Closed / Lapsed

Content-based information retrieval architecture

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag