Patent Publication Number: US-8527660-B2

Title: Data synchronization by communication of modifications

Description:
BACKGROUND 
     The present invention relates to data synchronization, and more specifically, to synchronizing data between or among multiple devices by communicating modifications made to the data instead of communicating the modified data. 
     Handheld devices and portable computers are becoming increasingly more powerful and functional devices. Many handheld devices are now multifunction devices with multiple device roles including: personal digital assistant (PDA), cellular phone, portable media player, voice recorder, video recorder, global positioning system (GPS), camera, and electronic file storage. Similarly, portable computers now have increased functionality and mobility. Because of these improvements in handheld devices and portable computers, these devices are increasingly used to access and modify data from multiple locations. 
     Additionally, advances in wireless Internet coverage and in wireless network capabilities made a broad range of data (such as electronic files, image files, audio files and video files) accessible to mobile communication devices, laptop computers, and other types of portable communication systems. Network improvements have also allowed electronic data to be accessed and modified from virtually any location. This combination of improved wireless network access and improved portable device functionality has caused users increasingly to access and modify electronic data from multiple, often widely separated, locations. 
     Because multiple users can access and modify the same data, the different data modifications should be synchronized to ensure the each user accesses the most recent version of the data. For example, a first user may edit an electronic document in one location, and a second user later accesses the same electronic document from a different location. Synchronization ensures that the electronic document accessed by the second user includes the modifications made by the first user. Synchronization is also used where a single user can access and modify the same data from multiple devices, requiring the data to be synchronized among the multiple devices. 
     Existing methods for data synchronization require the modified data, in its entirety, to be transmitted from one device to another or to a remote server. Significant network resources can be required to transmit the altered data, especially when large data files are modified. In areas with poor network connectivity or limited network access, transmission of the modified data can substantially degrade network performance and reduce the network resources available for user actions. 
     Therefore, there is a need for a method for synchronizing data among devices that reduces the network resources used in traditional systems for data synchronization. 
     SUMMARY 
     Using various embodiments of the invention, data are synchronized between or among multiple devices by communicating the modifications made to the data instead of communicating the modified data itself. In one embodiment, the modifications made to data on one device are expressed in metadata. The metadata may comprise, for example, a set of instructions that specify modifications that can be made to recreate the modified data on another device. When synchronization is to be achieved on another device, the data on the other device are then modified using the metadata, thereby enabling the modified data to be synchronized in the other devices without transmitting the modified data to those devices. 
     In one embodiment, when a shared data file is modified at a local device, metadata describing the modification of the shared data file are generated. The generated metadata are useable by the other device to recreate the modification of the shared data file. The generated metadata can then be transmitted to another device, which is configured to recreate the modification to synchronize the data file. In an embodiment, the metadata comprise textual commands for use by an application to recreate the modification of the shared data file. To synchronize the shared data file on the remote device, the remote device uses the received metadata to modify a stored shared data file on the remote device. The metadata allow the remote device to recreate the modification of the shared data file by the local device. This conserves network resources by transmitting only metadata describing changes to the shared data file rather than transmitting the modified shared data file in its entirety. 
     In one embodiment, the size of the metadata and the size of the modified data are compared, with the smaller being transmitted. This further conserves network resources by transmitting the least amount of information that still permits data synchronization between multiple devices. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       The disclosed embodiments have other advantages and features, which will be more readily apparent from the following detailed description and the appended claims, when taken in conjunction with the accompanying drawings, in which: 
         FIG. 1  is a block diagram of an architecture of the system, according to one embodiment of the invention. 
         FIG. 2  is a high-level block diagram of a device, according to one embodiment of the invention. 
         FIG. 3  is a trace diagram illustrating the synchronization of data between a local device and a remote device, according to one embodiment of the invention. 
         FIG. 4  is an example of metadata used to describe modifications to data, according to one embodiment of the invention. 
     
    
    
     DETAILED DESCRIPTION 
     Embodiments of the invention allow shared data stored on multiple devices to be synchronized between or among the devices. When the shared data are modified on one device, for example, metadata are generated to represent the modifications. The metadata are transmitted to one or more other devices, which can use the metadata to update their locally stored data according the modifications represented in the metadata and thereby synchronize the shared data that was modified on one device. Rather than transmitting the modified data in its entirety, only the metadata describing the changes need to be transmitted. The metadata may describe the actual changes to the data or may describe how to make the changes. Because the metadata are typically smaller than the data, transmitting metadata may reduce the network resources necessary to synchronize shared data stored on multiple devices. 
     System Architecture 
       FIG. 1  illustrates one embodiment of a system  100  for synchronizing data between devices. The system  100  comprises a local device  110 , a remote device  115 , and a network  130 . In an embodiment, the system  100  further comprises a remote server  120 . Network  130  allows local device  110  and remote device  115  to communicate with each other. In one embodiment, the remote server  120  is used to allow local device  110  and remote device  115  to communicate with each other. 
     Local device  110  and remote device  115  may each include computing capabilities and data communication capabilities. For example, local device  110  and remote device  115  may be a tablet computer, a laptop computer, a portable digital assistant (PDA), a smartphone, or any device able to transmit and receive data and perform actions on data. In one embodiment, local device  110  or remote device  115  comprises a desktop computer with data communication capabilities. In another embodiment, local device  110  or remote device  115  comprises a mobile communication device that is structured to fit, and be controlled from, the palm of a hand while providing computing capabilities with wireless communication capabilities. Further embodiments of device  110  and/or device  115  are described in more detail below. 
     Further, local device  110  and remote device  115  each include data storage capabilities for storing data shared between local device  110  and remote device  115 . The shared data may comprise one or more data files, which may comprise electronic documents, graphical images, audio files, video files, e-mails, and/or any other electronic representations of information. When data are shared, both the local device  110  and remote device  115  store local copies of the shared data. Because the shared data are stored on multiple devices, the shared data stored on each device need to be synchronized so each device has a current version of the shared data. 
     The remote server  120  contains information that can be used to identify and access local device  110 , remote device  115  and other devices connected to the network  130 , such as Internet protocol (IP) addresses, or similar network addresses. The remote server  120  stores information, or data, accessible to device  110  and device  115 . In an embodiment, the remote server  120  also stores metadata describing modifications to the stored data. Alternatively, the remote server  120  uses received metadata to update locally stored data without storing the received metadata. In other embodiments, the remote server  120  stores metadata local device  110  and remote device  115  access to determine how to locally modify data. In one embodiment, the remote server  120  stores the shared data and metadata in a central location that the local device  110  and the remote device  115  use to access the shared data and metadata. Alternatively, other synchronization configurations are possible. For example, local device  110  and remote device  115  may communicate directly with each other and access information locally stored on each device in a peer-to-peer configuration. 
     The network  130  is used to transmit information between device  110 , device  115  and other devices. In one embodiment, the network  130  enables device  110 , device  115  and the remote server  120  to communicate with each other. The network  130  may comprise a conventional wireless data communication system, for example, general packet radio service (GPRS), IEEE 802.11 (or WiFi), IEEE 802.16 (or WiMax), or any other suitable wireless communication system. Alternatively, the network  130  may comprise a conventional wired data communication system, such as Ethernet, digital subscriber line (DSL), integrated services digital network (ISDN), or any other suitable wired communication system. 
       FIG. 2  is a block diagram illustrating components of the local device  110  according to an embodiment. The remote device  115  and remote server  120  may be implemented with the same or a similar structure. Those of skill in the art will recognize that other embodiments can include different and/or additional features and/or components than the ones described here. 
     Local device  110  comprises an application  210 , a metadata store  240 , a data store  230  and a communication module  250 . In an embodiment, the metadata store  240  is not present because the local device  110  may transmit metadata describing file modifications whenever a change is made, and therefore the local device  110  need not store this type of metadata. The application  210  allows a user to access and modify a data file on the device  110 . Local device  110  may also include a visual display device, such as a liquid crystal display or cathode ray tube display, allowing the application  210  to present information to the user. Further, local device  110  may include an input device, such as a keyboard, a digitizer pad, a “touch” sensitive display (e.g., pressure-sensitive (resistive), electrically-sensitive (capacitance), acoustically-sensitive (SAW, or surface acoustic wave), or photo-sensitive (infra-red)) that allows the application  210  to receive input from the user. 
     The communication module  250  enables the local device  110  to communicate with network  130  and other remote devices  115  or remote servers  120 . In an embodiment, the communication module  250  comprises a transceiver such as for infrared communication, Bluetooth communication, 3G communication, radio frequency communication, or any other wireless communication technique. In an alternative embodiment, the communication module  250  comprises a conventional wired connection, such as Ethernet, USB, etc. or other wired communication technique. The communication module  250  allows data files and/or information to be distributed using network protocols, such as Transmission Control Protocol (TCP), Internet Protocol (IP), Hypertext Transmission Protocol (HTTP), or other protocols capable of communicating data or information. 
     The application  210  allows a user to access and modify data files that are stored in the data store  230 . Alternatively, the application  210  may use and modify data files without any direct user input. The application  210  may present information to the user and receive input from a user. In an embodiment, the application  210  may also access and modify data in response to input from the metadata store  240 . Alternatively, the application  210  may generate metadata, for storage or transmission, describing the contents of the data store  230  accessed or modified by a user. Typically, the device  110  will contain a number of different applications  210  that each perform different functions (such as word processors, email clients, and various types of computer software for viewing and manipulating media), but for simplicity, an embodiment with a single application  210  is described herein. 
     The metadata store  240  stores metadata, or other information, that describes changes made to the data files by the application  210 . The metadata store  240  can be a hard disk drive, a flash memory device, or any other suitable mass storage device. Further, the metadata store  240  can be a volatile storage device, a non-volatile storage device, or a combination of a volatile storage device and a non-volatile storage device. In an embodiment, the device  110  does not include a metadata store  240 , but transmits metadata describing data modifications to remote device  115  or remote server  120  when the metadata is generated using the communication module  250 . 
     The data store  230  stores data for use by the local device  110 . The stored data can be received from the remote device  115  or the remote server  120 , or the stored data can be locally generated by a user of device  110 . The data store  230  can be a hard disk drive, a flash memory device, or some other mass storage device known in the art. Further, the data store  230  can be a volatile storage device, a non-volatile storage device, or a combination of a non-volatile storage device and a volatile storage device. 
     The data store  230  may include a shared data file  235  corresponding to data stored on local device  110  and a remote device  115  or a remote server  120 . Each device  115  that uses the shared file  235  locally stores a copy of the shared file  235  on the device  115 . The shared file  235  may comprise textual data, graphical data, video data, audio data, multimedia content, or any other information capable of being represented electronically. When a user modifies the shared file  235  on the local device  110 , the copy of the shared file  235  stored on remote devices  115  needs to be modified accordingly so the local device  110  and the remote device  115  access the same version of the shared file  235 . 
     System Operation 
       FIG. 3  is a trace diagram illustrating data synchronization between a local device  110  and a remote device  115  according to one embodiment. Those of skill in the art will recognize that other embodiments can perform the steps of  FIG. 3  in different orders. Moreover, other embodiments can include different and/or additional steps than the ones described here. 
     Initially, the shared file  235 , or other shared data, is modified  310  on the local device  110 . In an embodiment, the data modification  310  is responsive to user actions. Alternatively, the data modification  310  may be responsive to actions performed by software running on the local device  110 . Examples of data modification  310  include rotating an image, resizing an image, cropping an image, editing an electronic document, and a virtually unlimited variety of other actions that alter characteristics or contents of the shared file  235 . Metadata describing the data modifications are then generated  320  on the local device. The generated  320  metadata identify the modified file and describe the data modifications or otherwise enable another device to recreate the modifications made to the data file  235 . 
     In an embodiment, the metadata  210  comprise a description of the differences between the original shared file  235  and the modified shared file  235 . For example, the metadata may describe the areas of an image file that have been altered or the sections of an electronic document that have been edited, as well as what modifications were made. In another embodiment, the metadata comprise instructions and arguments specifying how the shared file  235  should be updated. For example, the metadata can comprise an instruction to rotate an image file a specified amount or to remove a specified number of words from a portion of an electronic document, or any instruction the application  210  can use to modify data. 
     The generated metadata are then transmitted  330  to the remote server  120 . Because the metadata describe the modifications to the shared file  235 , the remote server  120  uses the metadata to update  340  the copy of the shared file  235  stored on the remote server  120 . This causes the same modifications to be made to the copy of the shared file  235  on the local device  110  and the copy of the shared file  235  on the remote server  120 , synchronizing the contents of the shared file  235  between devices. 
     In an embodiment, an application  210  on the remote server  120  performs operations on the shared file  235  corresponding to the contents of the metadata once the remote server  120  receives the metadata. Alternatively, the remote server  120  may store the metadata in a metadata store  240 , which the application  210  running on the remote device  115  then accesses to alter the shared file  235 . Transmitting  330  the metadata describing the modifications  310  conserves network resources by allowing the remote server  120  to locally modify the shared file  235  the remote server  120  rather than requiring transmission of the modified  310  shared file  235  to the remote server  120 . 
     In an embodiment, the local device  110  compares the size of the metadata to the size of the shared file  235 , and transmits  330  the smaller of the two to the remote server  120 . In this way, the metadata is transmitted if it is not larger than the modified shared file  235  or the modified shared file  235  is transmitted if it is smaller than the metadata. This comparison may further conserve network resources by transmitting the smallest amount of information necessary to communicate changes in the shared file  235  to another device. 
     After the remote server  120  updates  340  the data file, and when the remote device  115  requests  350  the shared data file  235 , the remote server  120  transmits  360  the updated shared file  235  to the remote device  115 . Changing the copy of the shared file  235  on the remote server  120  allows the changes to the shared file  235  to be propagated to other devices, such as remote device  115 , when they request  350  the shared file  235  from the remote server  120 . This allows the remote server  120  to update  340  shared files  235  centrally, rather than requiring each of the individual remote devices  115  to modify locally stored copies of the shared file  235 . Additionally, using the remote server  120  to update  340  shared files  235  may increase the type and extent of data modifications  310  possible by using the computing resources of the remote server  120 , which are likely to exceed the computing resources of local device  110  or remote device  115 . 
     In an alternative embodiment, the local device  110  transmits  330  the metadata describing the changes to the shared file  235  to the remote device  115 . The remote device  115  then uses the metadata to update  340  a copy of the shared file  235  stored on the remote device. This allows each remote device  115  to synchronize the contents of the shared file  235  by locally modifying copies of the shared file  235 . In this embodiment, the remote devices  115  also perform conflict resolution to determine the order in which to use the metadata to accurately update  340  the shared file  235 . Conflict resolution allows the remote devices  115  to determine what changes to the local copy of the shared file  235  should be made first, or what changes to the local copy of the shared file  235  have priority over other changes. The remote devices  115  may implement various conflict resolution schemes, such as recording timestamps of changes made, assigning priority to changes from certain devices, or any other suitable conflict resolution scheme. 
       FIG. 4  illustrates an example use of metadata to represent modifications made to a shared data file  325 , according to an embodiment. In the example of  FIG. 4 , image files are stored on the local device  110 . The application  210  allows a user to access and modify the stored image files. 
     Initially, image  410  is accessed by the application  210  and presented to the user. The original image  410  can then be changed by the user to produce modified image  415 . For example, modified image  415  can comprise the original image  410  rotated by a specified amount. The application  210  can record and store the actions taken by the user to generate modified image  415  as metadata  420 . For example, metadata  420  describes the user action  422 , the name  424  of the original image  410 , and an argument  426  modifying the user action  422 . In the example of  FIG. 4 , metadata  420  indicates that the user has rotated image — 1 by X degrees to create the modified image  415 . 
     Because metadata  420  is a textual string, in one embodiment, transmission of metadata  420  requires less bandwidth on the network  130  than would transmission of the modified image  415  in its entirety. Upon receiving the metadata  420 , an application  210  on the remote server  120  may modify the locally stored copy of the shared file  325  to reflect the alterations described by metadata  420 . Thus, the metadata  420  enables an application  210  on the local device  110  and an application on the remote server  120  to perform the same modifications to copies of the shared file  325  stored on each device, synchronizing the shared file  325  copy on each device. 
     Alternatively, the local device  110  may transmit the metadata  420  to a remote device  115  (directly, or via the remote server  120 ), which modifies a local copy of the shared file  325  on the remote device based on the contents of the metadata. This allows remote devices  115  to synchronize locally stored copies of image  410  by each changing locally stored copies of image  410 . Because the remote device  115  may receive metadata  420  from a plurality of other devices at different times, the remote device  115  may also determine the appropriate order in which to apply the received metadata to modify the image  410  accurately. 
     Summary 
     Some portions of above description describe the embodiments of the invention in terms of algorithms and symbolic representations of operations on information. These algorithmic descriptions and representations are commonly used by those skilled in the data processing arts to convey the substance of their work effectively to others skilled in the art. These operations, while described functionally, computationally, or logically, are understood to be implemented by computer programs or equivalent electrical circuits, microcode, or the like. Furthermore, it has also proven convenient at times, to refer to these arrangements of operations as modules, without loss of generality. The described operations and their associated modules may be embodied in software, firmware, hardware, or any combinations thereof. 
     In addition, the terms used to describe various quantities, data values, and computations are understood to be associated with the appropriate physical quantities and are merely convenient labels applied to these quantities. Unless specifically stated otherwise as apparent from the following discussion, it is appreciated that throughout the description, discussions utilizing terms such as “processing” or “computing” or “calculating” or “determining” or the like, refer to the action and processes of a computer system or similar electronic computing device, which manipulates and transforms data represented as physical (electronic) quantities within the computer system memories or registers or other such information storage, transmission, or display devices. 
     Embodiments of the invention may also relate to an apparatus for performing the operations herein. This apparatus may be specially constructed for the required purposes, or it may comprise a general-purpose computing device selectively activated or reconfigured by a computer program stored in the computer. Such a computer program may be stored in a computer readable storage medium, such as, but not limited to, any type of disk including floppy disks, optical disks, CD-ROMs, magnetic-optical disks, read-only memory (ROM), random access memory (RAM), EPROMs, EEPROMs, magnetic or optical cards, application specific integrated circuits (ASICs), or any type of media suitable for storing electronic instructions, and each coupled to a computer system bus. Furthermore, the computers referred to in the specification may include a single processor or may be architectures employing multiple processor designs for increased computing capability. 
     Embodiments of the invention may also relate to a computer data signal embodied in a carrier wave, where the computer data signal includes any embodiment of a computer program product or other data combination described herein. The computer data signal is a product that is presented in a tangible medium and modulated or otherwise encoded in a carrier wave transmitted according to any suitable transmission method. 
     The algorithms and displays presented herein are not inherently related to any particular computer or other apparatus. Various general-purpose systems may also be used with programs in accordance with the teachings herein, or it may prove convenient to construct more specialized apparatus to perform the required method steps. The required structure for a variety of these systems will appear from the description above. In addition, embodiments of the invention are not described with reference to any particular programming language. It is appreciated that a variety of programming languages may be used to implement various embodiments of the invention as described herein, and any references to specific languages are provided for disclosure of enablement and best mode of embodiments of the invention. 
     Finally, it should be noted that the language used in the specification has been principally selected for readability and instructional purposes, and it may not have been selected to delineate or circumscribe the inventive subject matter. Accordingly, the disclosure of the embodiments of the invention is intended to be illustrative, but not limiting, of the scope of the invention, which is set forth in the following claims.