Search templates

Searching a data store for parameter patterns specified in a query. A method includes receiving a query from a user including N parameter patterns. One or more alternatives are associated to one or more of the N parameter patterns. One or more templates are created. Each of the templates describes a number of microsearches. Each of the microsearches includes one or more of the N parameter patterns or the alternatives. Microsearches described by at least one of the one or more templates are enumerated. One or more sub-microsearches are performed by searching for parameter patterns and/or alternatives. Each sub-microsearch may have less than all terms needed for a full microsearch. Based on the results of the one or more sub-microsearches, one or more microsearches are eliminated from searching. The data store is searched using one or more of the remaining microsearches.

BACKGROUND

Background and Relevant Art

To facilitate the retrieval of electronic content from a database, several types of search engines and indexes have been developed. Initially, traditional databases were developed with fields of information that could only be searched through a rigid alphabetically ordering of associated fields, such as a last name field. Later, full text indexing was developed to provide greater searching flexibility. With a full text index, all words are indexed and can therefore be searched for within a document or record.

Often, search engines can provide results to a user in a ranked fashion. Ranking may be based on relevance or other factors. Additionally some search engines will provide results that include alternatives to search terms specified in a query. These results are typically ranked by relevance by taking into account the search terms in the records returned as compared to the search terms specified by a user. This ranking is typically accomplished by performing a union of searching of search terms for the entire database where each search term has a weight, and the relevance of a result is based on the combined weight of each search term that references the record or document. The highest ranked results are the records with the highest summation of weights coming from search terms. Computing the combined weights and sorting the highest ranked records to the top of this large set is cumbersome and computationally expensive.

BRIEF SUMMARY

One embodiment illustrated herein is directed to a method of searching a data store. The method may be practiced in a computing environment including a data store. The data store includes data items stored in records in the data store. The method includes acts for searching the data store for parameter patterns specified in a query. The method includes receiving a query from a user including N parameter patterns. One or more alternatives are associated to one or more of the N parameter patterns. One or more templates are created. Each of the templates describes a number of microsearches. Each of the microsearches includes one or more of the N parameter patterns or the alternatives. Microsearches described by at least one of the one or more templates are enumerated. One or more sub-microsearches are performed by searching for parameter patterns and/or alternatives. Each sub-microsearch may have less than all terms needed for a full microsearch. Based on the results of the one or more sub-microsearches, one or more microsearches are eliminated from searching. The data store is searched using one or more of the remaining microsearches.

DETAILED DESCRIPTION

Embodiments herein may comprise a special purpose or general-purpose computer including various computer hardware, as discussed in greater detail below.

Some embodiments described herein are directed to ranking searches of a data store before the searches are performed as opposed to ranking results after searches are performed on the data store. For example, previously, search engines have searched records in the data store for search terms and alternatives to the search terms and then ranked the results according to the search terms or alternatives found in a particular record. Some embodiments described herein, instead rank the searches to be performed and perform a sufficient number of searches to obtain the desired number of results.

In particular, in one embodiment a system receives a query which includes a number of parameter patterns. Alternatives are associated with the parameter patterns from the query. Templates are then created where the templates generally describe a number of microsearches that can be performed. The microsearches are combinations of parameter patterns and/or alternatives that should be searched for in the data store. Microsearches for a template may be enumerated. Sub-microsearches, which are searches of parameter patterns representing less than some entire microsearch can be performed where the results of the sub-microsearch are used to eliminate microsearches from the enumerated microsearches. The sub-microsearches may also be able to be used to eliminate entire templates or to eliminate microsearches before they are enumerated. Remaining microsearches can be used to search the data store.

This method of searching may be especially useful for search methods where portions of a data store are eliminated from searching by identifying the absence of one or more parameter patterns or the intersection of one or more parameter patterns. Such a search method is illustrated in U.S. application Ser. No. 11/847,688 titled “Vortex Searching” filed concurrently herewith, which is incorporated herein by reference.

Referring now toFIGS. 1A-1C, an embodiment is illustrated.FIG. 1Aillustrates an alternatives association module102, which may be, for example, a software module of a search engine system. A query104from a user may be received by the alternatives association module102. The alternatives association module102associates alternative parameter patterns with parameter patterns specified in the query104. For example, the query104includes a parameter pattern specifying a first name of John (F: John). Alternatives to John that may be assigned by the alternatives association module102include Jack and J. as illustrated.

FIG. 1Afurther illustrates that the query104includes a first name argument (F: John) a surname argument (S: Kennedy) a birth year argument (B: 1917), a death year argument (D: 1963) and a place argument (P: Boston Mass.).FIG. 1Aalso illustrates that the alternatives association module102associates alternatives with the first name (Jack and J.) birth year (1914-1920), death year (1959-1966) and place (Cambridge) arguments, as illustrated. Alternatives may be associated based on the functionality or environment in which the query104is implemented. In the example illustrated inFIG. 1A, no alternative is associated with Kennedy, perhaps because Kennedy is sufficiently unique that any alternatives would be irrelevant to a user submitting the query104. For the birth years and death years, alternatives are associated based on the proximity to the year specified in the query. In the present example, alternatives are allowed to be three years before and after. For the place, in this example, the selected alternative is based on geographical proximity. Illustratively, Cambridge Mass. being geographically proximate to Boston Mass. causes Cambridge to be selected as an alternative.

In some embodiments, weights may be assigned at the alternatives association module102to the parameter patterns and alternatives (also referred to herein as alternative parameter patterns). The weights may define a relevance measurement for a parameter pattern or alternative. As might be expected, the parameter patterns specified in the query are often assigned weights indicating their being the most significant. While in this example, higher weights indicate more significance, other weighting systems may be used including lower weighting indicating more significance. Illustratively,FIG. 1Ashows that a weight of 20, as indicated in the parenthesis, is assigned to the parameter pattern John. The alternative Jack has a weight of 18 assigned to it. The alternative J. has a weight of 16 assigned to it. Similarly, parameter patterns for birth and death years specified in the query each of a weight of 10 assigned to them. The alternatives are assigned a weight of 1 less for each year away they are from the year specified in the query. For example, for a parameter pattern 1917 specified in a query, the alternatives 1916 and 1918 each have a weight of 9. For the alternatives 1915 and 1919, the weight assigned is 8. For the alternatives 1914 and 1920, the weight assigned is 7. The example further illustrates that the weight assigned for MA is 10, the weight for Boston is 7, and the weight for Cambridge is 5. These weights may be used later in the process to determine which microsearches to search, when to enumerate microsearches from other templates, and when to create templates as will be explained in more detail herein.

Relevance ranking algorithms could be dynamic rather than static, with an update process based on feedback from the user. For example, a user searches for John Kennedy, b. 1917 in CT, died 1963 in TX. Suppose no acceptable result is found, and that the ranking algorithm only scored points for an exact hit in states. Suppose then that another search came in for John Kennedy, b. 1917 in RI, died 1963 in TX. A query log could be kept. When it is detected that an almost identical query has come in soon after the first query, then it is clear that the user is telling us that he is unsure of the state of birth. The ranking algorithm could be then be modified to give points for nearby states. Assuming the search is for JFK, including MA in the search would give the desired result.

Referring now toFIG. 1B, a template generation module106is illustrated. The template generation module receives as input the parameter patterns and alternatives associated with the parameter patterns from the alternative association module102. The parameter patterns and alternatives108are used to create templates, such as templates110,112, and114. Notably,FIG. 1Bonly shows a small sample of the possible templates that may be created. Each of the templates describes a number of microsearches, where each of the microsearches includes one or more of the parameter patterns from the query or the alternatives. Notably, as will be described later herein, templates may be generated on an as needed basis. This can help to conserve computing power as some templates may not be generated if they are not needed to achieve a given number of search results.

Each of the templates may have a weight or range of weights associated with them. The weights or range of weights are the weights of the microsearches described by the template. For example template110describes a microsearch John Kennedy 1917 1963 Boston Mass. In this example of one implementation, the weight of this microsearch is calculated by adding the weights of the individual parameter patterns or alternatives. Thus, this particular microsearch has a weight of (20)+(30)+(10)+(10)+(10)+(7)=87. At the less significant weight end, the template110describes a microsearch John Kennedy 1914 1960 Cambridge Mass. which has a weight of 79. Thus, the weight range116for the template110is 87-79. This weight range may be used when determining when to enumerate microsearches as will be described in more detail below.

FIG. 1Cillustrates a microsearch enumeration module118. While the template110may describe generally the micorsearches of a template110, the microsearch enumeration module118may enumerate specifically all or a portion of the microsearches described by the template110.FIG. 1Cillustrates where all microsearches have been enumerated, although not all microsearches for the template110are shown. Notably, rather than enumerating all microsearches, microsearches may also be enumerated on an as needed basis as will be discussed in more detail below.

The system illustrated inFIGS. 1A-1Cmay further include functionality for performing sub-microsearches. Sub-microsearches are searches which include less than a given full microsearch. For example, for the microsearches enumerated inFIG. 1C, a sub-microsearch may be Kennedy-Cambridge as a single compound term or Kennedy-John-Cambridge as single compound term. Assuming that requirements for records returned for the query specify that all results must include the parameter pattern Kennedy, and if the sub-microsearch can identify that the terms Kennedy and Cambridge do not appear in the same record of the data store, then all microsearches including the term Cambridge can be eliminated from further searching. For example, at least the microsearches identified at120, as well as a number of microsearches not shown for template110and for other templates can be eliminated from further searching. In some cases, entire templates can be eliminated from searching such that there is no need to generate a given template or to enumerate some microsearches.

Note that microsearches may be eliminated on a consolidated basis. For example, template110(although not shown inFIG. 1C) includes a segment from the 74thmicrosearch to the 83rdmicrosearch which is as follows:

74Kennedy John 1914 1966 MA Boston75Kennedy John 1915 1961 MA Cambridge76Kennedy John 1915 1965 MA Cambridge77Kennedy John 1916 1960 MA Cambridge78Kennedy John 1916 1966 MA Cambridge79Kennedy John 1918 1960 MA Cambridge80Kennedy John 1918 1966 MA Cambridge81Kennedy John 1919 1961 MA Cambridge82Kennedy John 1919 1965 MA Cambridge83Kennedy John 1920 1960 MA Boston
In this example, microsearches 75-82 all include the term Cambridge. Embodiments may be implemented where loops, jumps, or groupings may be used to eliminate microsearches. For example, an elimination routine may use a “for” loop which is executed eight times to eliminate microsearches 75-82. Alternatively, a routine identifying included microsearches may jump over microsearches 75-82. Further, in another alternative, embodiments may be implemented where microsearches 75-82 are eliminated as a group or vector of microsearches.

The sub-microsearches may be performed using a number of different mechanisms. For example, different types of indexes and index searches may be used to perform the sub-microsearches. Examples of indexes that may be used include an abbreviated index or a full index of the data store.

An abbreviated index is a probabilistic data structure that identifies within some probability if a parameter pattern or combination of parameter patterns is included in a data store. The abbreviated index can quickly identify with a certainty that a parameter pattern is not included in a data store. Thus, the abbreviated index is well suited for searching sub-microsearches to eliminate microsearches. An example of an abbreviated index is illustrated in U.S. patent application Ser. No. 11/681,673, titled “Abbreviated Index” and filed on Mar. 2, 2007, which is incorporated herein by reference in its entirety. Additionally, the following illustrates generally the principles of abbreviated indexing.

Referring now toFIG. 2, an abbreviated index202is illustrated, which in this example is a 32 bit binary number. The abbreviated index202is shown with an index field204and a value field206. Notably, the index field204in this example is shown for convenience of explanation. The value field206, in this example, includes the 32 bit binary number stored in physical memory. The index field204includes hexadecimal index representations of each of the elements of the 32 bit number represented in the value field206.

FIG. 2further illustrates a numerical representation table208. The numerical representation table208includes a parameter patterns field210, a numerical representation field212, a last 8 bits field214, a last 5 bits field216, and a hex of the last 5 bits field218.

In the example illustrated inFIG. 2, the parameter patterns field210represents search strings that may be performed to locate elements in a data store, such as a data store including the phrase “The quick red fox.”

The numerical representation field212in this example includes a numerical representation of each of the parameter patterns in the parameter patterns field210. The numerical representations may be generated in any suitable fashion. In this particular example the numerical representations are hash values of the parameter patterns. For example, a hash calculation may be performed for the parameter “fox.” This hash calculation results in a number, which in this example is represented as a 64 bit hexadecimal number. Preferably, the hash calculation is performed using a good algorithm that results in a high percentage of unique numbers for calculations performed on different parameters and parameter patterns. For example, it is preferable that a hash calculation for “fox” results in a number that is different from the hash calculation for “red.” The other fields in the numerical representation table208will be explained in more detail at a later point herein. Notably, other identifiers than hash numbers may be used. Hash numbers are simply one embodiment of identifiers. Numerous other identifiers may be used as well.

Referring once again to the abbreviated index202, each of the elements of the value field206represents a portion of a numerical representation212in the numerical representation table208. Thus, the value field206contains a representation that a parameter pattern may be included in a set of parameters, such as a data store, based on the calculated hash for the parameter pattern. In this example, when a bit is set or as used herein “true,” i.e. “1” in an element of the value field206, this is an indication that a parameter pattern may be included within a set of parameters. Specifically, this indicates that a parameter pattern may be found in a data store which the abbreviated index202indexes.

For effective results, the abbreviated index202typically includes a number of elements that is equal to or greater than some multiple greater than 1 of the number of parameter patterns for a set of parameters. In the present example, 15 parameter patterns are included in the illustrated set of parameters. The abbreviated index202corresponding to the set of parameters therefore includes 32 elements (i.e. the 32 binary digits of the 32 bit binary number in the abbreviated index202) which is a value greater than 2× of 15. Notably, the number of a multiplier (in this example 2) provides greater confidence that a parameter pattern is included in the set of parameters as the multiplier increases. For example, in the present 2× example, if a bit in the abbreviated index is set indicating that a parameter pattern may be included in the set of parameters, the confidence is about 50%. If a 64 bit binary number representing a 4× multiplier is used to represent the abbreviated index, confidence can be increased to about 75%. Similar increases in confidence can be achieved as the number of elements used to represent the abbreviated index is increased.

Now with particular emphasis on how the existence of parameter patterns are noted in the abbreviated index202, note thatFIG. 2includes the last five bits of hash field216. The last five bits of hash field represents the last five binary bits of the hexadecimal number in the numerical representation field212. Five bits are selected because that is the number of binary bits needed to represent 32 unique binary numbers, the number of binary bits in the abbreviated index202. Note that while the last five bits have been chosen in this example, embodiments are not limited to just the last bits. Any appropriate selection of bits can be used. In this example, so long as the same bits are used consistently to set bits in the abbreviated index202, effective filtering can be performed.

For the parameter pattern “fox” in the parameter pattern patterns field210, a hash of 40b8636cf497235c is calculated as shown in the numerical representation field212. The last two hexadecimal numbers of the hash are 5c. These numbers represent the 8 bit binary number 01011100 as shown in the last 8 bits of hash field214. By truncating the three most significant bits, the five least significant bits remain which are 11100 as shown in the last 5 bits of hash field216. The last 5 bits can then be converted back to a hexadecimal number, which is 1c as shown in the hex of the last 5 bits field218. Thus the bit indexed by 1c in the index field204is set in the value field of the abbreviated index202. As illustrated, continuing this process for each of the parameter patterns in the parameter patterns field210results in the element in the value field206corresponding to the index numbers of 3, 5, 9, d, 11, 15, 16, 18, 1c, and 1f in the index field204of the abbreviated index202are set. Notably, the abbreviated index202includes a sampling of representations that can be maintained by the abbreviated index.

The abbreviated index202can then be used at a later time to determine the probability that a parameter pattern is represented in a data store. A check of the abbreviated index202can be made for the parameter pattern. This can be done by hashing the parameter pattern, and in this case, checking the last 5 bits of the hash as an identifier for the parameter pattern to see if the identifier appears in the abbreviated index202. If it does not appear in the abbreviated index, it can be determined with 100% accuracy that the particular parameter pattern does not exist in the data store. However, if the identifier is in the abbreviated index202it is known, in this example, that there is about a 50% chance that the parameter pattern appears in the data store. This confidence can be increased by searching of related parameter patterns or making the abbreviated index array larger and more sparse. For example, if the search term entered by a user is “quick red fox,” confidence can be increased by checking the abbreviated index202for indicators for “quick,” “quick red,” “red fox,” “red,” etc.

Sub-microsearches may also be performed on a full index of the data store. This can be performed either by searching for individual terms or by searching for combinations of terms that have been indexed in the index.

When using a full index, it may be helpful to augment the index with an offset correlation table. Offset correlation tables are described in more detail in U.S. patent application Ser. No. 11/847,688 titled “Vortex Searching”, filed concurrently herewith, and incorporated herein by reference in its entirety. In one embodiment, an offset correlation table correlates portions of hashes for parameter patterns, such as the top given number of bits, with actual records where the parameter patterns may be found. Additionally, entries in the offset correlation table may indicate that no records are included in a data store for a particular portion of a hash.

Using the sub-microsearches, microsearches can be eliminated from the templates, so as to eliminate irrelevant or less relevant microsearches. Microsearches that have not been eliminated by the sub-microsearch searches can be used to provide results for the query104. Notably, typically the system described herein will provide a given number of results rather than providing all possible results. Further, it is desirable that the most relevant results be returned. Thus, in one embodiment, the weighting described above is used to determine which microsearches should be searched first. Microsearches with a weight that indicates that they are more relevant will be searched before microsearches with weights indicating that they are comparatively less relevant.

A rareness table for each search element can be defined to help determine the most efficient patterns to be used for a given microsearch. One use would be to select the order of microsearches in such a way as to maximize elisions, hence avoiding some future microsearches altogether.

For example, suppose the query is to find Fauntleroy Fontinelli born in Wyoming in 1910 and dying in New York in 1970. A very inexpensive table lookup could determine that both the name and the state Wyoming are rare. Hence the pattern searches could be divided on the first (possibly) exact search to both include the name and birth state. For example one pattern search could be for Fauntleroy Fontinelli born in Wyoming in 1910 and the other could be the exact search with all elements specified. If no hits were retrieved for either, then the second search could check the abbreviated pattern index for the pattern of Fauntleroy Fontinelli born in Wyoming “near 1910” with a good probability that there will be no hits. If none, then there is no need for performing microsearches for any of the nearby birth years.

In the preceding, the concept of nearness has been introduced. While nearness will be discussed in more detail below in conjunction with the description ofFIG. 3, certain principles will now be explained. Indexes may include entries for nearness. Additionally, the nearness can be quantified. Thus for example, 1911 and 1909 have the same nearness value to 1910 and are nearer to 1910 than 1912 and 1908. Thus, an index may include index entries for 1910_near—1 and 1910_near—2. Nearness can be defined in many different contexts. For example, as will be discussed in more detail below, nearness can be defined numerically, spatially, geographically, linguistically, etc.

One implementation of a rareness table would be a bit map for each possible element in a given search. This would work best for an element of finite range. Again using the U.S. state as an example, 9 states comprise 50% of the U.S. population (CA, TX, NY, FL, IL, PA, OH, MI, GA). Nine more states comprise the next quarter of the population, seven more the next eighth, and 25 the last eighth. Thus, a table with only two bits allocated per state could keep track the four degrees of rareness (or frequency) of being in the lower eighth, next eighth, next quarter, or upper half. In this example, a more useful table might be simply a one-bit table recording whether or not the state is common (upper 75%) or not (lower 25%). If the only use of this table is to determine how to divide up pattern searches, then a simple bit table might suffice.

In the case of many possible values for an element, one could extend the rareness table and base it on a ratio other than two. For example, with three bits per element (eight table values) and a base of four, one could partition the space into regions of the upper ¾, next 3/16th (42), next 3/64th (43), next 3/256th (44), next 3/1,024th (45), next 3/4096th (46), next 3/16,384th (47), and lowest 1/16,384th.

Notably, microsearches will not necessarily be completed for a single template before microsearches from adjacent or other templates are searched. For example,FIG. 1Billustrates that template110includes microsearches with weights between 87 and 79. Template112includes microsearches with weights between 85 and 77. Thus, when microsearches with weights of 85 from the first template110are being searched, it may be desireable to also enumerate microsearches from the second template112and to possibly perform additional sub-microsearches to eliminate microsearches from the second template such that microsearches from the second112, and eventually other subsequent templates, may be interleaved with microsearches from the first template110by weight as appropriate.

An example of this is illustrated inFIG. 1D.FIG. 1Dillustrates an example where templates110and112have had microsearches enumerated and interleaved together. Further, while, for convenience, only templates110and112have been shown as having enumerated microsearches interleaved, it should be appreciated that in practice a number of templates may have all or a portion of their microsearches enumerated and interleaved. For example, consider that a third template with a weight range of 83-75. Thus, template110has a weight range of 87-79, template112has a weight range of 85-77, and the third template has a weight range of 83-75. As microsearches from template110are enumerated where their weights approach a weight of 85, microsearches from template112will begin to be enumerated and interleaved with the microsearches enumerated for template110. Further, as weights of microsearches enumerated from template110and112approach 83, microsearches from the third template will begin to be enumerated and interleaved with the microsearches enumerated from templates110and112. As can be appreciated, this process can be continued with other templates which have overlapping weights.

It is appropriate to note at this point that previously performed sub-microsearches may be used to eliminate searches from subsequent templates. For example, the results of the sub-microsearch illustrated above that was used to eliminate microsearches with Cambridge from the first template110may likewise be used to eliminate microsearches from the second template112. Similarly, in some embodiments, previous results may be used to eliminate entire templates.

Referring now toFIG. 3, a method300is illustrated. The method300illustrates a method that may be performed in a computing environment including a data store. The data store includes data items stored in records in the data store. The method includes acts for searching a data store for parameter patterns specified in a query. The method includes receiving a query from a user including N parameter patterns (act302). For example,FIG. 1Aillustrates a query104including a number of parameter patterns being received.

The method300further includes associating one or more alternatives to one or more of the N parameter patterns (act304). An example of this is illustrated inFIG. 1Awherein an alternatives association module associates alternatives with the parameter patterns submitted in the query104.

The method300further includes creating one or more templates (act306). Each of the templates describes a number of microsearches where each of the microsearches includes one or more of the N parameter patterns or the alternatives. For example,FIG. 1Billustrates where parameter patterns alternatives108are supplied to a template generation module106. The template generation module106uses the parameter patterns and alternatives108to generate a number of templates such as templates110,112, and114.

As described previously, the method300may further include assigning weights to each of the parameter patterns specified in the query104and to each of the alternatives. Microsearches have weights based on the weights assigned to parameter patterns and/or alternatives in the microsearch. Based on the assigned weights, a weight range for may be determined for one or more of the templates. This weight range may be used for several functions including determining when to generate templates and when to enumerate microsearches.

As alluded to above, the method300further includes enumerating microsearches described by at least one of the one or more templates (act308).FIG. 1Cillustrates the enumeration of microsearches from a template such as template110. Notably, in some embodiments all possible microsearches may be enumerated at a given time, all microsearches may be enumerated for one or more templates at a given time, or alternatively microsearches may be enumerated when needed.

In one embodiment, the act of enumerating microsearches is performed for a template in response to weights for microsearches being searched, as is described below in conjunction with the description of act314, from an adjacent or other template approaching a weight range of the template. For example, reference is made toFIG. 1B.FIG. 1Billustrates the template110that has a weight range of 87-79. An adjacent template, template112has a weight range of 85-77. Thus, in one embodiment, when searches for microsearches with weights approaching or at 85 are being or have been performed, microsearches from the template112can be begun to be enumerated and searched as appropriate with the microsearches from the template110. For example, microsearches from different templates can be interleaved with one another.

Further, in some embodiments creating one or more templates may include creating templates on basis as needed to allow for a determination to be made that weights for microsearches being searched are approaching a weight range of the template. However, in some alternative embodiments, creating one or more templates may include creating all templates prior to performing one or more microsearches.

Returning once again toFIG. 3,FIG. 3illustrates that the method300further includes an act of performing one or more sub-microsearches (act310). This may be done by searching for parameter patterns and/or alternatives where each sub-microsearch has less than all terms needed for a full microsearch. For example, as illustrated above, a sub-microsearch for template110may be Kennedy Cambridge. Notably, while a sub-microsearch may be a full microsearch in some templates, it may nonetheless be a sub-microsearch as to microsearches in other templates.

In one embodiment, performing one or more sub-microsearches may include searching an index for parameter patterns and/or alternatives. As discussed previously, various indexes may be used. In one embodiment, the index is an abbreviated index. For example, an abbreviated index, such as the abbreviated index illustrated inFIG. 2may be used.

Embodiments may be implemented where searching an index comprises searching for index entries that index combinations of parameter patterns and/or alternatives. For example, an abbreviated index or full index of a data store may include single entries for combinations of parameter patterns. As noted previously, alternatives are also parameter patterns even though they are not specifically enumerated in a query. Thus, for example, an abbreviated index may include a bit which indexes the combination of Kennedy and Boston. Additionally, the index may have an absence of an indicator where Kennedy and Cambridge should be indexed. An absence of the combination may be used as one indicator for determining if microsearches should be eliminated from further searching of a data store. Other embodiments may search for individual terms of a sub-microsearch either in an abbreviated index or other index.

Searching an index may include searching for index entries that index ranges of parameter patterns and/or alternatives. For example, the indexed space can be divided into three separate areas: an exact hit, near hit (which includes the exact hit) and not near hit. A separate indexed hash entry in an offset correlation table or an abbreviated index can be made for the both the exact hit and the near hit.

Near can be defined in a variety of ways. One way is to define it in an absolute manner, independent of the data store and ranking algorithm. For example, a “near” state of the United States could be defined as any adjacent state to the exact hit state. A second way would be to define it based on a given data store, but independent of the ranking algorithm, and a third way would be to define “near” in terms also of the ranking algorithm which is employed. This latter might be a more logical choice in the case of a fixed ranking algorithm which implicitly defines “near” by giving higher rank to hits within a well defined “near” space. For example, if the ranking algorithm gives points for years within five years of the year requested, then one could define nearness of year to be within five years. Note that such a definition is not required. Note that nearness is not limited to numerical or spatial nearness, but may also include other forms of nearness such as linguistic nearness. One example of linguistic nearness relates to similarities between words. For example, nearness may be defined such that words that are more synonymous are nearer to each other. In another example, nearness may be defined based on the amount of misspelling of a word as compared to the word. Nearness may be defined in terms of similarity of pronunciations of the words. Nearness may be defined based on how common a nickname is for a particular given name. Other examples of nearness may also be implemented with the scope of the embodiments described herein.

While examples of determining nearness have been provided herein, it should be appreciated that other calculations and methods of determining nearness may be implemented within the scope of embodiments claimed herein. Any appropriate ranges described or defined by any appropriate systematic methodology may be used. Methodologies may be those expressible by computer executable algorithm, recursive partial function, or otherwise. Additionally, virtually any methodology generally recognized as a methodology for computation or description of proximity, distance, or metric between entities may be used.

The not near hit would be defined by the absence of both the exact hit and the near hit in either the offset correlation table or the abbreviated index.

For example, a search may be performed where the ranges include numeric proximity ranges. Illustratively, an index may include entries which include ranges of years indexed with other parameter patterns. Further, as illustrated above, the ranges may include geographic proximity ranges. Other ranges may also be included such as linguistic proximity ranges. Linguistic proximity ranges may index synonyms, homonyms, antonyms, or other language characteristics.

Referring once again toFIG. 3, the method300further illustrates based on the results of the one or more sub-microsearches, eliminating one or more microsearches from searching (act312) As has been illustrated previously, the results of the sub-microsearches can be used to eliminate microsearches. For example, as illustrated above, if Kennedy Cambridge is not found in a sub-microsearch, then all microsearches with the parameter pattern Cambridge can be eliminated from searching.

The method300further includes searching the data store using one or more of the remaining microsearches (act314). In one embodiment, searching the data store using one or more of the remaining microsearches is performed until a predetermined condition is satisfied. For example, the predetermined condition may include finding a prespecified number of records that satisfy the query. Satisfying the query may include finding a record for a microsearch.