Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-12-29
2001-10-30
Black, Thomas (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06311187
ABSTRACT:
BACKGROUND
The present invention relates to distributed computing systems and databases. More particularly, the present invention relates to a method and an apparatus that facilitates detecting changes in hierarchically structured data and producing corresponding updates for remote copies of the hierarchically structured data.
The advent of the Internet has led to the development of web browsers that allow a user to navigate through inter-linked pages of textual data and graphical images distributed across geographically distributed web servers. Unfortunately, as the Internet becomes increasingly popular, the Internet often experiences so much use that accesses from web browsers to web servers often slow to a crawl.
In order to alleviate this problem, a copy of a portion of a web document from a web server (document server) can be cached on a client computer system, or alternatively, on an intermediate proxy server, so that an access to the portion of the document does not have to travel all the way back to the document server. Instead, the access can be serviced from a cached copy of the portion of the document located on the local computer system or on the proxy server.
However, if the data on the document server is frequently updated, these updates must propagate to the cached copies on proxy servers and client computer systems. Such updates are presently propagated by simply sending a new copy of the data to the proxy servers and client computer systems. However, this technique is often inefficient because most of the data in the new copy is typically the same as the data in the cached copy. In this case, it would be more efficient to simply send changes to the data instead of sending a complete copy of the data.
This is particularly true when the changes to the data involve simple manipulations in hierarchically structured data. Hierarchically structured data typically includes a collection of nodes containing data in a number of forms including textual data, database records, graphical data, and audio data. These nodes are typically inter-linked by pointers (or some other type of linkage) into a hierarchical structure, which has nodes that are subordinate to other nodes, such as a tree—although other types of linkages are possible.
Manipulations of hierarchically structured data may take the form of operations on nodes, such as node insertions, node deletions or node movements. Although such operations can be succinctly stated and easily performed, there presently exists no mechanism to transmit such operations to update copies of the hierarchically structured data. Instead, existing systems first apply the operations to the data, and then transmit the data across the network to update copies of the data on local machines and proxy servers.
SUMMARY
One embodiment of the present invention provides a system that efficiently propagates changes in hierarchically organized data to remotely cached copies of the data. The system operates by receiving changes to the data located on the server, and applying the changes to the data on the server. These changes are propagated to remotely cached copies of the data in response to an event on the server and independently of the client, by (1) determining differences between the current version of the data at the server and an older copy of the data at the client, which the server has stored locally; (2) using the differences to construct an update for the copy of the data, which may include node insertion and node deletion operations for hierarchically organized nodes in the data; and (3) sending the update to the client where the update is applied to the copy of the data to produce an updated copy of the data. According to one aspect of the present invention, the act of determining differences, and the act of using the differences to construct the update both take place during a single pass through the data. According to another aspect of the present invention, the update for the copy of the data may include node copy, node move, node collapse, node split, node swap and node update operations.
REFERENCES:
patent: 5068804 (1991-11-01), watanabe et al.
patent: 5430869 (1995-07-01), ishak et al.
patent: 5475837 (1995-12-01), ishak et al.
patent: 5916299 (1999-06-01), poppen
patent: 6192368 (2001-02-01), Gerard et al.
patent: WO 97/34240 (1997-09-01), None
Oh et al., An Increment Update Propagation Scheme for a Cooperative Model, Sep., 1996, IEEE, pp. 353-362.*
Mostardi et al., Achieving Consistency of replicated Copies with the Relay Race Method, Apr. 1993, IEEE, pp. 232-235.*
Alonso et al., Managing Replicated Copies in Very Large Distributed Systems, Nov. 1990, IEEE, pp. 39-42.*
Yamashita et al., View Divergence Control of Replicated Data using Update Delay Estimation, Oct. 1999, pp. 102-111.*
Wiederhold et al., Consistency Control of Replicated Data in Federated Databases, Nov. 1990, IEEE, pp. 130-132.*
Introducing Castanet. Castanet Tuner User's Guide. Available at URL http//www.marimba.com., no date.
Delivering and Updating Applications with the Castanet198 Infrastructure Suite. Available at URL http://www.marimba.com/three/infrastructure.html., no date.
Publication entitled “Data Caching with Incremental Update Propagation in Mobile Computing Environments”, by Hyunsik Chung, et al. Yeungnam University, XP-002157518, Jan. 17, 2001.
Publication entitled “Meaningful Change Detection in Structured Data”, by Sudarshan S. Chawathe, et al. ,Stanford University, XP-002157519, May 13, 1997, pp. 26-37.
Publication entitled “A Graphical Environment for Change Detection in Structured Documents”, by George S. Chang, et al., New Jersey Institute of Technology, XP-002157517, 1997, pp. 536-540.
Publication entitled “Simple Fast Algorithms for the Editing Distance Between Trees and Related Problems”, by Kaizhong Zhang, et al., XP-000978540, Dec., 1989, pp. 1245-1262.
Publication entitled “HTTP: Delta-Encoding Notes”, XP-002157520, Jan. 17, 1997, pp. 1-7.
Publication entitled “Web Prefetching Between Low-Bandwidth Clients and Proxies: Potential and Performance”, by Li Fan, et al., University of Wisconsin-Madison, XP-00215751?, Jan. 5, 1999, pp. 178-187.
Publication entitled “Web Express: A System for Optimizing Web Browsing in a Wireless Environment”, by Barron C. Housel Ph.d, et al. ,IBM Corporation, XP-00215754, 1997, pp. 108-116.
Publication entitled “Optimistic Deltas for WWW Latency Reduction”, by Gaurav Banga, et al., Rice University, XP-000874445, 1997, pp. 289-303.
Black Thomas
Coby Frantz
Park Vaughan & Fleming LLP
Sun Microsystems Inc.
LandOfFree
Propogating updates efficiently in hierarchically structured... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Propogating updates efficiently in hierarchically structured..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Propogating updates efficiently in hierarchically structured... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2609642