Index compression

Details Index compression Index compression

2008-06-20

2011-10-04

Leroux, Etienne (Department: 2161)

Data processing: database and file management or data structures

File or database maintenance

Database recovery

C707S800000, C711S170000, C711S171000, C711S172000, C711S173000

Reexamination Certificate

active

08032495

ABSTRACT:
Compressing and decompressing compressed index lists. One or more index lists include at least a portion of the list that is compressed. A method includes reading an entry from a list. The method further includes determining that the entry indicates the start of a compressed block of the list. The compressed block is compressed using a compression algorithm including a plurality of delta pointers. Each of the delta pointers point to data store entries by reference to a difference from a reference in a previous entry in the list. An entry size indicator is referenced. The entry size indicator is configured to indicate a memory storage size for a delta pointer, and the entry size indicator supports indications for all of fixed storage sizes, variable storage sizes, and run length encoding. The compressed block of the list is decompressed according to the entry size indicator.

REFERENCES:
patent: 4961139 (1990-10-01), Hong et al.
patent: 5530854 (1996-06-01), Emery et al.
patent: 5590716 (1997-01-01), Mansfield
patent: 5664179 (1997-09-01), Tucker
patent: 5699441 (1997-12-01), Sagawa
patent: 5701459 (1997-12-01), Millett
patent: 5737734 (1998-04-01), Schultz
patent: 5740445 (1998-04-01), Okuda
patent: 5761652 (1998-06-01), Wu
patent: 5799312 (1998-08-01), Rigoutsos
patent: 5850565 (1998-12-01), Wightman
patent: 6018733 (2000-01-01), Kirsch et al.
patent: 6026398 (2000-02-01), Brown
patent: 6076051 (2000-06-01), Messerly
patent: 6128613 (2000-10-01), Wong et al.
patent: 6216123 (2001-04-01), Robertson et al.
patent: 6233571 (2001-05-01), Egger et al.
patent: 6253188 (2001-06-01), Witek
patent: 6473729 (2002-10-01), Gastaldo et al.
patent: 6584458 (2003-06-01), Millett et al.
patent: 6584465 (2003-06-01), Zhu
patent: 6658626 (2003-12-01), Aiken
patent: 6678686 (2004-01-01), Patel
patent: 6718325 (2004-04-01), Chandra
patent: 6748401 (2004-06-01), Blackburn
patent: 6772141 (2004-08-01), Pratt
patent: 6778981 (2004-08-01), Lee
patent: 6785677 (2004-08-01), Fritchman
patent: 6804664 (2004-10-01), Hartman et al.
patent: 6947931 (2005-09-01), Bass et al.
patent: 6985904 (2006-01-01), Kaluskar et al.
patent: 6993533 (2006-01-01), Barnes
patent: 7139753 (2006-11-01), Bass et al.
patent: 7181438 (2007-02-01), Szabo
patent: 7266553 (2007-09-01), Anderson et al.
patent: 7590716 (2009-09-01), Sinclair
patent: 7640363 (2009-12-01), Teodosiu
patent: 2001/0050682 (2001-12-01), Deering et al.
patent: 2002/0099536 (2002-07-01), Bordner et al.
patent: 2002/0099685 (2002-07-01), Takano
patent: 2002/0103799 (2002-08-01), Bradford
patent: 2003/0074341 (2003-04-01), Blackburn et al.
patent: 2003/0097356 (2003-05-01), Lee et al.
patent: 2003/0191737 (2003-10-01), Steele
patent: 2004/0225497 (2004-11-01), Callahan
patent: 2004/0225643 (2004-11-01), Alpha et al.
patent: 2004/0260694 (2004-12-01), Chaudhuri et al.
patent: 2005/0108230 (2005-05-01), Carroll
patent: 2005/0108394 (2005-05-01), Braun et al.
patent: 2005/0114298 (2005-05-01), Fan et al.
patent: 2005/0131872 (2005-06-01), Calbucci et al.
patent: 2005/0171926 (2005-08-01), Thione
patent: 2005/0281469 (2005-12-01), Anderson et al.
patent: 2005/0283468 (2005-12-01), Kamvar
patent: 2006/0004740 (2006-01-01), Dettinger
patent: 2006/0036649 (2006-02-01), Simske et al.
patent: 2006/0080361 (2006-04-01), Suzuki
patent: 2006/0106793 (2006-05-01), Liang
patent: 2006/0126916 (2006-06-01), Kokumai
patent: 2006/0195672 (2006-08-01), Inoue
patent: 2006/0212420 (2006-09-01), Murthy
patent: 2006/0235843 (2006-10-01), Musgrove et al.
patent: 2006/0265396 (2006-11-01), Raman
patent: 2007/0027864 (2007-02-01), Collins et al.
patent: 2007/0033165 (2007-02-01), Sheinwald et al.
patent: 2007/0073894 (2007-03-01), Erickson et al.
patent: 2007/0088686 (2007-04-01), Hurst-Hiller
patent: 2007/0106876 (2007-05-01), Goswami
patent: 2007/0156677 (2007-07-01), Szabo
patent: 2007/0162481 (2007-07-01), Millett
patent: 2007/0175674 (2007-08-01), Brinson
patent: 2007/0203898 (2007-08-01), Carmona
patent: 2007/0250494 (2007-10-01), Peoples et al.
patent: 2008/0018794 (2008-01-01), Fung
patent: 2008/0154938 (2008-06-01), Cheslow
patent: 2009/0019038 (2009-01-01), Millett
patent: WO 2007082212 (2007-07-01), None
patent: WO 2007103815 (2007-09-01), None
U.S. Appl. No. 11/328,863, filed Jan. 10, 2006, Millett.
U.S. Appl. No. 60/779,214, filed Mar. 3, 2006, Millett.
U.S. Appl. No. 11/681,673, filed Mar. 2, 2007, Millett.
U.S. Appl. No. 11/847,688, filed Aug. 30, 2007, Millett.
U.S. Appl. No. 11/847,784, filed Aug. 30, 2007, Millett.
U.S. Appl. No. 11/847,869, filed Aug. 30, 2007, Millett.
U.S. Appl. No. 12/143,441, filed Jun. 20, 2008, Millett.
Manning, Christopher D. and Schutze, Hinrich Foundations of Statistical Natural Language Processing, The MIT Press, Cambridge Massachusetts, May 1999 (pp. 151, 158, 192-194, 377 and 532).
Mitra, Mandar et al. “An Analysis of Statistical and Syntactic Phrases”, Jun. 1997.
Possas, Bruno et al. “Set-Based Vector Model: An Efficient Approach for Correlation-Based Ranking”, Oct. 2005.
Office Action mailed Feb. 20, 2008 cited in related case U.S. Appl. No. 11/328,863.
Ceglowski, Maciej “Using Bloom Filters”, Apr. 8, 2004, http://www.perl.com/pub/a/2004/04/08/bloom—filters.html, 4 pages.
Office Action dated Dec. 29, 2008 cited in U.S. Appl. No. 11/681,673.
Notice of Allowance mailed in U.S. Appl. No. 11/681,673, Oct. 5, 2009.
Office Action dated Nov. 27, 2009 cited in U.S. Appl. No. 11/847,688.
Office Action dated Jan. 8, 2010 cited in U.S. Appl. No. 11/847,869.
Office Action dated Mar. 4, 2010 cited in U.S. Appl. No. 11/847,784.
U.S. Appl. No. 12/143,441, Mail Date May 12, 2010, Office Action.
Roblee, Chris, “Hierarchical Bloom Filters: Accelerating Flow Queries and Analysis”, Lawrence Livermore National Laboratory FloCon 2008, dated Jan. 8, 2008.
U.S. Appl. No. 11/847,688, Mail Date Apr. 1, 2010, Notice of Allowance.
U.S. Appl. No. 13/052,399, filed Mar. 21, 2011, Millett.
U.S. Appl. No. 11/847,784, Mail Date Aug. 19, 2010, Office Action.
U.S. Appl. No. 12/211,713, Mail Date Sep. 16, 2008, Office Action.
U.S. Appl. No. 11/847,869, Mail Date May 13, 2010, Notice of Allowance.
U.S. Appl. No. 12/143,441, Mail Date Dec. 14, 2010, Notice of Allowance.
U.S. Appl. No. 12/211,713, Mail Date Jan. 12, 2011, Office Action.

Affiliated with

Also associated with

Rating

Index compression does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Index compression, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Index compression will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4273214