System for searching information using combinatorial signature d

Details System for searching information using combinatorial signature d System for searching information using combinatorial signature d

1992-02-19

1994-06-07

Lee, Thomas C.

Coded data generation or conversion

Digital code to digital code converters

Tree structure

341 55, 341 60, 341 78, 341 79, 364DIG1, 36422281, 36422282, 3642821, 3642822, 3642823, 3642831, G06F 1540, G06F 15411, H03M 730

Patent

active

053197798

ABSTRACT:
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 be efficiently 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) of each 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.

REFERENCES:
patent: 4118788 (1978-10-01), Roberts
patent: 4677550 (1987-06-01), Ferguson et al.
patent: 4817036 (1989-03-01), Millett et al.
patent: 4841433 (1989-06-01), Hakim et al.
patent: 4991087 (1991-02-01), Burkowski et al.
W. Litwin et al., A New Method for Fast Data Searches with Keys, IEEE Software, vol. 4, No. 2, Mar. 1987, pp. 16-24.
C. J. Guarin, Access by Content of Documents in an Office Information System, 11th International Conf. on Research & Dev. in Infor. Retrieval, Jun. 13, 1988, Grenoble, France, pp. 629-649.
R. Sacks-Davis et al., Multikey Access Methods Based on Superimposed Coding Techniques, ACM Transactions on Database Systems, vol. 12, No. 4, pp. 655-696, Dec. 1987.
Roberts, "Partial-Match Retrieval Via The Method of Super-Imposed Codes", Proceedings of the IEEE, vol. 67, No. 12, Dec. 1979, pp. 1624-1642.
Pfaltz et al., "Partial-Match Retrieval Using Indexed Descriptor Files", Communications of the ACM, Sep. 1980, vol. 23, No. 9, pp. 522-528.
Deppisch, "S-Tree: A Dynamic Balanced Signature Index for Office Retrieval" Proceedings of the 1986 ACM Conference, Sep. 8-10, 1986.
Harrison, "Implementation of the Substring Test by Hashing" Communications of the ACM, vol. 14, No. 12, Dec. 1971, pp. 777-779.
King et al., "Design of a Document Filing and Retrieval Service" IBM Research Report, Nov. 1982.
Dadam et al., "A Predicate Oriented Locking Approach for Integrated Information Systems" Information Processing 83, Sep. 19-23, 1983.
Goyal, "Coding Methods for Text String Search on Compressed Databases" Information Systems, vol. 8, No. 3, pp. 231, 233, 1983.
Faloutsos et al., "Optical Signature Extraction and Information Loss" ACM Transactions on Database Systems, vol. 12, No. 3, Sep. 1987, pp. 395-428.
Christodoulakis et al., "Design Considerations for a Message File Server", IEEE Transactions on Software Engineering, vol. SE-10, No. 2 Mar. 1984, pp. 201-209.
Faloutsos, "Signature Files: Design and Performance Comparison of Some Signature Extraction Methods" ACM, 1985, pp. 63-82.
Faloutsos, "Design of a Signature File Method that Accounts for Non-Uniform Occurrence and Query Frequencies" Proceedings of VLDB 85, pp. 165-170.
Sacks-Davis et al., "A Two-Level Superimposed Coding Scheme for Partial Match Retrieval" Information Systems, vol. 8, No. 4, pp. 273-280, 1983.
Schek, "The Reference String Indexing Method" Information Methodology, vol. 65, 1978, pp. 432-459.

Affiliated with

Also associated with

Rating

System for searching information using combinatorial signature d does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with System for searching information using combinatorial signature d, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System for searching information using combinatorial signature d will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-800965