Answering queries using query signatures and signatures of cached semantic regions
First Claim
1. A method of obtaining answers to queries using a system that includes memory with a set of locations in memory defining a cache, the cache including, for each of a set of one or more semantic regions, contents that include one or more items of data;
- the method comprising;
(a) obtaining a query Q;
(b) using the query Q to obtain a query signature SQ; and
(c) using the query signature SQ and a region signature SR for at least one of the semantic regions to find one or more semantic regions that are qualified and using the contents of at least one of the qualified regions to obtain an answer to the query Q.
6 Assignments
0 Petitions
Accused Products
Abstract
In a system with cache that includes contents for each of a set of semantic regions, a query signature corresponding to a query is obtained. The query signature is used, together with a region signature for at least one of the regions, to find one or more semantic regions that are qualified and to use the contents of at least one of the qualified regions to obtain an answer to the query. The signatures can, for example, be binary strings, all having the same length. If the query and region formula are each a conjunction of terms, a signature can be obtained for each term and term signatures can be combined to obtain a query or region signature. Each signature can, for example, be a binary string, with all signatures having the same length so that signatures can be combined by performing logical operations. The query signature can be compared with the region signatures to determine whether the query is equivalent to or contained in any of the regions, in which case an answer can be obtained from cached contents. If not, another comparison can be made, either to determine whether any of the regions are contained within the query or to determine whether the query is likely to have a one-term difference with any of the regions. In these cases, a partial answer to the query can be obtained from cached contents that match the query, and a query remainder can be sent to obtain content necessary for a complete answer.
66 Citations
18 Claims
-
1. A method of obtaining answers to queries using a system that includes memory with a set of locations in memory defining a cache, the cache including, for each of a set of one or more semantic regions, contents that include one or more items of data;
- the method comprising;
(a) obtaining a query Q;
(b) using the query Q to obtain a query signature SQ; and
(c) using the query signature SQ and a region signature SR for at least one of the semantic regions to find one or more semantic regions that are qualified and using the contents of at least one of the qualified regions to obtain an answer to the query Q. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)
receiving signals indicating the query Q from the user interface device.
- the method comprising;
-
3. The method of claim 2 in which the system further includes an internet connection and the query Q is a World Wide Web query.
-
4. The method of claim 1, in which the query Q is a conjunction of terms and in which (b) comprises:
-
(b1) using each of the terms to obtain a respective term signature; and
(b2) combining the term signatures to obtain the query signature SQ.
-
-
5. The method of claim 4, in which each term signature is a binary string, all of the term signatures having the same length, and in which (b2) comprises:
performing one or more logical operations to combine the term signatures.
-
6. The method of claim 1, in which the cache further includes, for each semantic region, a replacement function value and in which (c) further comprises, after obtaining the answer, updating the replacement function value of the region.
-
7. The method of claim 1, in which the cache further includes, for each semantic region R, the region signature SR, and in which (c) comprises:
-
(c1) determining whether SQ=SRi for any of the semantic regions;
if not, determining whether SQ⊃
SRi for any of the semantic regions;
if not, determining whether SQ ⊂
SRi for any of the semantic regions; and
(c2) if (c1) determines that SQ=SRi for a region, obtaining the contents of the region as the answer to the query;
if (c1) determines that SQ⊃
SRi for one or more regions, obtaining an answer that includes items of data that match the query in the contents of one of the regions;
or if (c1) determines that SQ⊂
SRi for one or more regions, obtaining an answer that includes items of data from the contents of a subset of at least one of the regions.
-
-
8. The method of claim 7, in which the cache further includes, for each semantic region, a replacement function value and in which, if (c1) determines that SQ⊂
- SRi for a subset of regions, (c) further comprises;
constructing a query remainder from the query;
sending the query remainder to a server;
upon receiving an answer to the query remainder from the server, replacing the subset of regions with a semantic region equivalent to query Q; and
setting the replacement function value for the semantic region equivalent to query Q to a most recent value.
- SRi for a subset of regions, (c) further comprises;
-
9. The method of claim 8, in which the act of constructing the query remainder comprises:
-
setting the query remainder to query Q;
for each region in the subset, determining a difference between a formula for the region and the query Q, and if the difference is one term ai only, constraining the query remainder with ai.
-
-
10. The method of claim 1, in which each term has approximately k bits that are set, in which the cache further includes, for each semantic region, the region signature SR, and in which (c) comprises:
-
(c3) determining whether SQ=SR for any of the semantic regions;
if not, determining whether SQ∩
SR=SQ for any of the semantic regions;
if not, determining whether |SQ∩
SR|≧
|SR|−
k for any of the semantic regions; and
(c4) if (c3) determines that SQ=SR for a region, obtaining the contents of the region as the answer to the query Q;
if (c3) determines that SQ∩
SR=SQ for one or more regions, obtaining an answer that includes items of data that match the query Q in the contents of one of the regions;
or if (c3) determines that |SQ∩
SR|≧
|SR|−
k for one or more regions, obtaining an answer that includes items of data from the contents of a subset of at least one of the regions.
-
-
11. The method of claim 10, in which, if (c3) determines that |SQ∩
- SR|≧
|SR|−
k for one or more regions, (c4) comprises;constructing a query remainder from the query Q;
sending the query remainder to a server.
- SR|≧
-
12. The method of claim 11, in which the act of constructing a query remainder comprises:
-
setting the query remainder to query Q, and for each region Ri for which |SQ∩
SR|≧
|SR|−
k, determining a difference ai from the query Q and constraining the query remainder with ai.
-
-
13. The method of claim 11, In which, if (c3) determines that |SQ∩
- SR|≧
|SR|−
k for one or more regions, (c4) further comprises, after sending the query remainder to the server and before receiving an answer to the query remainder from the server;applying a criterion to the region signature SR for at least one of the semantic regions, the region signature SR meeting the criterion if either |SR|−
2k≦
|SR∩
SQ|<
|SR|−
k or 0≦
|SR∩
SQ|<
|SR|−
k; and
for a region whose region signature SR meets the criterion, if an intersection of the region with the query Q is not null, obtaining an answer that includes items of data that match the query Q in the region'"'"'s contents.
- SR|≧
-
14. The method of claim 11, in which the cache further includes, for each semantic region, a replacement function value and in which (c) further comprises, upon receiving an answer to the query remainder:
-
(c5) if a set of two or more regions in the cache together contain the query Q, replacing the set of regions that contain the query Q with a new region equivalent to the query Q;
if a region R in the cache is a complement to the query Q and a formula R∪
Q is a disjunction, replace the region R with a new region equivalent to the formula R∪
Q; and
otherwise, adding a new region to the cache equivalent to the query remainder; and
(c6) for each region from whose contents one or more items of data are included in the answer to the query Q, updating the region'"'"'s replacement function value.
-
-
15. A system for obtaining answers to queries, the system comprising:
-
memory, with a set of locations in memory defining a cache, the cache including, for each of a set of one or more semantic regions, contents that include one or more items of data; and
a processor connected for accessing the memory;
the processor operating to;
obtain a query Q;
use the query Q to obtain a corresponding query signature SQ; and
use the query signature SQ and a region signature SR for at least one of the semantic regions to find one or more semantic regions that are qualified and using the contents of at least one of the qualified regions to obtain an answer to the query Q. - View Dependent Claims (16, 17)
a set of one or more user interface devices for providing a user interface;
the processor being connected to the set of user interface devices for providing signals to and receiving signals from a user;
the processor obtaining the query a by receiving signals indicating the query Q from a user through one of the set of user interface devices;
the processor further operating to;
provide the answer to the query a to the user through one of the user interface devices.
-
-
17. The system of claim 16, further comprising:
an internet connection to the processor;
the query Q being a World Wide Web query.
-
18. An article of manufacture for use in a system that includes:
-
memory, with a set of locations in memory defining a cache, the cache including, for each of a set of one or more semantic regions, contents that include one or more items of data;
a storage medium access device for accessing data on storage media; and
a processor connected for receiving queries, for accessing the memory, and for accessing data on storage media using the storage medium access device;
the article of manufacture comprising; a storage medium;
instruction data stored on the storage medium, the instruction data defining a sequence of instructions that can be accessed by the processor using the storage medium access device;
the processing, in executing the sequence of instructions;
obtaining a query Q;
using the query Q to obtain a corresponding query signature SQ; and
using the query signature SQ and a region signature SR for at least one of the semantic regions to find one or more semantic regions that are qualified and using the contents of at least one of the qualified regions to obtain an answer to the query Q.
-
Specification