Method for compressing full text indexes with document identifiers and location offsets

Patent 5649183 Issued on July 15, 1997. Estimated Expiration Date:

July 15, 2014. Estimated Expiration Date is calculated based on simple USPTO term provisions. It does not account for terminal disclaimers, term adjustments, failure to pay maintenance fees, or other factors which might affect the term of a patent.

Abstract Claims Description Full Text

Patent References

Information retrieval system and method
Patent #: 5062074
Issued on: 10/29/1991
Inventor: Kleinberger

High speed computer system for search and retrieval of data within text and record oriented files
Patent #: 5201048
Issued on: 04/06/1993
Inventor: Coulter, et al.

Method for storing bibliometric information on items from a finite source of text, and in particular document postings for use in a full-text document retrieval system
Patent #: 5293552
Issued on: 03/08/1994
Inventor: Aalbersberg

Method for locating compressed data in a computed memory back up device including steps of refining estimater location
Patent #: 5313604
Issued on: 05/17/1994
Inventor: Godwin

Adaptive ranking system for information retrieval
Patent #: 5321833
Issued on: 06/14/1994
Inventor: Chang, et al.

Method of indexing keywords for searching in a database recorded on an information recording medium
Patent #: 5375235
Issued on: 12/20/1994
Inventor: Berry, et al.

Record retrieval method using key bondary value table and condition valid status table
Patent #: 5398338
Issued on: 03/14/1995
Inventor: Yoshida

System and method for database tomography
Patent #: 5440481
Issued on: 08/08/1995
Inventor: Kostoff, et al.

System of document representation retrieval by successive iterated probability sampling Patent #: 5488725
Issued on: 01/30/1996
Inventor: Turtle, et al.

Inventors

Assignee

Microsoft Corporation

Application

No. 986754 filed on 12/08/1992

US Classes:

707/6, Pattern matching access712/300, BYTE-WORD REARRANGING, BIT-FIELD INSERTION OR EXTRACTION, STRING LENGTH DETECTING, OR SEQUENCE DETECTING715/530, Edit, composition, or storage control715/531Text

Examiners

Primary: Black, Thomas G.
Assistant: Alam, Hosain T.

Attorney, Agent or Firm

Seed and Berry LLP

Foreign Patent References

0124097 EP 11/13/1984

International Class

G06F 017/30

Abstract

A method is disclosed for recording a text index wherein the text index comprises a plurality of data key fields. Each data key field includes a data key identifier, document identifier data, and an offset field. The document identifier data is provided to identify each document in which the data key identifier appears. The offset field includes a plurality of offset sequences wherein each offset sequence is associated with a respective document identified by the document identifier data and wherein each offset sequence identifies the location of each data key within its associated document by identifying the offset of the data key from the preceding data key. In accordance with the subject invention, the document identifier data and the offset data field are compressed by disclosed methods.

Other References

Mullin, J.K., "Accessing Textural Documents using Compressed Indexes of Arrays of Small Bloom Filters", The Computer Journal, Aug. 1987, vol. 30, No. 4, pp. 343-348
Choueka, Y. et al., "Compression of Concordances in Full-Text Retrieval Systems", 11th International Conference on Research & Development in Information Retrieval, Grenoble, France, Jun. 13-15, 1988, pp. 597-612
Zobel, Justin et al., "An Efficient Indexing Technique for Full-Text Database Systems", Proceedings of the 18th VLDB Conference, Vancouver, British Columbia, Canada, Aug. 1992, pp. 352-362
"Indexing and Compressing Full-text Databases for CD-ROM", Witten et al., Journal of Information Science, vol. 17, n(5), p(265-271). Dec. 199