Source: https://patents.google.com/patent/US8407239B2/en
Timestamp: 2019-09-22 07:20:39
Document Index: 511697942

Matched Legal Cases: ['art 1', 'Application No. 200580034128', 'Application No. 200580034128', 'Application No. 200580034128', 'Application No. 201010144526', 'Application No. 201110121210', 'Application No. 05784308', 'Application No. 05784308', 'Application No. 2007', 'Application No. 2007']

US8407239B2 - Multi-stage query processing system and method for use with tokenspace repository - Google Patents
US8407239B2
US8407239B2 US10/917,746 US91774604A US8407239B2 US 8407239 B2 US8407239 B2 US 8407239B2 US 91774604 A US91774604 A US 91774604A US 8407239 B2 US8407239 B2 US 8407239B2
US20060036593A1 (en
This application is related to U.S. patent application Ser. No. 10/917,745, filed Aug. 13, 2004, entitled “System and Method for Encoding and Decoding Variable-Length Data,” and U.S. patent application Ser. No. 10/917,739, filed Aug. 13, 2004, entitled “Document Compression System and Method For Use With Tokenspace Repository,” which applications are incorporated by reference herein in their entirety.
In some embodiments, a list of information is received by the preprocessor 302 which orders the information for efficient encoding. The preprocessor 302 may order the data into a monotonic sequence using one or more sorting algorithms. For example, if a set of integers are sorted by value, then adjacent integers will be close in magnitude, thus enabling the delta encoder 304 to generate delta values that are small valued integers for encoding. The ordered data is received by the delta encoder 304, which computes differences between adjacent pairs of the ordered data to obtain the small valued integers. The small valued integers are received by the variable-length data encoder 306, which encodes the data into a compressed format which can be efficiently decoded. One example of a suitable variable-length data encoder 306 is described more fully in co-pending U.S. patent application Ser. No. 10/917,745, entitled “System and Method For Encoding And Decoding Variable-Length Data.”
FIG. 3B is a block diagram of an embodiment of a decoding system 308 for decoding documents in a tokenspace repository. The decoding system 308 includes a variable-length data decoder 310 and an optional delta decoder 312. In some embodiments, encoded groups of data are received by the variable-length data decoder 310, which decodes the groups with the assistance of one or more offset/mask tables. The decoded data is received by the delta decoder 312, which computes running sums, thereby producing delta-decoded data, which is equivalent to the original list of information. The use of offset/mask tables in decoding group encoded variable-length integer values is described more fully in co-pending U.S. patent application Ser. No. 10/917,745, entitled “System and Method For Encoding And Decoding Variable-Length Data.”
FIG. 3C is a block diagram of an embodiment of an attribute encoding/decoding system 314 for encoding/decoding document attributes. The attribute encoding/decoding system 314 includes an encoding/decoding system 320 which encodes attribute information 322 into attribute records 318 for storage in an attribute table 316. The attributes for a document are determined on a token-by-token basis, with a 0 or 1 bit value being used to represent the presence or absence of each attribute for a given token. For instance an attribute record 318 in the attribute table may be conceptually represented as an A.times.K bit map, where A is the number of attributes that are encoded and K is the number of tokens whose attributes are represented by the record 318. If A is 8 and K is 32, then each attribute record 318 stores eight attributes for each of 32 tokens. Each attribute record 318 may be encoded so as to compress the amount of space occupied by the attributes table while enabling very fast decoding of selected attribute records during query processing. One suitable methodology for encoding and decoding the attribute records 318 is described in co-pending U.S. patent application Ser. No. 10/917,745, entitled “System and Method For Encoding And Decoding Variable-Length Data.” Alternately, the information in each attribute record may be run-length encoded.
performing first stage processing of the query, including:
retrieving from an index, a list of token positions for one or more query terms in the query, wherein the token positions in the list specify positions of individual tokens that match the query terms;
based on the list of token positions, producing a first set of document identifiers, and
generating a first set of relevancy scores for a first set of documents corresponding to the first set of document identifiers;
generating a second set of relevancy scores for the documents in the first set of documents based on one or more of: the list of token positions, distances between query terms in the documents, attributes of tokens in the documents, and a context in which a query term is used in a document of the first set of documents, and
selecting a subset of the first set of documents based on the second set of relevancy scores;
automatically generating one or more new query expansion terms based on documents in the subset of the first set of documents; and
generating a new query expression based on the query and the one or more new query expansion terms for processing by at least the first processing stage to produce at least a second set of document identifiers corresponding to a second set of documents.
reconstructing one or more portions of the first set of documents using the list of token positions.
presenting the reconstructed portions to a user with an ordered list of documents selected from the first and second sets of documents based at least in part on the second set of relevancy scores.
adjusting the first set of relevancy scores for the documents in the first set of documents based on one or more of: the list of token positions, attributes of tokens in the documents, and a context in which a query term is used in a document of the documents to generate the second set of relevancy scores.
during the second stage processing of the query, generating snippets for one or more documents in the subset of the first set of documents; and
automatically generating one or more new query expansion terms based on the snippets.
6. The method of claim 1, wherein the token positions in the list of token positions are positions in a document repository having a range of token positions, wherein documents in the repository have distinct non-overlapping sub-ranges of token positions within the document repository's range of token positions.
7. A computer readable storage medium storing one or more programs configured for execution by a computer, the one or more programs comprising instructions to:
perform first stage processing of the query, including:
perform a second stage processing of the query, including:
automatically generate one or more new query expansion terms based on documents in the subset of the first set of documents; and
generate a new query expression based on the query and the one or more new query expansion terms for processing by at least the first processing stage to produce at least a second set of document identifiers corresponding to a second set of documents.
reconstruct one or more portions of the first set of documents using the list of token positions.
present presenting the reconstructed portions to a user with an ordered list of documents selected from the first and second sets of documents based at least in part on the second set of relevancy scores.
adjust the first set of relevancy scores for the documents in the first set of documents based on one or more of: the list of token positions, attributes of tokens in the documents, and a context in which a query term is used in a document of the documents to generate the second set of relevancy scores.
11. The computer readable storage medium of claim 7, further comprising instructions for use during the second stage processing of the query, comprising:
generate snippets for one or more documents in the subset of the first set of documents; and
automatically generate one or more new query expansion terms based on the snippets.
12. The computer readable storage medium of claim 7, wherein the token positions in the list of token positions are positions in a document repository having a range of token positions, wherein documents in the repository have distinct non-overlapping sub-ranges of token positions within the document repository's range of token positions.
13. A multi-stage query processing system, comprising:
16. The system of claim 13, further comprising instructions to:
instructions for use during the second stage processing of the query, comprising:
18. The system of claim 13, wherein the token positions in the list of token positions are positions in a document repository having a range of token positions, wherein documents in the repository have distinct non-overlapping sub-ranges of token positions within the document repository's range of token positions.
US20060036593A1 US20060036593A1 (en) 2006-02-16
US8407239B2 true US8407239B2 (en) 2013-03-26
Fukushima, Basic technologies and trends of Web search engines, Part 1, Basic technologies, pp. 363-372.
Google Inc., International Search Report and Written Opinion, PCT/US2005/028192, Jan. 16, 2006, 11 pgs.
Google Inc., Office Action, Chinese Patent Application No. 200580034128.9, Apr. 25, 2008, 8 pgs.
Google Inc., Office Action, Chinese Patent Application No. 200580034128.9, Dec. 5, 2008, 3 pgs.
Google Inc., Office Action, Chinese Patent Application No. 200580034128.9, Jun. 8, 2010, 4 pgs.
Google inc., Office Action, Chinese Patent Application No. 201010144526.9, Jan. 27, 2011, 6 pgs.
Google Inc., Office Action, Chinese Patent Application No. 201110121210.2, Nov. 16, 2011, 6 pgs.
Google Inc., Office Action, European Patent Application No. 05784308.8, Aug. 12, 2010, 7 pgs.
Google Inc., Office Action, European Patent Application No. 05784308.8, May 10, 2012, 7 pgs.
Google Inc., Office Action, Japanese Patent Application No. 2007-525718, Nov. 10, 2010, 6 pgs.
Google Inc., Office Action, Korean Patent Application No. 2007-7005777, Jul. 25, 2011, 3 pgs.
Search Report for International Application No. PCT/US2005/028192, dated Jan. 16, 2006.
Sheng, X., et al., "An Information Retrieval System Based on Automatic Query Expansion and Hopfield Network," IEEE Int'l Conf. Neural Networks & Signal Processing, Nanjing, China, Dec. 14-17, 2003.