Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2007-09-18
2007-09-18
Wassum, Luke S (Department: 2167)
Data processing: database and file management or data structures
Database design
Data structure types
Reexamination Certificate
active
10861796
ABSTRACT:
A system and method for unorchestrated determination of data sequences using “sticky byte” factoring to determine breakpoints in digital sequences such that common sequences can be identified. Sticky byte factoring provides an efficient method of dividing a data set into pieces that generally yields near optimal commonality. This is effectuated by employing a rolling hashsum and, in an exemplary embodiment disclosed herein, a threshold function to deterministically set divisions in a sequence of data. Both the rolling hash and the threshold function are designed to require minimal computation. This low overhead makes it possible to rapidly partition a data sequence for presentation to a factoring engine or other applications that prefer subsequent synchronization across the data set.
REFERENCES:
patent: 3668647 (1972-06-01), Evangelisti et al.
patent: 4215402 (1980-07-01), Mitchell et al.
patent: 4404676 (1983-09-01), DeBenedictis
patent: 4649479 (1987-03-01), Advani et al.
patent: 4761785 (1988-08-01), Clark et al.
patent: 4887204 (1989-12-01), Johnson et al.
patent: 4887235 (1989-12-01), Holloway et al.
patent: 4897781 (1990-01-01), Chang et al.
patent: 4901223 (1990-02-01), Rhyne
patent: 4929946 (1990-05-01), O'Brien et al.
patent: 4982324 (1991-01-01), McConaughy et al.
patent: 5005122 (1991-04-01), Griffin et al.
patent: 5018060 (1991-05-01), Gelb et al.
patent: 5089958 (1992-02-01), Horton et al.
patent: 5109515 (1992-04-01), Laggis et al.
patent: 5133065 (1992-07-01), Cheffetz et al.
patent: 5146568 (1992-09-01), Flaherty et al.
patent: 5155835 (1992-10-01), Belsan
patent: 5162986 (1992-11-01), Graber et al.
patent: 5163148 (1992-11-01), Walls
patent: 5210866 (1993-05-01), Milligan et al.
patent: 5218695 (1993-06-01), Noveck et al.
patent: 5239637 (1993-08-01), Davis et al.
patent: 5239647 (1993-08-01), Anglin et al.
patent: 5239659 (1993-08-01), Rudeseal et al.
patent: 5263154 (1993-11-01), Eastridge et al.
patent: 5276860 (1994-01-01), Fortier et al.
patent: 5276867 (1994-01-01), Kenley et al.
patent: 5278838 (1994-01-01), Ng et al.
patent: 5305389 (1994-04-01), Palmer
patent: 5317728 (1994-05-01), Tevis et al.
patent: 5325505 (1994-06-01), Hoffecker et al.
patent: 5347653 (1994-09-01), Flynn et al.
patent: 5355453 (1994-10-01), Row et al.
patent: 5367637 (1994-11-01), Wei
patent: 5367698 (1994-11-01), Webber et al.
patent: 5379418 (1995-01-01), Shimazaki et al.
patent: 5403639 (1995-04-01), Belsan et al.
patent: 5404508 (1995-04-01), Konrad et al.
patent: 5404527 (1995-04-01), Irwin et al.
patent: 5448718 (1995-09-01), Cohn et al.
patent: 5452440 (1995-09-01), Salsburg
patent: 5452454 (1995-09-01), Basu
patent: 5454099 (1995-09-01), Myers et al.
patent: 5479654 (1995-12-01), Squibb
patent: 5485474 (1996-01-01), Rabin
patent: 5487160 (1996-01-01), Bemis
patent: 5497483 (1996-03-01), Beardsley et al.
patent: 5513314 (1996-04-01), Kandasamy et al.
patent: 5515502 (1996-05-01), Wood
patent: 5521597 (1996-05-01), Dimitri
patent: 5524205 (1996-06-01), Lomet et al.
patent: 5532694 (1996-07-01), Mayers et al.
patent: 5535407 (1996-07-01), Yanagawa et al.
patent: 5544320 (1996-08-01), Konrad
patent: 5559991 (1996-09-01), Kanfi
patent: 5574906 (1996-11-01), Morris
patent: 5586322 (1996-12-01), Beck et al.
patent: 5604862 (1997-02-01), Midgely et al.
patent: 5606719 (1997-02-01), Nichols et al.
patent: 5608801 (1997-03-01), Aiello et al.
patent: 5640561 (1997-06-01), Satoh et al.
patent: 5649196 (1997-07-01), Woodhill et al.
patent: 5659743 (1997-08-01), Adams et al.
patent: 5659747 (1997-08-01), Nakajima
patent: 5696901 (1997-12-01), Konrad
patent: 5742811 (1998-04-01), Agrawal et al.
patent: 5751936 (1998-05-01), Larson et al.
patent: 5754844 (1998-05-01), Fuller
patent: 5765173 (1998-06-01), Cane et al.
patent: 5771354 (1998-06-01), Crawford
patent: 5778395 (1998-07-01), Whiting et al.
patent: 5794254 (1998-08-01), McClain
patent: 5802264 (1998-09-01), Chen et al.
patent: 5802297 (1998-09-01), Engquist
patent: 5909677 (1999-06-01), Broder et al.
patent: 5933104 (1999-08-01), Kimura
patent: 5978791 (1999-11-01), Farber et al.
patent: 5990810 (1999-11-01), Williams
patent: 6014676 (2000-01-01), McClain
patent: 6016553 (2000-01-01), Schneider et al.
patent: 6029168 (2000-02-01), Frey
patent: 6044220 (2000-03-01), Breternitz, Jr.
patent: 6085298 (2000-07-01), Ohran
patent: 6122754 (2000-09-01), Litwin et al.
patent: 6141421 (2000-10-01), Takaragi et al.
patent: 6230155 (2001-05-01), Broder et al.
patent: 6268809 (2001-07-01), Saito
patent: 6307487 (2001-10-01), Luby
patent: 6320520 (2001-11-01), Luby
patent: 6374250 (2002-04-01), Ajtai et al.
patent: 6611213 (2003-08-01), Bentley et al.
patent: 6667700 (2003-12-01), McCanne et al.
patent: 6704730 (2004-03-01), Moulton et al.
patent: 6810398 (2004-10-01), Moulton
patent: 6828925 (2004-12-01), McCanne et al.
patent: 6961009 (2005-11-01), McCanne et al.
patent: 7116249 (2006-10-01), McCanne et al.
patent: 2001/0037323 (2001-11-01), Moulton et al.
patent: 2002/0010797 (2002-01-01), Moulton
patent: 2002/0152218 (2002-10-01), Moulton
patent: 2004/0148306 (2004-07-01), Moulton et al.
patent: 2005/0091234 (2005-04-01), Hsu et al.
patent: PCT/AU96/00081 (1996-08-01), None
Rabin, M.O. “Fingerprinting by Random Polynomials”, Technical Report TR-15-81, Department of Computer Science, Harvard University, 1981.
Karp, R.M. and M.O. Rabin “Efficient Randomized Pattern-Matching Algorithms”m IBM Journal of Research and Development, vol. 31, No. 2, Mar. 1987, pp. 249-260.
Broder, A.Z. “On the Resemblance and Containment of Documents”, Proceedings of the IEEE Conference on Compression and Complexity of Sequences, Jun. 11-13, 1997.
Spring, N.T. and D. Wetherall “A Protocol-Independent Technique for Eliminating Redundant Network Traffic”, Proceedings of the Conference on Applications, Technologies, Architectures and Protocols for Computer Communication, 2000, pp. 87-95.
Tridgell, A. “SpamSum Overview and code”, downloaded from samba.org/ftp/unpacked/junkcode/spamsum, 2002.
Schleimer, S., D.S. Wilkerson and A. Aiken “Winnowing: Local Algorithms for Document Fingerprinting”, SIGMOD 2003, Jun. 9-12, 2003.
Scheirer, W. and M. Chuah “Comparison of Three Sliding-Window Based Worm Signature Generation Schemes”, Technical Paper LU-CSE-05-025, CSE Department, Lehigh University, 2005.
Kornblum, J. “Identifying Almost Identical Files Using Context Triggered Piecewise Hashing”, Digital Investigation, vol. 35, pp. S91-S97.
Tridgell, Andrew, Efficient Algorithms for Sorting and Synchronization, Apr. 2000, pp. i-viii, pp. 1-106.
Aho, Alfred V., Hopcroft, John E., and Ullman, Jeffrey D., Data Structures and Algorithms, 1983, Chapter 4, Addison-Wesley Publishing Company, Reading, Massachusetts, pp. 107-151.
Hegazy, A.E.F.A. “Searching Large Textual Files for Near Matching Patterns”, Dissertation, School of Engineering and Applied Science, George Wahington University, Jul. 24, 1985.
EMC Corporation
Wassum Luke S
Workman Nydegger
LandOfFree
System and method for unorchestrated determination of data... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for unorchestrated determination of data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for unorchestrated determination of data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3742689