Enabling Faster Full-Text Searching Using a Structured Data Store

• US 20110113048A1
• Filed: 11/09/2010
• Published: 05/12/2011
• Est. Priority Date: 11/09/2009
• Status: Abandoned Application

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Inventors: Njemanze, Hugh S.
• Application Number:
  US12/942,890
• Publication Number:
  US 20110113048A1
• Time in Patent Office: Days
• US Class Current: 707/755
• CPC Class Codes: G06F 16/243 Natural language query formulation
• CPC Class Codes: G06F 16/24522 Translation of natural language queries to structured queries
• CPC Class Codes: G06F 16/3329 Natural language query formulation or dialogue systems
• CPC Class Codes: G06F 2207/025 String search, i.e. pattern matching, e.g. find identical word or best match in a string
• CPC Class Codes: G06F 7/02 Comparing digital values G06F7/06, G06F7/22, G06F7/38 take precedence

Abstract

A traditional structured data store is leveraged to provide the benefits of an unstructured full-text search system. A fixed number of “extended” columns is added to the traditional structured data store to form an “enhanced structured data store” (ESDS). The extended columns are independent of any regular columnar interpretation of the data and enable the data that they store to be searched using standard full-text query syntax/techniques that can be executed faster (as opposed to SQL syntax). In other words, the added columns act as a search index. A token is stored in an appropriate extended column based on that token'"'"'s hash value. The hash value is determined using a hashing scheme, which operates based on the value of the token, rather than the meaning of the token. This enables subsequent searches to be expressed as full-text queries without degrading the ensuing search to a brute force scan.

Claims

1. A computer-implemented method for storing information in an entry within a structured data store, wherein the entry includes one or more base fields and one or more extended fields, comprising:

receiving a string;

extracting information from the string;

storing the extracted information in the one or more base fields of the entry based on the meaning of the extracted information;

identifying a portion of the string that is to be enabled for faster searching;

parsing the identified portion of the string into a plurality of tokens; and

for each token in the plurality of tokens;

determining a hash value of the token based on a hashing scheme; and

storing the token in an extended field that corresponds to the determined hash value.

2. The method of claim 1, wherein the identified portion of the string comprises the entire string.

3. The method of claim 1, wherein the identified portion of the string is a value stored in a base field.

4. The method of claim 1, wherein the hash value of the token comprises a character.

5. The method of claim 1, wherein the hashing scheme comprises using the first character of the token as the token'"'"'s hash value.

6. The method of claim 1, wherein the hash value of the token comprises a number.

7. The method of claim 1, wherein the hashing scheme comprises using the number of characters within the token as the token'"'"'s hash value.

8. The method of claim 1, wherein the hashing scheme comprises using both the first character of the token and the number of characters within the token as the token'"'"'s hash value.

9. The method of claim 1, further comprising:

for each token in the plurality of tokens;

generating a token pair that comprises the token and a second token that immediately follows the token within the identified portion of the string;

determining a hash value of the token pair based on a hashing scheme; and

storing the token pair in an extended field that corresponds to the determined hash value.

10. The method of claim 1, further comprising:

for each token in the plurality of tokens;

if the token is the first token within the identified portion of the string;

generating a beginning token that comprises a special character and the token, wherein the special character indicates that the token is the first token within the identified portion of the string;

determining a hash value of the beginning token based on a hashing scheme; and

storing the beginning token in an extended field that corresponds to the determined hash value.

11. The method of claim 1, further comprising:

for each token in the plurality of tokens;

if the token is the last token within the identified portion of the string;

generating an ending token that comprises the token and a special character, wherein the special character indicates that the token is the last token within the identified portion of the string;

determining a hash value of the ending token based on a hashing scheme; and

storing the ending token in an extended field that corresponds to the determined hash value.

12. A computer program product for storing information in an entry within a structured data store, wherein the entry includes one or more base fields and one or more extended fields, and wherein the computer program product is stored on a computer-readable medium that includes instructions that, when loaded into memory, cause a processor to perform a method, the method comprising:

receiving a string;

extracting information from the string;

storing the extracted information in the one or more base fields of the entry based on the meaning of the extracted information;

identifying a portion of the string that is to be enabled for faster searching;

parsing the identified portion of the string into a plurality of tokens; and

for each token in the plurality of tokens;

determining a hash value of the token based on a hashing scheme; and

storing the token in an extended field that corresponds to the determined hash value.

13. A system for storing information in an entry within a structured data store, wherein the entry includes one or more base fields and one or more extended fields, the system comprising:

a computer-readable medium that includes instructions that, when loaded into memory, cause a processor to perform a method, the method comprising;

receiving a string;

extracting information from the string;

storing the extracted information in the one or more base fields of the entry based on the meaning of the extracted information;

identifying a portion of the string that is to be enabled for faster searching;

parsing the identified portion of the string into a plurality of tokens; and

for each token in the plurality of tokens;

determining a hash value of the token based on a hashing scheme; and

storing the token in an extended field that corresponds to the determined hash value; and

a processor for performing the method.