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

Patent 5832479 Issued on November 3, 1998. Estimated Expiration Date:

March 28, 2017. 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.

Method for compressing full text indexes with document identifiers and location offsets Patent #: 5649183
Issued on: 07/15/1997
Inventor: Berkowitz, et al.

Inventors

Assignee

Microsoft Corporation

Application

No. 829461 filed on 03/28/1997

US Classes:

707/3, Query processing (i.e., searching)707/6, Pattern matching access712/300BYTE-WORD REARRANGING, BIT-FIELD INSERTION OR EXTRACTION, STRING LENGTH DETECTING, OR SEQUENCE DETECTING

Examiners

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

Attorney, Agent or Firm

Seed and Berry, LLP

Foreign Patent References

0 124 097 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 Textual 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," Proceedings of the 18th VLDB Conference, Vancouver, British Columbia, Canada, Aug. 1992, pp. 352-362
Witten et al., "Indexing and Compressing Full-Text Databases for CD-ROM," Journal of Information Science, vol. 17, n(5), pp. 265-271. Dec., 1990
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-36