Description
UPDATING CACHE WITH SPATIAL DATA
TECHNICAL FIELD
[0001] The present invention relates generally to caching spatial data, and more specifically to using a spatial geometry which is a currency shape to indicate the currency of spatial data in a cache and how the cache and the currency shape should be updated.
BACKGROUND
[0002] The enormous sizes of spatial data sets adversely affect their storage, transmission, access, etc. A cache may used to minimize the adverse effects but the data in the cache becomes stale and outdated in between client sessions or connections to a source of spatial data. Other approaches use only timestamps without taking spatial information into consideration. Currently, cached data is deleted at the end of a session because it will be stale and out of date when the next session is initiated. This deletion of cached data loses any benefit of caching data in previous sessions.
[0003] Current practices include using versions which indicate the state of the database system at a specific time. A source of spatial data may use three tables. An Original Table representing the original database, which is version 0. An Add Table of all additions to the database and the version corresponding to each addition. A Deletion Table of all deletions to the database and the versions corresponding to each deletion. In addition the client stores the version of the state that represents the client cache. Each time a client connects to the server, the server compares the version of the client cache and the versions of all the information in the tables being stored and updates the client cache accordingly. This results in large and constantly growing Add and Deletion Tables, tracking client version numbers and a great deal of processing to update the client cache at the beginning of each session. [0004] Some other attempts to minimize the impact of the size of spatial data sets access and cache much more data than is needed. None of these attempts are satisfactory.
[0005] A better way is needed to minimize processing time and storage and bandwidth requirements, and to maximize speed and timeliness, in handling spatial data sets and thereby lessen problems caused by the size of spatial data sets.
BRIEF DESCRIPTION OF THE DRAWINGS
[0006] FIG. 1 is a schematic showing the general components of a computer-based system to update spatial data in accordance with an embodiment of the present invention;
[0007] FIG. 2 is a chart of steps to update spatial data during an initial connection in accordance with an embodiment of the invention; and
[0008] FIG. 3 is a chart of steps to maintain currency of spatial data during subsequent connections in accordance with an embodiment of the invention.
DETAILED DESCRIPTION
[0009] FIG. 1 is an illustrative schematic of a computer-based system 100 for updating and maintaining currency of spatial data in a cache. The computer-based system 100 includes a server 110 which functions as a source of spatial data. Other embodiments may have more than one server 110. In this embodiment, the server 110 keeps the spatial data in a Geographic Information System (GIS) database 112. GIS databases are well known, and basically provide a framework for working with the spatial components and spatially related components of spatial data, both of which may be related to a feature. The spatial component is generally a geometry or shape of a feature, and the spatially related component may contain attributes that pertain to the geometries of the features, all of which are stored in layer tables. Data stored in the GIS database 112 are stored on computer readable media. There may be more than one GIS database 112 on the server 110. The server 110 has, among other things, software 114 and memory 116. The software 114 may be used by the server 110 to manipulate the GIS database, perform communication functions, or any other functions required by the server 110.
[0010] A transmission medium 130 enables server 110 to communicate with, for example, a client 150. The transmission medium 130 may include the Internet, a wide area network, an intranet, wireless media, fiber-optic media, satellites, direct hardwire connections, a computer bus, etc. Other embodiments may include more than one client 150. The client 150 contains a cache 152 which, among other things, stores spatial data. In alternate embodiments the cache 152 may reside on the server 110 or outside the client 150 and the server 110. As with the spatial data stored in the GIS database 112, the spatial data in cache 152 consists of the spatial component and spatially related component of spatial data, both of which may be related to a feature. The spatial component is generally a geometry or shape of a feature, and the spatially related component may contain attributes that may pertain to the geometries of the features, all of which are stored in layer tables. The client 150 also has software 154, which may be used to maintain the cache 152, perform communications or other functions required by the client 150. The client also has memory 156.
[0011] The relationship between the server 110, a transmission medium 130, and the client 150 may be embodied in various ways. The server 110 and the GIS database 112 are basically a source of GIS data. The client 150 uses medium 130 and the server 110 to access spatial data from the GIS database 112. The relationship may range from the server 110 being external to the client 150 with the transmission medium 130 being the Internet to where all components are internal to a single computer system or switch with the transmission medium 130 being a computer bus.
[0012] FIG. 2 illustrates steps of an example process 200 wherein the FIG. 1 client
150 initiates a first session 210 between the client 150 and the server 110. The cache 152 has not yet been created. The client 150 and the server 110, among other things, perform a series of registration and notification procedures. The client 150 registers for the types of spatial data it will require and for which it wishes to be notified. These types of data may include full geometry, derived geometry, unions, etc. The client 150 may also specify a filter, which may specify the types of geometries or attributes of which it wishes to be notified. To provide a good understanding and for illustrative purposes only, this embodiment is described with just one client 150, one server 110, and one GIS database 112. Other embodiments may include more than one client 150, more than one server 110, and/or more than one GIS database 112 in any combination.
[0013] The data in the GIS database 112 is stored primarily in layer tables. The layer tables correspond to organizational types such as roads. There may be numerous road layer tables, where each road layer table corresponds to road spatial data that are visible at a particular scale. The scale corresponds to a zoom level or an elevation from which observations are made, as is well known in the art. The layer tables in the GIS database 112 contain numerous columns or fields for each record or row. The fields described here are not meant to limit the types of fields that may be present in the layer tables. One field is an ID number, which is unique to the table and may be used to identify a record for a specific feature in the table. Another field is the feature geometry. There may be any number of attribute fields which contain information related to the feature. There is also a timestamp which indicates the last time that data for this record was updated on the server. The timestamp may be of any type to uniquely identify a specific time, such as a year/month/day/hour/minute/second/fraction with suitable precision. The layer tables also contain metadata among which may be the scale for the layer table, e.g., the minimum and maximum visible scales for this particular layer table.
[0014] Once registration and notification procedures are completed, the cache 152 is first created. Layer tables are created in the cache 152 that correspond to the registration and notification procedures. The layer tables in the cache 152 are structured the same way as the layer tables in the GIS database 112, except that the layer tables in the cache 152 have no records containing data. The layer tables in the cache 152 have similar metadata as is in the layer tables in GIS database 112.
[0015] A session table (not shown) is also created in the cache. Each record or row in the session table corresponds to a layer table. The fields in the session table may include an ID number, a Layer Currency Shape (which during a session is identified as an LCS), the name of a layer table, a source ID denoting the server 110 and the GIS database 112 containing the particular layer table, the session start which is the start time of the session, and the last update time at which the LCS was changed during the session. The ID number is unique for each row of the session table. The LCS is a geometry that is used to indicate currency, during a client 150 server 110 session, of the data for the particular layer table in cache 152. The LCS indicates geographic areas that have been visited or processed during a session. If an area is visited or processed during a session, the area is known to be accurate for the session and is included in the LCS. The LCS is initialized with a null geometry. The name of the layer table for each row corresponds to the layer tables that were identified during the registration and notification procedures. The source ID for each layer table is entered. The session start is entered for each record of the current session. The session start and the last update are used for various synchronization procedures which will be discussed below. LCS will be used to describe the currency shape for the current session between the client 150 and the server 110.
[0016] Once the empty layer tables in cache 152 are created, the session table is created and an Area of Interest (AOI) 212 is specified by the client 150. The AOI 212 is a geometry, which may be a bounding box as is well-known in the art. A bounding box is a rectangle which is demarcated by its minimum and maximum coordinates in the x and y directions. Since the x and y coordinates of the bounding box may be latitude and longitude or coordinated to a local coordinate system, the x and y coordinates allow the geographic area of the AOI 212 to be known. In addition, the scale at which the features of the AOI 212 may be visible may be determined by knowing the geographic extent of the AOI 212. This allows selection of the layer tables that correspond to the scale of the AOI 212. Control is then passed to step 214.
[0017] Step 214 tests the geometry of the AOI 212 against the geometry of the LCS in the session table for each visible layer. The visible layers are those layers which would be visible for the AOI 212. The visible layers correspond to the scale for the AOI 212. A determination is made to find out what parts of the AOI 212 are, and what parts are not, already stored in cache. This is done using set mathematics where the geometry of the LCS is subtracted from the geometry of the AOI. If the result of the subtraction is not greater than zero then the AOI 212 is completely contained in the LCS and the cache has current data for this visible layer of the AOI 212, indicating that the data for the AOI 212 was loaded during the current session. Control is then passed to step 218 which waits for a new AOI to be specified. [0018] If the result of the subtraction is greater than zero then there are parts of the AOI 212 that are outside the LCS and not stored in cache 152. Then the cache 152 must be updated. This process may be represented by determining whether (AOI 212 geometry - LCS geometry > 0). If the result is greater than zero then control passes to step 216.
[0019] Step 216 fetches data corresponding to the geometry defined by (AOI 212 geometry - LCS geometry) from the server 110, using the server database indicator in the session table that corresponds to the layer to determine which server 110 and which GIS database 112 contain the layer table. Spatial queries are used to compare the geometry of the AOI 212 with the geometry of the individual feature records in the layer table in the GIS database 112. Records in the GIS database 112, whose geometries intersect the geometry of the AOI 212, are fetched and loaded into the layer table in cache 152. The LCS in the session table for the layer is changed to indicate the addition of this data. The geometries of records stored in cache 152 are added to the geometry of the LCS. In addition the last update is updated to the actual time that the data was stored in cache and the LCS was changed.
[0020] Steps 214 and 216 are repeated for each visible layer of the AOI 212. Once all visible layers of the AOI 212 have been processed control is passed to step 218 which waits for a new AOI of step 218 to be specified. Control passes to step 214 and the process continues as described above using the newly specified AOI of step 218 the same way the AOI 212 was used.
[0021] When the session is terminated and the client 150 disconnects from the server 110 all layer tables in the cache 152 remain intact. Also, the session table remains intact and the last update time for all the records of the current session is changed to the time the current session ended.
[0022] FIG. 3 illustrates steps of an example process 300 wherein the FIG. 1 client 150 initiates a session 310. The cache 152 has already been created and a session table exists. The currency shape in the session table, which indicates the currency of a layer table for the previous session, is now identified as the Previous Layer Currency Shape (PLCS) to distinguish previous session shape geometries from those of a current session (LCS). The client 150 and the server 110 perform the same registration and notification procedures as described above for step 210 of FIG. 2. Layer tables in the GIS database 112 that correspond to the registration and notification procedures which are not yet in the cache 152 are created in the cache 152 as described above when the cache 152 was initially created in step 210 of FIG. 2. Records in the session table are added for the current session as described in step 210 of FIG. 2. The records for the current session have different session start times which distinguish them from those for the previous session.
[0023] In step 312 an AOI is specified as described above in step 212 of FIG. 2. Testing of each visible layer of the AOI 312 against the cache 152 begins with step 314. Various procedures will be executed on the AOI 312 and a resultant, named an AOI remainder, will be used in further tests. In step 314 the AOI 312 is tested against the LCS of the current session. Any portion of the AOI that intersects with the LCS represents data in cache 152 that was loaded during the current session and is good data. Any portion of the AOI that is outside the LCS needs to be tested further. The geometry of the LCS is subtracted from the geometry of the AOI 312 and the result is the AOI remainder. If the AOI remainder is not greater than zero, then all of the AOI 312 intersects the LCS and the cache is up-to-date, because all data corresponding to the AOI 312 was loaded during the current session, and nothing more need be done. Control then passes to step 330, which waits for a new AOI to be specified. If the AOI remainder is greater than zero, then some of the AOI 312 remainder does not intersect the LCS. Data for the geometry represented by the AOI remainder was not loaded during this current session and further testing is required.
[0024] In step 316 the AOI remainder is tested against the PLCS of the previous session to determine what parts of the AOI remainder were not loaded from the previous session and have never been loaded into cache 152. The PLCS is subtracted from the AOI remainder and if the result is greater than zero then part of the AOI remainder, the result, was not loaded into cache 152 and control moves to step 318, which fetches the geometry defined by (AOI remainder - PLCS). The data is stored in a layer table in cache 152 and the LCS of the session table is updated, as described in step 216 of FIG. 2. Control is then passed to step 320. If the result is less than or equal to zero, then the AOI remainder intersects with the PLCS, indicating that the AOI remainder was loaded into cache 152 during the previous session. Control is then passed directly to step 320.
[0025] In step 320 the AOI remainder is tested to determine if any part of the AOI remainder has been loaded into cache 152 prior to the current session. This is done by determining if any part of the AOI remainder intersects with the PLCS. If the intersection is greater than zero, then the parts of the AOI remainder represented by the intersection were loaded into cache 152 prior to the current session and control is passed to step 322. If the intersection is not greater than zero, then all of the AOI remainder was loaded to cache 152 by step 318 and control is passed to step 330, which waits for a new AOI to be specified as described in step 218 of FIG. 2.
[0026] In step 322 the geometry defined by the intersection of the AOI remainder and the PLCS is used to query the server 110 for the ID number and timestamp of each geometry corresponding to the intersection in both the layer table of the GIS database 112 and the layer table in cache 152. The ID numbers and timestamps are used to determine whether the data in cache 152 is current, and what steps to take. Control is then passed to step 324.
[0027] Step 324 determines whether records in the cache 152 have been deleted from the layer table in the GIS database 112 since the previous session. If records in the cache 152 have ED numbers that do not appear in the layer table on the GIS database 112 then these records have been deleted from the GIS database 112 and are deleted from the cache. The LCS in the session table is changed by adding the geometries of the deleted records from the geometry of the LCS. The PLCS for the previous session is changed by subtracting the geometries of the deleted records from the geometry of the PLCS. Control is then passed to step 326.
[0028] Step 326 determines whether any records have been added to the layer table on the GIS database 112 since the previous session. If there are any records in the layer table of the GIS database 112 whose ID numbers do not appear in the layer table in the cache 152 then the records corresponding to these ID numbers are fetched from the layer table in the GIS database 112. The records are stored in the layer table in cache 152 and the LCS is changed by adding the geometries of the newly stored records to the LCS. The PLCS for the previous session is changed by subtracting the geometries of the newly added records from the geometry of the PLCS. Control is then passed to step 328.
[0029] Step 328 determines whether any records have been updated on the GIS database 112 since the previous session. These records are identified when the ID numbers exist both in the layer table in the GIS database 112 and in a layer table in cache 152. Timestamps are compared from the layer table in the GIS database 112 and the layer table in cache 152. If the timestamp for the record in the layer table in the GIS database 112 is more recent than the timestamp for the record of the layer table in cache 152, the record has been updated and is fetched from the layer table in the GIS database 112. The old record in the layer table in the cache 152 is deleted and the geometry of this record is subtracted from the geometry of the PLCS. The new record is then added to the layer table in cache 152 and the geometry of the new record is added to the geometry of the LCS and the last update time is changed accordingly for the LCS. Control is then passed to step 330. If no records have been updated then control is passed to directly to step 330 which waits for a new AOI to be specified without making any changes to cache or session table.
[0030] Step 330 functions the same as step 218 of FIG. 2. Step 330 waits for a new AOI to be specified and passes control to step 314 and the process repeats as described above with the new AOI from step 330 being processed the same way that the AOI from step 312 was processed.
[0031] The session is eventually terminated and the client 150 disconnects from the server 110. After termination, all layer tables in the cache 152 remain intact. The records for the current session in the session table have the last update time changed to be the time the session ended for all the records of the current session. The times for all the PLCS records are unchanged.
[0032] At this point, after two client 150 server 110 sessions, the session table has records for both of the sessions. Because the PLCS is also changed to reflect changes in cache, the various PLCS shapes will not intersect. Therefore, in additional sessions, when checking the LCS against the numerous PLCS records only one PLCS record may match. Therefore the LCS is checked against PLCS records for the appropriate layer name. If a PLCS matches then that PLCS is used as described above. In addition, a PLCS is deleted when it reverts back to the null geometry.
[0033] The foregoing detailed description has described the invention with reference to specific embodiments thereof. An embodiment is described primarily in reference to feature data being stored in the cache 152. This feature data may be used by the client 150 to render images. This feature data may be used by the client 150 to prerender tiles into the cache 152 from which the prerendered tiles may be sent to another client. A tile, as is well known in the art, may be thought of as an internal subsetting of a spatial dataset (commonly raster) into a manageable rectangular set, such as rows and columns of pixels, which is typically used to process, analyze, or visualize a large raster dataset by processing a smaller subset at a time. Another embodiment may store prerendered tiles in the GIS database 112 and in the cache 152. It will, however, be evident to a skilled artisan that various modifications and changes can be made thereto without departing from the broader spirit and scope of the present invention as set forth in the appended claims. Aspects of the disclosure described herein may be stored or distributed on computer-readable media, including magnetic and optically readable and removable computer disks, as well as distributed electronically over the Internet or over other networks, including wireless networks. Data structures and transmission of data particular to aspects of the disclosure are also intended to be encompassed within the scope of the invention. Further, principles of the invention may be beneficially applied to other types of spatial data. The specification and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense.