Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-12-29
2002-04-23
Coby, Frantz (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06377957
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 an access to the data at a client. In response to this access, the system determines if the client contains a copy of the data. If so, the system sends a request to a server for an update to the copy. The server receives the request and determines 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. These differences are used 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. Next, the update is sent to the client where it is applied to the copy of the data to produce an updated copy of the data. Finally, the original access is allowed to proceed on the 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 and node splitting 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
Wiederhold et al., Consistency Control of Replicated Data in Federated Databases, Nov. 1990, IEEE, pp. 130-132.*
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.*
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.
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-2912128