Identifying results through substring searching

• US 8,296,279 B1
• Filed: 06/03/2008
• Issued: 10/23/2012
• Est. Priority Date: 06/03/2008
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Singh, Mukesh Kumar
• Primary Examiner(s): MORRISON, JAY A
• Application Number:
  US12/132,094
• Time in Patent Office: 1,603 Days
• Field of Search: None
• US Class Current: 707/706
• CPC Class Codes: G06F 16/313 Selection or weighting of terms for indexing
• CPC Class Codes: G06F 16/3338 Query expansion
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques

Abstract

Systems, methods, and computer program products identifying a search query, the search query including at least one search term. An index is used to identify a word as a search result for the search query, where the index includes a substring of the word, one or more inclusive strings corresponding to the substring, the one or more inclusive strings including the substring and at least one more character, and one or more word objects, the one or more word objects identifying content including the substring of the word.

Claims

1. A computer-implemented method, comprising:

identifying a search query comprising one or more search terms;

identifying an index for a word, wherein the word or a substring of the word matches one of the one or more search terms of the search query, and wherein the index comprises;

one or more substrings of the word, wherein each substring includes one or more but not all characters included in the word;

one or more inclusive strings corresponding to the one or more substrings, each of the one or more inclusive strings comprising the corresponding substring and at least one more character included in the word; and

two or more word objects, wherein each of the one or more substrings correspond to at least one of the two or more word objects, and the two or more word objects identify content that includes at least one substring of the word; and

using the index to identify one or more search results for the search query based on the two or more word objects;

wherein the word object is a location of a web page in which the word occurs.

2. The method of claim 1, wherein the word occurs in a web page identified by a uniform-resource locator (URL) identified by a word object that corresponds to the word.

3. The method of claim 1, further comprising:

receiving a numerical variable ‘

k’

; and

generating the index using the numerical variable ‘

k’

,

wherein the one or more substrings of the word do not include a greater number of characters than the numerical variable ‘

k’

.

4. The method of claim 1, wherein the index comprises at least one index table or at least one indexed tree.

5. The method of claim 1, wherein at least one search term includes a wildcard character.

6. The method of claim 5, further comprising dividing the search term into two or more sub-patterns.

7. The method of claim 6, further comprising identifying a sub-pattern, from the two or more sub-patterns, that is identical to one of the one or more substrings of the word.

8. The method of claim 7, further comprising comparing the word to the sub-pattern to determine if the word satisfies the sub-pattern.

9. The method of claim 8, further comprising identifying the at least one word object that corresponds to the word as a search result for the search query if the word satisfies the sub-pattern.

25. The method of claim 1, wherein:

the one search term matches the word; and

the one or more search results include all content identified by the two or more word objects.

26. The method of claim 1, wherein:

the one or more substrings comprises a plurality of substrings and the two or more word objects comprise a plurality of word objects;

the one search term matches a first substring of the plurality of substrings of the word; and

the one or more search results include content identified by one or more word objects of the plurality of word objects, and the one or more word objects correspond to the first substring and one or more substrings that match the one or more inclusive strings that correspond to the first substring.

27. The method of claim 1, wherein:

the index further includes the word; and

at least one or more of the two or more word objects identify content that includes the word.

10. A method, comprising:

creating an index corresponding to a word occurring in content at one or more network locations, the index including;

two or more substrings of the word;

one or more inclusive strings associated with at least one of the two or more substrings of the word, each of the one or more inclusive strings comprising the corresponding substring and at least one more character included in the word; and

one or more locations, wherein each of the two or more substrings correspond to at least one of the one or more locations, and the one or more locations identify content that includes at least one of the substring of the word;

identifying a search query, the search query including at least one search term that matches the word; and

using the index to identify one or more search results for the search query based on the one or more locations included in the index

wherein the location is a network location of a web page in which the word occurs.

11. The method of claim 10, wherein creating an index corresponding to a word comprises creating an index corresponding to a word occurring in an object identified by a memory address or a unique ID in a storage device.

12. The method of claim 10, wherein creating an index corresponding to a word comprises creating an index corresponding to a word occurring in a web page identified by a uniform-resource locator (URL).

13. The method of claim 10, further comprising receiving a numerical variable ‘

k’

, and wherein each of the two or more substrings do not include a greater number of characters than the numerical variable ‘

k’

.

14. The method of claim 10, wherein the index comprises at least one index table or at least one indexed tree.

15. The method of claim 10, wherein identifying a search query comprises identifying a search query comprising at least one search term having a wildcard character.

16. The method of claim 15, further comprising dividing the search term into two or more sub-patterns.

17. The method of claim 16, further comprising identifying a sub-pattern, from the two or more sub-patterns, that is identical to the substring, of the two or more substrings, having a least number of associated inclusive substrings.

18. A system, comprising:

means for creating an index corresponding to a word occurring in content at one or more network locations, the index including;

two or more substrings of the word;

one or more inclusive strings associated with at least one of the two or more substrings of the word, each of the one or more inclusive strings comprising the corresponding substring and at least one more character included in the word; and

one or more locations, wherein each of the two or more substrings correspond to at least one of the one or more locations, and the one or more locations identify content that includes at least one of the substring of the word;

means for identifying a search query, the search query including at least one search term that matches the word; and

means for using the index to identify one or more search results for the search query based on the one or more locations included in the index;

wherein the location is a network location of a web page in which the word occurs.

19. The system of claim 18, wherein means for creating an index corresponding to a word comprises means for creating an index corresponding to a word occurring in a web page identified by a uniform-resource locator (URL).

20. The system of claim 18, further comprising means for receiving a numerical variable ‘

k’

, and wherein each of the two or more substrings do not include a greater number of characters than the numerical variable ‘

k’

.

21. The system of claim 18, wherein the index comprises at least one index table or at least one indexed tree.

22. The system of claim 18, wherein the means for identifying a search query comprises means for identifying a search query comprising at least one search term having a wildcard character.

23. The system of claim 22, further comprising means for dividing the search term into two or more sub-patterns.

24. The system of claim 23, further comprising means for identifying a sub-pattern, from the two or more sub-patterns, that is identical to the substring, of the two or more substrings, having the least number of associated inclusive substrings.

28. A computer-implemented method, comprising:

receiving a search query that includes one or more search terms;

identifying an index for a word, wherein the word matches one of the one or more search terms of the search query, and wherein the index comprises;

the word which includes a plurality of characters;

a plurality of substrings of the word, wherein each substring includes one or more but not all of the characters included in the word;

a plurality of inclusive strings corresponding to a substring from the plurality of substrings, each inclusive string from the plurality of inclusive strings comprising the corresponding substring and at least one more character included in the word, and

a plurality of word objects, wherein each of the words and each of the substrings corresponds to at least one of the word objects that identifies content that includes the respective word or substring; and

using the index to identify one or more search results for the search query based on the content identified by the plurality of word objects;

wherein the word object is a location of a web page in which the word occurs.