Dictionary-based order-preserving string compression for...

Details Dictionary-based order-preserving string compression for... Dictionary-based order-preserving string compression for...

2011-01-11

2011-01-11

Mai, Lam T (Department: 2819)

Coded data generation or conversion

Digital code to digital code converters

Adaptive coding

C382S233000

Reexamination Certificate

active

07868789

ABSTRACT:
Methods and systems are described that involve usage of dictionaries for compressing a large set of variable-length string values with fixed-length integer keys in column stores. The dictionary supports updates (e.g., inserts of new string values) without changing codes for existing values. Furthermore, a shared-leaves approach is described for indexing such a dictionary that compresses the dictionary itself while offering access paths for encoding and decoding.

REFERENCES:
patent: 6121901 (2000-09-01), Welch et al.
patent: 7164370 (2007-01-01), Mishra
patent: 7263238 (2007-08-01), Singh
Daniel J. Abadi, Samuel R. Madden and Miguel C. Ferreira; Integrating Compression and Execution in Column-Oriented Database Systems; Proceedings of the 2006 ACM SIGMOD International Conference on Management of Data; 2006, pp. 671-682, (http://db.csail.mit.edu/projects/cstore/abadisigmod06.pdf).
Nikolas Askitis and Ranjan Sinha; HAT-trie: A Cache-conscious Trie-based Data Structure for Strings; Proceedings of the thirtieth Australasian conference on Computer science (2007), pp. 97-105, (http://crpit.com/confpapers/CRPITV62Askitis.pdf).
Nikolas Askitis and Justin Zobel; Cache-Conscious Collision Resolution in String Hash Tables; Proceedings of 12th international conference, SPIRE 2005, pp. 91-102; (http://goanna.cs.rmit.edu.au/˜jz/fulltext/spire05.pdf).
Rudolf Bayer and Karl Unterauer; Prefix B-Trees; ACM Transactions on Database Systems (TODS), 1977; vol. 2 , Issue 1, pp. 11-26 (http://wwwbayer.in.tum.de/cgi-webcon/webcon/lehrstuhldb/download/52/application/pdf).
Jon L. Bentley and Robert Sedgewick; Fast Algorithms for Sorting and Searching Strings; Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete algorithms, 1997, pp. 360-369 (http://www.citeulike.org/user/sudhanshu—goswami/article/707565).
Philip Bohannon, Peter McLlroy and Rajeev Rastogi; Main-Memory Index Structures with Fixed-Size Partial Keys; Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data, 2001, pp. 163-174; (http://portal.acm.org/citation.cfm?id=375681).
Zhiyuan Chen, Johannes Gehrke and Flip Korn; Query Optimization In Compressed Database Systems; ACM SIGMOD Record, vol. 30, Issue 2 (Jun. 2001), pp. 271-282 (http://www.cs.cornell.edu/johannes/papers/2001/sigmod2001-compression.pdf).
Jun Rao and Kenneth A. Ross; Cache Conscious Indexing for Decision-Support in Main Memory; Proceedings of the 25th International Conference on Very Large Data Bases; 1999, pp. 78-89 (http://www1.cs.columbia.edu/˜library/TR-repository/reports/reports-1998/cucs-019-98.pdf).
Ranjan Sinha, David Ring and Justin Zobel; Cache-Efficient String Sorting Using Copying; ACM Journal of Experimental Algorithmics (ACM JEA), 11(1.2), 2006 (http://www.cs.mu.oz.au/˜rsinha/papers/SinhaRingZobel-2006.pdf).
Mike Stonebraker et al.; C-Store: A Column-oriented DBMS; Proceedings of the 31st international conference on Very large data bases; Session: Research session: architectural issues, 2005, pp. 553-564 (http://db.csail.mit.edu/projects/cstore/vldb.pdf).
Jingren Zhoul and Kenneth A. Ross; Buffering Accesses to Memory-Resident Index Structures; Proceedings of the 29th international conference on Very large data bases—vol. 29, 2003, pp. 405-416 (http://www1.cs.columbia.edu/˜kar/pubsk/buffer.pdf).
Jonathan Goldstein et al.; Compressing Relations and Indexes; Proceedings of the Fourteenth International Conference on Data Engineering; 1998, pp. 370-379 (http://portal.acm.org/citation.cfm?id=656226).
G. Antoshenkov et al.; Order Preserving String Compression; Proceedings of the Twelfth International Conference on Data Engineering, 1996, pp. 655-663 (http://ieeexplore.ieee.org/xpl/freeabs—all.jsp?arnumber=492216).
Ian H. Witten et al.; Managing Gigabytes: Compressing and Indexing Documents and Images—2nd edition; Chapter Two—Text Compression; Morgan Kaufmann Publishers, Inc., USA, 1999; pp. 82; (http://ww2.cs.mu.oz.au/mg/blurb.pdf).
Ian H. Witten et al.; Managing Gigabytes: Compressing and Indexing Documents and Images—2nd edition; Chapter Three—Indexing; Morgan Kaufmann Publishers, Inc., USA, 1999; pp. 49; (http://ww2.cs.mu.oz.au/mg/blurb.pdf).
Ian H. Witten et al.; Managing Gigabytes: Compressing and Indexing Documents and Images—2nd edition; Chapter Four—Querying; Morgan Kaufmann Publishers, Inc., USA, 1999; pp. 70; (http://ww2.cs.mu.oz.au/mg/blurb.pdf).
Ian H. Witten et al.; Managing Gigabytes: Compressing and Indexing Documents and Images—2nd edition; Chapter Five—Index Construction; Morgan Kaufmann Publishers, Inc., USA, 1999; pp. 39; (http://ww2.cs.mu.oz.au/mg/blurb.pdf).
European Search Report for EP Application No. 10004976.6, mailed on Sep. 9, 2010, 11 pages.
Daniel J. Abadi et al.; Integrating Compression and Execution in Column-Oriented Database Systems; Proceedings of the 2006 ACM SIGMOD international conference on Management of data; pp. 671-682; (http://db.csail.mit.edu/projects/cstore/abadisigmod06.pdf).
Gennady Antoshenkov et al.; Order preserving string compression; Proceedings of the Twelfth International Conference on Data Engineering, 1996; pp. 655-663; (http://research.microsoft.com/apps/pubs/default.aspx? id=68322).
Zhiyuan Chen et al.; Query Optimization in Compressed Database Systems; SIGMOD Record, ACM, New York, NY US, vol. 30, Issue 2 (Jun. 2001); pp. 271-282 (http://portal.acm.org/citation.cfm?id=376284.375692).
Till Westmann et al.; The Implementation and Performance of Compressed Databases; SIGMOD Record, ACM, New York, NY US, vol. 29 , Issue 3, 2000; pp. 55-67 (http://portal.acm.org/citation.cfm?id=362137).
Mario A. Nascimento et al.; Indexing Bitemporal Databases Via Trees with Shared Leaves - The SLT Approach, 1995, pp. 28, retrieved from Internet (http://citeseerx.ist.psu.edu/viewdocdownload?doi=10.1.1.54.4479&rep=rep1&type=pdf).
W.P. Cockshott et al.; High Performance Operations Using a Compressed Database Architecture; The Computer Journal (1998); vol. 41; No. 5; Oxford University Press; Surrey GB; pp. 283-296 (http://comjnl.oxfordjournals.org/content/41/5/283.abstract).
G. Graefe et al.; Data compression and database performance; Applied Computing 1991; Proceedings of the 1991 Symposium on Kansas City MO, USA; pp. 22-27 (http://ieeexplore.ieee.org/xpl/freeabs—all.jsp?arnumber=143840).

Affiliated with

Also associated with

Rating

Dictionary-based order-preserving string compression for... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Dictionary-based order-preserving string compression for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dictionary-based order-preserving string compression for... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2737127