Number-range search system and method

• US 7,693,824 B1
• Filed: 10/20/2003
• Issued: 04/06/2010
• Est. Priority Date: 10/20/2003
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Diament, Benjamin Jay
• Primary Examiner(s): Truong; Cam Y T
• Application Number:
  US10/690,401
• Time in Patent Office: 2,360 Days
• Field of Search: 707 3- 5, 707/10, 707/100, 707/102
• US Class Current: 1/1
• CPC Class Codes: G06F 16/322 Trees
• CPC Class Codes: G06F 16/328 Management therefor
• CPC Class Codes: G06F 16/93 Document management systems
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A system and method is disclosed for generating numerical index terms for numbers encountered in documents indexed by a search engine. The numerical index terms include information about the indexed number (e.g., fieldname, characteristic, sign) and each digit, or a subset of the digits, of the number (e.g., position, value). Also, disclosed is a system and method of processing number-range search queries having one or more number ranges and generating expressions (e.g., Boolean expression tree) of numerical index terms based on a boundary number associated with the number range. An expression is used to control the search of a document index so as to identify documents that contain numbers that satisfy the expression.

Claims

1. A computer-implemented method of querying number-range searches, comprising:

at a search engine having one or more processors and memory, the memory of the search engine storing one or more programs to be executed by the one or more processors of the search engine,

receiving a number-range search query having a number range, wherein the number range includes a boundary number;

generating an expression of numerical index terms based on the boundary number, wherein a respective numerical index term in the expression includes information indicative of an integral portion of a logarithm of the boundary number;

searching a document index of the search engine using the expression to identify one or more documents containing numbers that satisfy the expression; and

returning a result in accordance with at least a subset of the identified documents.

2. The method of claim 1, wherein at least one numerical index term in the expression includes information indicating that a specified digit is a last non-zero digit of a respective number.

3. The method of claim 1, wherein at least one numerical index term in the expression includes information indicative of a sign of a respective number.

4. The method of claim 1, wherein at least one numerical index term in the expression includes information indicative of a number type associated with a respective number range.

5. The method of claim 1, wherein the expression includes a plurality of numerical index terms that each correspond to a single respective digit of a respective number.

6. The method of claim 5, wherein a respective numerical index term in the expression represents a respective digit of a respective number in base 10.

7. The method of claim 6, wherein the respective numerical index term in the expression corresponds to the position of the respective digit within the respective number.

8. The method of claim 1, wherein the integral portion of the logarithm of a respective boundary number is an integral portion of a base 10 logarithm of the respective boundary number.

9. The method of claim 1, wherein a respective numerical index term in the expression includes information indicative of a mantissa of a respective number.

10. A computer-readable medium having stored thereon instructions which, when executed by a processor, cause the processor to perform the operations of:

receiving a number-range search query having a number range, wherein the number range includes a boundary number;

generating an expression of numerical index terms based on the boundary number, wherein a respective numerical index term in the expression includes information indicative of an integral portion of a logarithm of the boundary number;

searching a document index using the expression to identify one or more documents containing numbers that satisfy the expression; and

returning a result in accordance with at least a subset of the identified documents.

11. The computer-readable medium of claim 10, wherein at least one numerical index term in the expression includes information indicating that a specified digit is a last non-zero digit of a respective number.

12. The computer-readable medium of claim 10, wherein at least one numerical index term in the expression includes information indicative of a sign of a respective number.

13. The computer-readable medium of claim 10, wherein at least one numerical index term in the expression includes information indicative of a number type associated with a respective number range.

14. The computer-readable medium of claim 10, wherein the expression includes a plurality of numerical index terms that each correspond to a single respective digit of a respective number.

15. The computer-readable medium of claim 14, wherein a respective numerical index term in the expression represents a respective digit of a respective number in base 10.

16. The computer-readable medium of claim 15, wherein the respective numerical index term in the expression corresponds to a position of the respective digit within the respective number.

17. The computer-readable medium of claim 10, wherein the integral portion of the logarithm of a respective boundary number is an integral portion of a base 10 logarithm of the respective boundary number.

18. The computer-readable medium of claim 10, wherein a respective numerical index term in the expression includes information indicative of a mantissa of a respective number.

19. A search engine for querying number range searches, comprising:

one or more servers, each having one or more processors and memory, the memory of the one or more servers storing one or more programs to be executed by the one or more processors of the one or more servers, the one or more programs including;

a query encoder configured to receive a search query for a number range having a boundary number, wherein the query encoder is configured to generate an expression of numerical index terms based on the boundary number, and wherein a respective numerical index term in the expression includes information indicative of an integral portion of a logarithm of the boundary number; and

an index searcher coupled to the query encoder and configured to search a document index using the expression to identify one or more documents containing numbers that satisfy the expression and to return a result in accordance with at least a subset of the identified documents.

20. The search engine of claim 19, wherein at least one numerical index term in the expression includes information indicating that a specified digit is a last non-zero digit of a respective number.

21. The search engine of claim 19, wherein at least one numerical index term in the expression includes information indicative of a sign of a respective number.

22. The search engine of claim 19, wherein at least one numerical index term in the expression includes information indicative of a number type associated with a respective number range.

23. The search engine of claim 19, wherein the expression includes a plurality of numerical index terms that each correspond to a single respective digit of a respective number.

24. The search engine of claim 23, wherein a respective numerical index term in the expression represents a respective digit of a respective number in base 10.

25. The search engine of claim 24, wherein the respective numerical index term in the expression corresponds to a position of the respective digit within the respective number.

26. The search engine of claim 19, wherein the integral portion of the logarithm of a respective boundary number is an integral portion of a base 10 logarithm of the respective boundary number.

27. The search engine of claim 19, wherein a respective numerical index term in the expression includes information indicative of a mantissa of a respective number.