US6789255B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Determining update availability via set intersection over a sub-optimal pathway
Assignee: Microsoft Technology Licensing LLC
•
Filing: 2000-09-26
•
Granted: 2004-09-07
•
Expires: 2020-09-26
Abstract
Abstract A low bandwidth link can be used optimally for software updates, by successively transferring more information about the updates only as the likelihood of an applicable update successively increases. A many-to-one mapping function (e.g. a hash function) is applied to update identifiers on a server to generate a table of single bit entries corresponding to the updates. At a client, the same mapping function is applied to program identifiers to determine whether the server has a potential update. If a potential update is noted, a second transmission is requested for conveying additional data from the server by which hash collisions can be identified. A third transmission from the server is received conveying the actual update only after the availability of an actual update (versus a hash collision) is confirmed. The same arrangement can be employed in reverse.
Inventors
- 👤 Raymond D. Pedrizetti
- 👤 Scott D. Quinn
- 👤 Timothy W. Bragg
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 14:41
CPC Classifications
G; G06; G06F; G06F8/00; G06F8/60; G06F8/65
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
115 words
A computer-readable medium having computer-executable instructions for indicating resources for which at least one of a plurality of updates are available by performing the following: with a hash function, generating a table having a plurality of single bit entries, wherein at least one of the plurality of the single bit entries is set to inconclusively indicate the availability of at least one of the plurality of the updates to the resources having unique identifiers, wherein a plurality of the unique identifiers are associated with a single bit entry via the hash function; and transferring to a client computer the table inconclusively indicating the availability of the at least one of the plurality of the updates.
Claim 2
Dependent Claim
115 words
A computer-readable medium having computer-executable instructions for indicating resources for which at least one of a plurality of updates are available by performing the following: with a hash function, generating a table having a plurality of single bit entries, wherein at least one of the plurality of the single bit entries is set to inconclusively indicate the availability of at least one of the plurality of the updates to the resources having unique identifiers, wherein a plurality of the unique identifiers are associated with a single bit entry via the hash function; and transferring to a client computer the table inconclusively indicating the availability of the at least one of the plurality of the updates.
Claim 3
Dependent Claim
79 words
The computer-readable medium of claim 1 further comprising computer-readable instructions for performing the following: consulting the table to inconclusively determine that the at least one of the plurality of the updates is available by detecting that the at least one of the plurality of the single bit entries is set; and responsive to inconclusively determining that the at least one of the plurality of the updates is available, sending a list of resources associated with the single bit entry.
Claim 4
Dependent Claim
74 words
The computer-readable medium of claim 2 further comprising computer-readable instructions for performing the following: consulting the list of resources associated with the single bit entry to conclusively determine that the at least one of the plurality of the updates is available; and responsive to conclusively determining that the at least one of the plurality of the updates is available, transmitting the at least one of the plurality of the updates to the client computer.
Claim 5
Dependent Claim
12 words
The method of claim 1 wherein the table comprises a sparse table.
Claim 6
Independent Claim
164 words
A method for determining an update is available for an item installed at a client computer, the method comprising: determining a unique identifier for the item; assembling a first data structure by applying a many-to-one mapping function to the unique identifier for the item, wherein the first data structure inconclusively indicates that the update is available for the item; sending the first data structure in a first transmission; from the first data structure, determining the update may be available for the item installed at the client computer; responsive to determining the update may be available for the item installed at the client computer, in a second transmission, sending a second data structure comprising confirmation data for the item installed at the client computer, wherein the second data structure conclusively indicates that the update is available for the item; and via the confirmation data for the item installed at the client computer, confirming the update is available for the item installed at the client computer.
Claim 7
Independent Claim
164 words
A method for determining an update is available for an item installed at a client computer, the method comprising: determining a unique identifier for the item; assembling a first data structure by applying a many-to-one mapping function to the unique identifier for the item, wherein the first data structure inconclusively indicates that the update is available for the item; sending the first data structure in a first transmission; from the first data structure, determining the update may be available for the item installed at the client computer; responsive to determining the update may be available for the item installed at the client computer, in a second transmission, sending a second data structure comprising confirmation data for the item installed at the client computer, wherein the second data structure conclusively indicates that the update is available for the item; and via the confirmation data for the item installed at the client computer, confirming the update is available for the item installed at the client computer.
Claim 8
Dependent Claim
11 words
The method of claim 5 wherein the item is a file.
Claim 9
Dependent Claim
12 words
The method of claim 5 wherein the item is a hardware device.
Claim 10
Dependent Claim
57 words
The method of claim 5 wherein the first data structure comprises a bitmap inconclusively indicating the presence of the update via a bit, wherein the bit is associated with the unique identifier and at least one other unique reference for another item, wherein location of the bit within the bitmap is determined by the one-to-many mapping function.
Claim 11
Dependent Claim
19 words
The method of claim 5 wherein the confirmation data comprises a list of files for which updates are available.
Claim 12
Dependent Claim
21 words
The method of claim 5 wherein the confirmation data comprises a list of files and devices for which updates are available.
Claim 13
Dependent Claim
16 words
The method of claim 5 wherein the confirmation data comprises a version number for the item.
Claim 14
Dependent Claim
31 words
The method of claim 5 further comprising: responsive to confirming an update is available for the item installed at the client computer, transferring the update for the item to the client.
Claim 15
Dependent Claim
40 words
The method of claim 5 further comprising: identifying plural items on the client computer for which a corresponding update is available; transferring plural updates from the server to the client computer; and installing said plural updates on the client computer.
Claim 16
Dependent Claim
28 words
The method of claim 5 wherein the assembling comprises generating a hash code for the item, wherein the same hash code may be generated for two different items.
Claim 17
Dependent Claim
43 words
The method of claim 14 further comprising: responsive to confirming the update is available for the item installed at the client computer, transferring the update for the item to the client; and determining whether a hash conflict has occurred before transferring the update.
Claim 18
Dependent Claim
37 words
The method of claim 5 further comprising: transferring the confirmation data from a server computer to the client computer, wherein the confirmation data specifies the name of the item for which the server computer has the update.
Claim 19
Dependent Claim
30 words
The method of claim 16 wherein the confirmation data further specifies a file by which the automatic transfer and installation of the update on the client computer can be invoked.
Claim 20
Dependent Claim
26 words
The method of claim 16 wherein the administrative data further includes an override file, said override file operative to provide a reject indication for the update.
Claim 21
Independent Claim
168 words
A method for determining software update availability for a client computer by sending software update availability information over a communications pathway, the method comprising: with a hashing function, hashing unique identifiers of available software updates to non-unique identifiers to generate a data structure inconclusively indicating the availability of at least one software update; sending the data structure over the communications pathway during a first transmission; after the first transmission, comparing the data structure to a list of upgrade candidates for the client computer to determine an update may be available for an upgrade candidate in the list, wherein the update is identified by a non-unique identifier associated with the update via the hash function; responsive to affirmatively determining an update may be available, during a second transmission over the communications pathway, sending a list of entries for a plurality of software updates associated with the non-unique identifier via the hash function; and consulting the entries to conclusively determine if a software update is available for the upgrade candidate.
Claim 22
Independent Claim
168 words
A method for determining software update availability for a client computer by sending software update availability information over a communications pathway, the method comprising: with a hashing function, hashing unique identifiers of available software updates to non-unique identifiers to generate a data structure inconclusively indicating the availability of at least one software update; sending the data structure over the communications pathway during a first transmission; after the first transmission, comparing the data structure to a list of upgrade candidates for the client computer to determine an update may be available for an upgrade candidate in the list, wherein the update is identified by a non-unique identifier associated with the update via the hash function; responsive to affirmatively determining an update may be available, during a second transmission over the communications pathway, sending a list of entries for a plurality of software updates associated with the non-unique identifier via the hash function; and consulting the entries to conclusively determine if a software update is available for the upgrade candidate.
Claim 23
Dependent Claim
65 words
The method of claim 19 further comprising: over the communications pathway, before sending the software update available for the upgrade candidate, sending an executable override file for the software update available for the upgrade candidate; and before sending the software update available for the upgrade candidate, executing the override file to determine whether to reject the software update based on configuration of the client computer.
Claim 24
Dependent Claim
34 words
The method of claim 19 further comprising: responsive to conclusively determining that the software update is available for the upgrade candidate, in a third transmission, sending the software update available for the upgrade candidate.
References Cited (Backward Citations)
US4999806A
Cited
US5339430A
Cited
US6047129A
Cited
US5586304A
Cited
US5701463A
Cited
US5832275A
Cited
US5742829A
Cited
US5701491A
Cited
US6049671A
Cited
US5881236A
Cited
US5930513A
Cited
US5752042A
Cited
US5832484A
Cited
US5919247A
Cited
US5974454A
Cited
US6151708A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2007-09-07 | 2008-03-08 | 2008-09-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2011-09-07 | 2012-03-08 | 2012-09-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2015-09-07 | 2016-03-08 | 2016-09-07 | $7700.00 | Window Closed / Lapsed |