Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2004-11-24
2009-02-03
Lee, Wilson (Department: 2163)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
07487169
ABSTRACT:
A differential compression method and computer program product combines hash value techniques and suffix array techniques. The invention finds the best matches for every offset of the version file, with respect to a certain granularity and above a certain length threshold. The invention has two variations depending on block size choice. If the block size is kept fixed, the compression performance of the invention is similar to that of the greedy algorithm, without the expensive space and time requirements. If the block size is varied linearly with the reference file size, the invention can run in linear-time and constant-space. It has been shown empirically that the invention performs better than certain known differential compression algorithms in terms of compression and speed.
REFERENCES:
patent: 5281967 (1994-01-01), Jung
patent: 5371499 (1994-12-01), Graybill et al.
patent: 5532694 (1996-07-01), Mayers et al.
patent: 5799301 (1998-08-01), Castelli et al.
patent: 5930789 (1999-07-01), Agrawal et al.
patent: 5946692 (1999-08-01), Faloutsos et al.
patent: 6119120 (2000-09-01), Miller
patent: 6226634 (2001-05-01), Ogihara et al.
patent: 6359574 (2002-03-01), Yariv
patent: 6374250 (2002-04-01), Ajtai et al.
patent: 6392567 (2002-05-01), Satoh
patent: 6553372 (2003-04-01), Brassell et al.
patent: 6611832 (2003-08-01), Van Lunteren
patent: 6697810 (2004-02-01), Kumar et al.
patent: 6738762 (2004-05-01), Chen et al.
patent: 6792423 (2004-09-01), Jeffries et al.
patent: 7353225 (2008-04-01), Dada
patent: 2002/0010702 (2002-01-01), Ajtai et al.
patent: 2002/0152219 (2002-10-01), Singh
patent: 2002/0161860 (2002-10-01), Godlin et al.
patent: 2003/0030575 (2003-02-01), Frachtenberg et al.
patent: 2003/0120647 (2003-06-01), Aiken et al.
patent: 2003/0187856 (2003-10-01), Luk et al.
patent: 2003/0212712 (2003-11-01), Gu et al.
patent: 2004/0148506 (2004-07-01), Prince
R.C. Bums et al., “Efficient distributed backup with delta compression”, Proc. of the Fifth Workshop on I/O in Paralle and Dist. Syst., Nov. 1997.
R.A. Wagner et al., “The string-to-string correction problem”, Journal of the Association for Computing Machinery, vol. 21, No. 1, Jan. 1974, pp. 168-173.
W. Miller et al., “A file comparison program”, Software-Practice and Experience. vol. 15, Nov. 1985, pp. 1025-1040.
C. Reichenberger, “Delta storgae for arbitrary non-text files”, Proc. of the 3rd Int'l. Workshop on Software Configuration Management, Norway, Jun. 1991, ACM pp. 144-152.
J.J. Hunt et al., “Delta algorithms: An empirical analysis”, ACM Trans. on Software Eng. and Meth., vol. 7, No. 2, 1998, pp. 192-214.
J. P. MacDonald, “Versioned file archiving, compression, and distribution”, U.C. Berkeley, 1998.
M. Ajtai et al., “Compactly encoding unstructured inputs with differential compression”, Journal of ACM, vol. 49, No. 3, May 2002, pp. 318-367.
J. Ziv et al., “A universal algorithm for sequential data compression”, IEEE Transactions on Information Theory, vol. 23, No. 3, May 1977, pp. 337-343.
W.F. Tichy, “The string-to-string correction problem with block moves”, ACM Transactions on Computer Systems, vol. 2, No. 4, 1984, pp. 309-321.
J.P. Mac Donald, “File System Support for Delta Compression”, Masters Thesis at the University of California, Berkeley, 2000. Available at http://www.xcf.berkeley.edu/jmacd/.
P. Weiner, “Linear pattern matching algorithms”, Proc. of the 14th Annual IEEE Symposium on Switching and Automata Theory. IEEE Computer Society Press, Los Alamitos, Calif., Oct. 15-17, 1973, pp. 1-11.
U. Manber et al., “Suffix arrays: A New Method for On-Line String Searches”, First annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Jan. 1990, pp. 319-327.
Shapira et al., “In Place Differential File Compression”, Proc. of the Data Compression Conference (DCC), 2003, pp. 1-10.
R.M. Karp et al., “Efficient randomized pattern-matching algorithms”, IBM Journal of Research and Development, vol. 31, No. 2, Mar. 1987, pp. 249-260.
R. Agarwal et al., “An approximation to the greedy algorithm for differential compression”, Jan. 2004.
S. Rao Kosaraju, “Real-time pattern matching and quasi-real-time construction of suffix trees”, Proc. of the 28th Annual ACM Symp. on Theory of Comp. (STOC), ACM 1994, Montreal, Quebec, Canada, May 23-25, 1994, pp. 310-316.
M. Farach et al., “Perfect hashing for strings: Formalization and algorithms”, Proc. of the 7th annual symposium on combinatorial Pattern Matching, 1996.
B. Bollobas et al., “Time-series similarity problems and well-separated geometric sets”, Proc. of the 13th Annual Symposium on Comp. Geometry (SGC), 1997, pp. 454-457.
N. Yazdani et al., “Sequence matching of images”, Proc. of the 8th Conf. on Scientific and Statistical Database Management (SSDBM), 1996, pp. 53-63.
Darno Patrick A
International Business Machines - Corporation
Lee Wilson
McSwain Marc D.
LandOfFree
Method for finding the longest common subsequences between... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for finding the longest common subsequences between..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for finding the longest common subsequences between... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4092240