Combinatorial signatures for data encoding and searching

Details Combinatorial signatures for data encoding and searching Combinatorial signatures for data encoding and searching

G - Physics

06

F

354/67

G06F 17/30 (2006.01)

Patent

CA 2000006

This invention encodes information (such as the field values of a database record, or the words of a text document) so that the original information may beefficiently searched by a computer. An information object is encoded into a small "signature" or codeword using a method. A base or "leaf" signature S1 34 is computed by a known technique such as hashing. The logical intersection (AND) ofeach possible combination of pairs of bits of the base signature is computed, and the result is stored as one bit of a longer combinatorial signature CS1 42. The bit-wise logical union (bit-OR) of the combinatorial signatures of a group of records produces a second-level combinatorial signature CS2 52 representing particular field values present among those records. Higher-level combinatorial signatures CS3 60, CS4, etc. are computed similarly. These combinatorial signatures avoid a "saturation"problem which occurs when signatures are grouped together, and a "combinatorial error" problem which falsely indicates the existence of nonexistent records, thereby significantly improving the ability to reject data not relevant to a given query. When the combinatorial signatures are stored in a hierarchical data structure, such as a B- tree index of a database management system, they provide means for more efficiently searching database records or document text by eliminating large amounts of nonmatching data from further consideration.

Affiliated with

Also associated with

Rating

Combinatorial signatures for data encoding and searching does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Combinatorial signatures for data encoding and searching, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Combinatorial signatures for data encoding and searching will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFCA-PAI-O-1644069