Electrical computers and digital processing systems: multicomput – Remote data accessing
Reexamination Certificate
2004-09-24
2009-11-03
Dinh, Khanh (Department: 2151)
Electrical computers and digital processing systems: multicomput
Remote data accessing
C709S247000, C709S238000
Reexamination Certificate
active
07613787
ABSTRACT:
The present invention finds candidate objects for remote differential compression. Objects are updated between two or more computing devices using remote differential compression (RDC) techniques such that required data transfers are minimized. An algorithm provides enhanced efficiencies for allowing the receiver to locate a set of objects that are similar to the object that needs to be transferred from the sender. Once this set of similar objects has been found, the receiver may reuse any chunks from these objects during the RDC algorithm.
REFERENCES:
patent: 5446888 (1995-08-01), Pyne
patent: 5486826 (1996-01-01), Remillard
patent: 5488364 (1996-01-01), Cole
patent: 5721907 (1998-02-01), Pyne
patent: 5933104 (1999-08-01), Kimura
patent: 5987022 (1999-11-01), Geiger et al.
patent: 5990810 (1999-11-01), Williams
patent: 6049874 (2000-04-01), McClain et al.
patent: 6101507 (2000-08-01), Cane et al.
patent: 6226629 (2001-05-01), Cossock
patent: 6317754 (2001-11-01), Peng
patent: 6374250 (2002-04-01), Ajtai et al.
patent: 6449612 (2002-09-01), Bradley et al.
patent: 6574657 (2003-06-01), Dickinson
patent: 6728711 (2004-04-01), Richard
patent: 6771826 (2004-08-01), Boon
patent: 6791982 (2004-09-01), Westberg
patent: 6819271 (2004-11-01), Geiger et al.
patent: 7054912 (2006-05-01), Kanai et al.
patent: 7058941 (2006-06-01), Venkatesan et al.
patent: 7099884 (2006-08-01), Gu
patent: 2002/0010702 (2002-01-01), Ajtai et al.
patent: 2002/0152219 (2002-10-01), Garcia-Osuna et al.
patent: 2003/0028867 (2003-02-01), Kryloff et al.
patent: 2003/0061287 (2003-03-01), Yu et al.
patent: 2003/0110296 (2003-06-01), Kirsch et al.
patent: 2003/0133616 (2003-07-01), Lippincott
patent: 2003/0177485 (2003-09-01), Waldin et al.
patent: 2003/0187960 (2003-10-01), Koba et al.
patent: 2004/0015697 (2004-01-01), de Queiroz
patent: 2004/0039716 (2004-02-01), Thompson
patent: 2004/0054700 (2004-03-01), Okada
patent: 2005/0235043 (2005-10-01), Teodosiu et al.
patent: 2005/0256974 (2005-11-01), Teodosiu et al.
patent: 2005/0262167 (2005-11-01), Teodosiu et al.
patent: 2006/0047855 (2006-03-01), Gurevich et al.
patent: 2006/0064444 (2006-03-01), van Ingen et al.
patent: 2006/0085561 (2006-04-01), Manasse et al.
patent: 2006/0112113 (2006-05-01), Gu et al.
patent: 2006/0184652 (2006-08-01), Teodosiu et al.
patent: 01587007 (1995-10-01), None
patent: 01587007 (2005-10-01), None
patent: 01641219 (2006-03-01), None
patent: WO 98/27483 (1998-06-01), None
patent: WO 98/35306 (1998-08-01), None
patent: WO 02/41147 (2002-05-01), None
Randal C. Burns; “Differential Compression: A Generalized Solution for Binary Files,”University of California, Santa Cruz, Dec. 1996; (69 pgs.).
Randal C. Burns et al.; “A Linear Time, Constant Space Differencing Algorithm,”Performance, Computing and Communications Conference, IEEE International, Feb. 5-7, 1997, (8 pgs.).
Miklos Ajtai et al.; “Compactly Encoding: Unstructured Inputs with Differential Compression”; Journal of ACM, vol. 49, No. 3, May 2002; pp. 318-367.
Tridgell, The rsync algorithm,The Australian National University, Jun. 1996 (8 pgs.).
Tridgell,, “rsync algorithm,” Nov. 9, 1998 (last viewed Oct. 11, 2006) http://www.infoscience.co.jp/technical/rsync/tech—report/index.html (10 pgs.).
Tridgell,, “The Rsync Algorithm,” Jul. 21, 2000 (last viewed Oct. 11, 2006) http://olstrans.sourceforge.net/release/OLS2000-rsync/OLS2000-rsync.html (27 pgs.).
Tridgell, “Efficient Algorithms for Sorting and Synchronization,” Thesis—The Australian National University, Apr. 2000, (115 pgs.).
Samba documentation http://rsync.samba.org/documentation.html (last viewed Oct. 11, 2006) (1 pg.).
Muthitacharoen, Athicha; Chen, Benjie; Mazi{grave over ())}{grave over (})}res, David. “A low-bandwidth network file system,” Proceedings of the eighteenth ACM symposium on Operating systems principles, 2001, pp. 174-187.
Burns, Randal C.; Long, Darrell D.E. “Efficient Distributed Backup with Delta Compression,” Proceedings of the fifth workshop on I/O in parallel and distributed, 1997, pp. 27-36.
Spring, Neil T.; Wetherall, David. “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.
Douglis, Fred; Iyengar, Arun. “Application-specific Delta-encoding via Resemblance Detection,” USENIX Annual Technical Conference, 2003, [14 pages].
Torsten Suel et al.; “Improved File Synchronization Techniques for Maintaining Large Replicated Collections over Slow Networks,”In Proceedings: IEEE 20 International Conference on Data Engineering, Mar. 30, 2004 to Apr. 2, 2004, pp. 153 to 164, available from Massey University in 2004.
John Langford, “Multiround Rsync,” Jan. 31, 2001, p. 1-11.
Torsten Suel et al., “Algorithms for Delta Compression and Remote File Synchronization,” {suel,memon}@poly.eduAcademic Press, Aug. 2002, 24 pgs.
Andrei Z. Broder, On the resemblance and containment of documents,IEEE, 1997 Proceedings on Compression and Complexity of Sequences Conference Jun. 11-13, 1997 (11 pgs.).
Kave Eshghi, “Intrinsic References In Distributed Systems,”Hewlett-Packard Company, 2002, pp. 1-8.
Raffaele Giancarlo, et al., Combinatorial Pattern Matching, 11th Annual Symposium, CPM 2000,Springer(13 pgs.).
Kotz, et al., “I/O in Parallel and Distributed Systems,” Mar. 1, 1998, (last viewed Mar. 14, 2007) pp. 1-29, http://72.14.253.104/search?q=cache:OZiK—nQxc2sJ:www/cs/dart,pitj/edi/˜dfk/papers.
Dr. Jim Hamilton et al, “Design and Implementation of a Storage Repository Using Commonality Factoring,”IEEE2003 (6 pgs).
Chang, et al., Mimic: Raw Activity Shipping for File Synchronization in Mobile File Systems, 2004ACM, pp. 165-176.
Purushottam Kulkarni, et al., “Redundancy Elimination Within Large Collection of Files,”USENIX Association, 2004, pp. 59-72.
Andrei Z. Border, Identifying and Filtering Near-Duplicate Documents, Combinatorial Pattern Matching, 11th Annual Symposium, CPM 2000, Montreal, Canada, Jun. 21-23, 2000 Proceedings,Springer, (13 pgs).
Bjoner, Nikolaj; Blass, Andreas; and Gurevich, Yuri, “Content-Dependent Chunking for Differential Compression, The Local Maxim Approach,” TR-2007-102, pp. 1-93.
Chien, Steve, Jet Propulsion Laboratory, Gratch, Jonathan, Beckman Institute, “Producing satisfactory solutions to Scheduling problems: An Iterative Constraint Relaxation Approach,” 6 pp.
Fisher, Doug, “Iterative Optimization and Simplification of Hierarchical Clusterings” TR CS95-01, pp. 1-33.
Manber, Udi, “Finding Similar Files in a Large File System,” University of Arizona Technical report. TR-93-33, 11 pp.
Miyashita, Kazuo, Electrotechnical Laboratory, and Sycara, Katia, Carnegie Mellon University, “Improving System Performance in Case-Based Iterative Optimization through Knowledge Filtering,” 6 pp.
Rivest, R., “The MD4 Message-Digest Algorithm,” MIT Laboratory for Computer Science and RSA Data Security, Inc., Apr. 1992, Network Working Group, RFC 1320, 20 pp.
Teodosiu, Dan; Gjorner Nikolaj; Gurevich , Yuri; Manasse,Mark; and Porka, Joe, “Optimizing File Replication over Limited-Bandwidth Networks using Remote Differential Compression,” pp. 1-16.
Tridgell, Andrew,Rsync algorithm, http://www.infoscience.co.jp/technical/rsync/tech—report/index.html.
Tridgell, Andrew,Rsync algorithm, http://olstrans.sourceforge.net/release/OLS2000-rsync/OLS2000-rsync.html.
Samba documentation http://rsync.samba.org/documentation.html.
Muthitacharoen, et. al.,Low-Bandwidth File System(LBFS), http://pdos.csail.mit.edu/papers/lbfs:sosp01/lbfs.pdf.
Muthitacharoen, Athicha; Chen, Benjie; Mazières, David. “A low-bandwidth network file system,” Proceedings of the eighteenth ACM symposium on Operating systems prin
Manasse Mark S.
Teodosiu Dan
Wable Akhil
Dinh Khanh
Merchant & Gould P.C.
Microsoft Corporation
LandOfFree
Efficient algorithm for finding candidate objects for remote... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient algorithm for finding candidate objects for remote..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient algorithm for finding candidate objects for remote... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4128624