High-efficiency selection of runtime rules for programmable search

This application is a continuation application claiming priority to Ser. No. 13/547,171, filed Jul. 12, 2012.

The present invention relates to computerized programmable search engines.

Integrating programmable search technology into a computer search engine can greatly increase the quality of search results, but may reduce performance and result in inefficient use of resources.

A first embodiment of the present invention provides a method for the efficient selection of runtime rules for programmable search, said method comprising:

a processor of a computer system translating a plurality of runtime rules into a plurality of fielded documents, wherein a first runtime rule of said plurality of runtime rules comprises a first rule pattern and a first rewrite pattern, wherein said first rule pattern comprises a first set of tokens of a plurality of tokens, and wherein a first fielded document of said plurality of fielded documents comprises said first set of tokens;

said processor partitioning said plurality of fielded documents into a plurality of disjoint clusters of fielded documents;

said processor converting a first cluster of said plurality of disjoint clusters into a first inverted index of a plurality of inverted indices, wherein said first inverted index associates a first token comprised by said first cluster with a related subset of fielded documents of said first cluster, and wherein a fielded document of said related subset comprises said first token;

said processor generating a set of fielded queries as a function of an input query and as a function of said plurality of inverted indices, wherein said set of fielded queries satisfies a set of conditions;

said processor selecting a set of candidate rules of said plurality of runtime rules as a function of said set of fielded queries and of said plurality of inverted indices;

said processor selecting a set of applicable rules of said plurality of runtime rules by matching said set of candidate rules against said input query.

A second embodiment of the present invention provides a computer program product, comprising a computer-readable hardware storage device having a computer-readable program code stored therein, said program code configured to be executed by a processor of a computer system to implement a method for the efficient selection of runtime rules for programmable search, said method comprising:

said processor translating a plurality of runtime rules into a plurality of fielded documents, wherein a first runtime rule of said plurality of runtime rules comprises a first rule pattern and a first rewrite pattern, wherein said first rule pattern comprises a first set of tokens of a plurality of tokens, and wherein a first fielded document of said plurality of fielded documents comprises said first set of tokens;

said processor partitioning said plurality of fielded documents into a plurality of disjoint clusters of fielded documents;

said processor converting a first cluster of said plurality of disjoint clusters into a first inverted index of a plurality of inverted indices, wherein said first inverted index associates a first token comprised by said first cluster with a related subset of fielded documents of said first cluster, and wherein a fielded document of said related subset comprises said first token;

said processor generating a set of fielded queries as a function of an input query and as a function of said plurality of inverted indices, wherein said set of fielded queries satisfies a set of conditions;

said processor selecting a set of candidate rules of said plurality of runtime rules as a function of said set of fielded queries and of said plurality of inverted indices;

said processor selecting a set of applicable rules of said plurality of runtime rules by matching said set of candidate rules against said input query.

A third embodiment of the present invention provides a computer system comprising a processor, a memory coupled to said processor, and a computer-readable hardware storage device coupled to said processor, said storage device containing program code configured to be run by said processor via the memory to implement a method for the efficient selection of runtime rules for programmable search, said method comprising:

said processor translating a plurality of runtime rules into a plurality of fielded documents, wherein a first runtime rule of said plurality of runtime rules comprises a first rule pattern and a first rewrite pattern, wherein said first rule pattern comprises a first set of tokens of a plurality of tokens, and wherein a first fielded document of said plurality of fielded documents comprises said first set of tokens;

said processor partitioning said plurality of fielded documents into a plurality of disjoint clusters of fielded documents;

said processor converting a first cluster of said plurality of disjoint clusters into a first inverted index of a plurality of inverted indices, wherein said first inverted index associates a first token comprised by said first cluster with a related subset of fielded documents of said first cluster, and wherein a fielded document of said related subset comprises said first token;

said processor generating a set of fielded queries as a function of an input query and as a function of said plurality of inverted indices, wherein said set of fielded queries satisfies a set of conditions;

said processor selecting a set of candidate rules of said plurality of runtime rules as a function of said set of fielded queries and of said plurality of inverted indices;

said processor selecting a set of applicable rules of said plurality of runtime rules by matching said set of candidate rules against said input query.

A fourth embodiment of the present invention provides a process for supporting computer infrastructure, said process comprising providing at least one support service for at least one of creating, integrating, hosting, maintaining, and deploying computer-readable program code in a computer system, wherein the program code in combination with said computer system is configured to implement a method for the efficient selection of runtime rules for programmable search, said method comprising:

said processor translating a plurality of runtime rules into a plurality of fielded documents, wherein a first runtime rule of said plurality of runtime rules comprises a first rule pattern and a first rewrite pattern, wherein said first rule pattern comprises a first set of tokens of a plurality of tokens, and wherein a first fielded document of said plurality of fielded documents comprises said first set of tokens;

said processor partitioning said plurality of fielded documents into a plurality of disjoint clusters of fielded documents;

said processor converting a first cluster of said plurality of disjoint clusters into a first inverted index of a plurality of inverted indices, wherein said first inverted index associates a first token comprised by said first cluster with a related subset of fielded documents of said first cluster, and wherein a fielded document of said related subset comprises said first token;

said processor generating a set of fielded queries as a function of an input query and as a function of said plurality of inverted indices, wherein said set of fielded queries satisfies a set of conditions;

said processor selecting a set of candidate rules of said plurality of runtime rules as a function of said set of fielded queries and of said plurality of inverted indices;

said processor selecting a set of applicable rules of said plurality of runtime rules by matching said set of candidate rules against said input query.

FIG. 1 shows the structure of a computer system and computer program code that may be used to implement a method for the efficient selection of runtime rules for programmable search in accordance with embodiments of the present invention.

FIG. 2 shows relationships among data structures that are generated as a programmable search engine implements an embodiment of the method of the present invention.

FIG. 3 is a flow chart that illustrates the steps of a method for the efficient selection of runtime rules for programmable search in accordance with embodiments of the present invention.

FIG. 4 is a flow chart that elaborates the step of sequence enumeration described in FIG. 3 , step 307, in accordance with embodiments of the present invention.

Programmable search engines may use “runtime rules” to infer the intended meaning of user-submitted input queries. Each runtime rule attempts to match character strings (or “tokens”) comprised by a freeform query against a “rule pattern” specific to that rule. If a match is found, the rule then rewrites the query in a more easily analyzed format defined by a corresponding “rewrite pattern.”

This matching function may be resource-intensive, so if a programmable search engine comprises a large number of rules, the engine's performance may depend upon how efficiently the engine selects rules it attempts to match against a query.

The present invention is a system and method for efficiently selecting a candidate set of runtime rules that are likely to match a user query. This selection comprises partitioning a runtime rule set into optimized clusters as a function of their relationships to certain parameters and conditions. When analyzed in conjunction with parameters of an input query, these clusters allow a programmable search engine to identify an optimized subset of potentially applicable candidate rules, thus reducing the number of rules that must be matched against the query.

This invention may be implemented as a method performed by a processor of a computer system, as a computer program product, as a computer system, or as a processor-performed process or service for supporting computer infrastructure.

FIG. 1 shows the structure of a computer system and computer program code that may be used to implement a method for the efficient selection of runtime rules for programmable search in accordance with embodiments of the present invention. FIG. 1 refers to objects 101 - 115 .

Aspects of the present invention may take the form of an entirely hardware embodiment, an entirely software embodiment (including firmware, resident software, micro-code, etc.) or an embodiment combining software and hardware aspects that may all generally be referred to herein as a “circuit,” “module,” or “system.” Furthermore, in one embodiment, the present invention may take the form of a computer program product comprising one or more physically tangible (e.g., hardware) computer-readable medium(s) or devices having computer-readable program code stored therein, said program code configured to be executed by a processor of a computer system to implement the methods of the present invention. In one embodiment, the physically tangible computer readable medium(s) and/or device(s) (e.g., hardware media and/or devices) that store said program code, said program code implementing methods of the present invention, do not comprise a signal generally, or a transitory signal in particular.

Any combination of one or more computer-readable medium(s) or devices may be used. The computer-readable medium may be a computer-readable signal medium or a computer-readable storage medium. The computer-readable storage medium may be, for example, but is not limited to, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, or device, or any suitable combination of the foregoing. More specific examples (a non-exhaustive list) of the computer-readable storage medium or device may include the following: an electrical connection, a portable computer diskette, a hard disk, a random access memory (RAM), a read-only memory (ROM), an erasable programmable read-only memory (EPROM or flash memory), Radio Frequency Identification tag, a portable compact disc read-only memory (CD-ROM), an optical storage device, a magnetic storage device, or any suitable combination of the foregoing. In the context of this document, a computer-readable storage medium may be any physically tangible medium or hardware device that can contain or store a program for use by or in connection with an instruction execution system, apparatus, or device.

A computer-readable signal medium may include a propagated data signal with computer-readable program code embodied therein, for example, a broadcast radio signal or digital data traveling through an Ethernet cable. Such a propagated signal may take any of a variety of forms, including, but not limited to, electro-magnetic signals, optical pulses, modulation of a carrier signal, or any combination thereof.

Program code embodied on a computer-readable medium may be transmitted using any appropriate medium, including but not limited to wireless communications media, optical fiber cable, electrically conductive cable, radio-frequency or infrared electromagnetic transmission, etc., or any suitable combination of the foregoing.

Computer program code for carrying out operations for aspects of the present invention may be written in any combination of one or more programming languages, including, but not limited to programming languages like Java, Smalltalk, and C++, and one or more scripting languages, including, but not limited to, scripting languages like JavaScript, Perl, and PHP. The program code may execute entirely on the user's computer, partly on the user's computer, as a stand-alone software package, partly on the user's computer and partly on a remote computer, or entirely on the remote computer or server. In the latter scenario, the remote computer may be connected to the user's computer through any type of network, including a local area network (LAN), a wide area network (WAN), an intranet, an extranet, or an enterprise network that may comprise combinations of LANs, WANs, intranets, and extranets, or the connection may be made to an external computer (for example, through the Internet using an Internet Service Provider).

Aspects of the present invention are described above and below with reference to flowchart illustrations and/or block diagrams of methods, apparatus (systems) and computer program products according to embodiments of the present invention. It will be understood that each block of the flowchart illustrations, block diagrams, and combinations of blocks in the flowchart illustrations and/or block diagrams of FIGS. 1-4 can be implemented by computer program instructions. These computer program instructions may be provided to a processor of a general purpose computer, special purpose computer, or other programmable data-processing apparatus to produce a machine, such that the instructions, which execute via the processor of the computer or other programmable data-processing apparatus, create means for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks.

These computer program instructions may also be stored in a computer-readable medium that can direct a computer, other programmable data-processing apparatus, or other devices to function in a particular manner, such that the instructions stored in the computer-readable medium produce an article of manufacture, including instructions that implement the function/act specified in the flowchart and/or block diagram block or blocks.

The computer program instructions may also be loaded onto a computer, other programmable data-processing apparatus, or other devices to cause a series of operational steps to be performed on the computer, other programmable apparatus, or other devices to produce a computer-implemented process such that the instructions that execute on the computer or other programmable apparatus provide processes for implementing the functions/acts specified in the flowchart and/or block diagram block or blocks.

The flowchart illustrations and/or block diagrams FIGS. 1-4 illustrate the architecture, functionality, and operation of possible implementations of systems, methods and computer program products according to various embodiments of the present invention. In this regard, each block in the flowchart or block diagrams may represent a module, segment, or portion of code, wherein the module, segment, or portion of code comprises one or more executable instructions for implementing one or more specified logical function(s). It should also be noted that, in some alternative implementations, the functions noted in the block may occur out of the order noted in the figures. For example, two blocks shown in succession may, in fact, be executed substantially concurrently, or the blocks may sometimes be executed in the reverse order, depending upon the functionality involved. It will also be noted that each block of the block diagrams and/or flowchart illustrations, and combinations of blocks in the block diagrams and/or flowchart illustrations, can be implemented by special-purpose hardware-based systems that perform the specified functions or acts, or combinations of special-purpose hardware and computer instructions.

In FIG. 1 , computer system 101 comprises a processor 103 coupled through one or more I/O Interfaces 109 to one or more hardware data storage devices 111 and one or more I/O devices 113 and 115 .

Hardware data storage devices 111 may include, but are not limited to, magnetic tape drives, fixed or removable hard disks, optical discs, storage-equipped mobile devices, and solid-state random-access or read-only storage devices. I/O devices may comprise, but are not limited to: input devices 113 , such as keyboards, scanners, handheld telecommunications devices, touch-sensitive displays, tablets, biometric readers, joysticks, trackballs, or computer mice; and output devices 115 , which may comprise, but are not limited to printers, plotters, tablets, mobile telephones, displays, or sound-producing devices. Data storage devices 111 , input devices 113 , and output devices 115 may be located either locally or at remote sites from which they are connected to I/O Interface 109 through a network interface.

Processor 103 may also be connected to one or more memory devices 105 , which may include, but are not limited to, Dynamic RAM (DRAM), Static RAM (SRAM), Programmable Read-Only Memory (PROM), Field-Programmable Gate Arrays (FPGA), Secure Digital memory cards, SIM cards, or other types of memory devices.

At least one memory device 105 contains stored computer program code 107 , which is a computer program that comprises computer-executable instructions. The stored computer program code includes a program that implements a method for the efficient selection of runtime rules for programmable search in accordance with embodiments of the present invention, and may implement other embodiments described in this specification, including the methods illustrated in FIGS. 1-4 . The data storage devices 111 may store the computer program code 107 . Computer program code 107 stored in the storage devices 111 is configured to be executed by processor 103 via the memory devices 105 . Processor 103 executes the stored computer program code 107 .

Thus the present invention discloses a process for supporting computer infrastructure, integrating, hosting, maintaining, and deploying computer-readable code into the computer system 101 , wherein the code in combination with the computer system 101 is capable of performing a method for the efficient selection of runtime rules for programmable search.

Any of the components of the present invention could be created, integrated, hosted, maintained, deployed, managed, serviced, supported, etc. by a service provider who offers to facilitate a method for the efficient selection of runtime rules for programmable search. Thus the present invention discloses a process for deploying or integrating computing infrastructure, comprising integrating computer-readable code into the computer system 101 , wherein the code in combination with the computer system 101 is capable of performing a method for the efficient selection of runtime rules for programmable search.

One or more data storage units 111 (or one or more additional memory devices not shown in FIG. 1 ) may be used as a computer-readable hardware storage device having a computer-readable program embodied therein and/or having other data stored therein, wherein the computer-readable program comprises stored computer program code 107 . Generally, a computer program product (or, alternatively, an article of manufacture) of computer system 101 may comprise said computer-readable hardware storage device.

FIG. 2 shows relationships among data structures that are generated as a programmable search engine implements an embodiment of the method of the present invention. FIG. 2 shows elements identified by reference numbers 201 - 215 .

Reference number 201 shows a rule set R of i runtime rules r i , wherein i is a positive integer. Each runtime rule is of the form H 1 H 2 , wherein H 1 is an antecedent hedge expression and H 2 is a consequent hedge expression.

As used herein, the term “hedge” refers to a data structure that comprises an ordered set of binary trees. Each binary tree in such a hedge comprises nodes that each identify a “term” token or a “concept” token. As used herein, a “hedge expression” is a type of hedge that may further comprise nodes that each identifies a “variable” token. The simplest nontrivial example of a hedge expression comprises a single term token.

Concept tokens identify conceptual entities that may be matched to sets of associated keywords (or strings of characters). A “COUNTRY” concept, for example, may be defined to match elements of the set {“America”, “India”, “Kenya”}.

Term tokens match keywords or strings of characters. “Kenya,” “uranium,” “telephone,” and “news” are all term tokens that may match identical tokens in a user query.

Variable tokens comprise label variable tokens and hedge variable tokens. A label variable token may match a term or a concept and a hedge variable token may match a hedge. Queries cannot contain variables, but a rule pattern that comprises a variable may match that variable against a term or concept token comprised by a query.

Some embodiments may comprise different token categories, different definitions of each token category, and different definitions of the ways that tokens in each category may be used to match tokens of an input query. The embodiments of FIGS. 1-4 describe programmable search engines that comprise concept, term, and variable tokens, but other embodiments may apply analogous methods to search engines that comprise other types of tokens.

In embodiments of the present invention, a runtime rule comprises an ordered pair of hedge expressions known as an antecedent “rule pattern” and a consequent “rewrite pattern.” Each rule pattern and each rewrite pattern may comprise binary trees that in turn comprise nodes that may each be a concept token, a term token, or a variable token, as described above. A binary tree may contain a single node.

A runtime rule's hedge expressions comprise implicit logic that may be expressed as a function that rewrites all or part of a query that matches the form of the rule's rule pattern into the form of the rule's rewrite pattern. This rewriting may comprise attempting to match patterns of tokens in the query against patterns of tokens in the runtime rule's rule pattern and then, if a match is found, rewriting the matched tokens into a form defined by the runtime rule's rewrite pattern. Such rules allow programmable search engines to identify a pattern of tokens in a user query 209 and then rewrite that pattern in a more easily analyzed standard form. In other embodiments, a runtime rule may perform other types of actions upon an input query 209 , may have a different structure, or may perform different types of functions.

In an example, a programmable search engine may comprise a “COUNTRY” concept that may match tokens of the set {“America”, “India”, “Kenya”}, a “FN” concept that may match tokens of the set {“find”, “distance”, “map”, and “route”}, and a runtime rule: “FN COUNTRY location COUNTRY”.

Here, the runtime rule's rule pattern “FN COUNTRY” comprises two concept tokens and the runtime rule's rewrite pattern “location COUNTRY” comprises a “location” term token and a “COUNTRY” concept token.

A query that consists of the string “map America” would match the runtime rule's rule pattern, by matching the query's “map” token to the rule pattern's “FN” concept token and by matching the query's “America” token to the rule pattern's “COUNTRY” concept token. The runtime rule would then rewrite the matched pattern in the form of its rewrite rule, producing the rewritten query “location America.” In a real-world implementation, this rewritten query would be in a form that would be easier to parse or that would possess implicit semantic information.

Reference number 203 shows a set of fielded documents, each of which is extracted from one rule pattern of one runtime rule of the set of runtime rules 201 . A fielded document for a rule r i in R 201 comprises a set of fields that identify all tokens comprised by a rule pattern comprised by rule r i . In the embodiment of FIGS. 1-4 , a fielded document for a rule r i would contain three fields that respectively identify the concept tokens, term tokens, and variable tokens that comprise the rule pattern of rule r i . The order of these three fields may vary in some embodiments, but must be consistent among all fielded documents in a single set of fielded documents 203 .

In an example, a fielded document fd i associated with runtime rule r i might be of the form {t c , t t , t v }, wherein field t c lists concept tokens comprised by the rule pattern of runtime rule r i , field t t lists term tokens comprised by the rule pattern of runtime rule r i , and field t v lists variable tokens comprised by the rule pattern of runtime rule r i . A runtime rule

that comprises rule pattern “FN COUNTRY,” which in turn comprises concept tokens “FN” and “COUNTRY,” no term tokens, and no variable tokens, would thus be associated with fielded document

fd i ={(concept:FN, concept:COUNTRY), ( ), ( )}.

Reference number 205 shows a set of clusters of fielded documents that is produced from the set of fielded documents 203 by the partitioning procedure of FIG. 3 step 303 . In some embodiments, rule set 201 may be partitioned in an analogous manner into a set of clusters of rewrite rules, either in addition to or in place of the partitioning of the set of fielded documents of step 303 .

In embodiments described in FIGS. 1-4 , the set 205 of clusters of fielded documents comprises all fielded documents comprised by the set 203 of fielded documents. In other embodiments, the set 205 of clusters of fielded documents may comprise a proper subset of all fielded documents of the set 203 of fielded documents.

Each cluster of the set of clusters 205 is associated with a set of derived boundary variables. These boundary variables may be expressed using a “length” operator |, wherein the length of an entity S is equal to the number of tokens comprised by entity S, and wherein a length of entity S is expressed as |S|. If, for example, Concepts(r i ) is the set of all concept tokens in the rule r i described above, then |Concepts(r i )|=2 because rule r i as described above contains the two concept tokens FN and COUNTRY.

In embodiments described in FIGS. 1-4 , the length of a rule pattern comprised by a runtime rule r i is generally identical to the length of a fielded document fd i extracted from runtime rule r i by the procedure of FIG. 3 , step 301 because the number of tokens comprised by the rule pattern of r i is identical to the number of tokens comprised by r i 's analogous fielded document fd i .

By convention, we define Concepts(r i ) to be the set of all concept tokens in a rule r i , Terms(r i ) to be the set of all term tokens in a rule r i , and Variables(r i ) to be a set of all variable tokens in a rule r i . By convention, we further define Concepts(fd i ) to be the set of all concept tokens in a fielded document fd i that corresponds to a rule r i , Terms(fd i ) to be a set of all term tokens in the fielded document fd i , and Variables(fd i ) to be a set of all variable tokens in the fielded document fd i .

Using these conventions, the boundary variables for a cluster of fielded documents C i may comprise:

MIN c.i and MAX c.i , wherein MAX c.i is the greatest value of |Concepts(fd m )| for any fielded document fd m in cluster C i and MIN c.i is the smallest value of |Concepts(fd n )| for any fielded document fd n in cluster C i ; MK t.i and MAX t,i , wherein MAX t,i is the greatest value of |Terms(fd m )| for any fielded document fd m in cluster C i and MIN t.i is the smallest value of |Terms(fd n )| for any fielded document fd n in cluster C i ; MIN v.i and MAX v.i , wherein MAX v.i is the greatest value of |Variables(fd m )| for any fielded document fd m in cluster C i and MIN v.i is the smallest value of |Variables(fd n )| for any fielded document fd n in cluster C i ; NS L.i , wherein NS l.i =MIN c.i +MIN t.i +MIN v.i ; and NS u.i , wherein NS u.i is the total length of a fielded document fd min of cluster C i , and wherein no fielded document of cluster C i has a total length less than |fd min |.

In less formal terms, MIN c.i and MAX c.i identify the lower and upper limits of the number of concept tokens contained in any fielded document of cluster C i . Min t.i and Max t.i identify analogous limits for the numbers of terms in any single fielded document of cluster C i , and Min v.i , and Max v.i identify analogous boundaries for the number of variables in any single fielded document of cluster C i .

The six fielded documents whose lengths are identified by the Min and Max variables described above may not be distinct, but all six must be contained in the same cluster C i . A distinct set of six Min and Max variables may be defined for each cluster in the set 205 of clusters of fielded documents.

NS l.i identifies the smallest possible number of tokens in a theoretical fielded document that may be assembled from all concept tokens in a first fielded document of C i , all term tokens in a second fielded document of C i , and all variable tokens in a third fielded document of C i , wherein the first, second, and third fielded documents may not be distinct.

NS u.i identifies the length of the shortest fielded document fd min of C i , wherein no fielded document of C i contains fewer tokens than does fd min .

In an example that illustrates how these boundary variables may be determined, consider a cluster C i that comprises four fielded documents (fd1, fd2, fd3, fd4), wherein each fielded document may contain concept tokens c, term tokens t, and variable tokens v. C i thus might comprise:

The variables associated with this cluster C, of fielded documents might thus be derived through the following steps:

|Concepts(fd1)|=2[c1, c2]

|Concepts(fd2)|=|Concepts(fd3)|=0

|Concepts(fd4)|=1 [c3]

|Terms(fd1)|=1 [t1]

|Terms(fd2)|=|Terms(fd3)|=|Terms(fd4)|=0

|Variables(fd1)|=0

|Variables(fd2)|=1[v1]

|Variables(fd3)|=2[v1, v2]

|Variables(fd4)|=0

MIN c.i =0 [fd2, fd3]; MIN t.i =0 [fd2,fd3,fd4]; MIN v.i =0[fd1, fd4]

MAX c.i =2 [fd1]; MAX t.i =1 [fd1]; MAX v.i =2 [fd3]

NS 1 =MIN c.i +MIN t.i +MIN v.i =0

NS u =|fd2|=|fd4|=1 [fd2 and fd4 are the shortest fielded documents of C i ]

Reference number 207 identifies a set of inverted indices, each of which corresponds to a cluster C i of the clusters of fielded documents 205 , and wherein cluster C i comprises fielded documents fd i,1 . . . fd i.m . Each inverted index comprises a set of lists, wherein each list in the set of lists corresponds to a token found in any of fielded documents fd i.1 . . . fd i.m that comprise cluster C i . A list that corresponds to a token t enumerates every fielded document in cluster C i that contains token t. In an embodiment, an inverted index for a cluster of fielded documents

fd i.1 . . . fd i.m must contain one list for every token found in any fielded document of the set of fielded documents fd i.1 . . . fd i.m .

In a preceding example, cluster C i , which comprises fielded documents fd1 . . . fd4, would correspond to an inverted index Ind i , wherein Ind i contains an ordered list for each concept token, term token, or variable token in any fielded document in cluster C i . Thus, in this example:

Ind i ={(concept:c1, fd1), (concept:c2, fd1), (concept:c3, fd4), (term:t1, fd1), (variable:v1, fd2, fd3), (variable:v2, fd3)}.

Reference number 209 identifies a submitted user query or input query Q 209 that comprises an arbitrary set of concept tokens and term tokens in an arbitrary format. In the embodiments of FIGS. 1-4 , an input query 209 cannot contain variable tokens.

Reference number 211 identifies a set of fielded queries, wherein each fielded query in the set of fielded queries 211 comprises an ordered sequence of subsets of tokens contained in both user query 209 and in an inverted index of the set of inverted indices 207 .

A fielded query that corresponds to a user query Q 209 and to an inverted index Ind i of the set of inverted indices 207 comprises a three-element sequence of sets of tokens Q′ c.i , Q′ t.i , Q′ v.i , wherein Q′ c.i is a subset of the set of concept tokens comprised by both query 209 and by inverted index Ind i , wherein Q′ t.i is a subset of the set of term tokens comprised by both query Q 209 and by Ind i , and wherein Q′ v.i is a subset of the set of variable tokens comprised by Ind i . Selection of token sets Q′ c.i , Q′ t.i , and Q′ v.i is further constrained by conditions and functions described in reference numeral 205 . In other embodiments, a fielded query may comprise other types of data that may be selected by other criteria.

The set of fielded queries 211 is thus comprises all possible ordered sequences of token sets (Q′ c.i , Q′ t.i , Q′ v.i ), wherein each sequence is associated with one inverted index Ind i of the set of inverted indices 207 , and wherein each said sequence satisfies conditions described in step 205 , in step 307 of FIG. 3 , and in FIG. 4 .

A set of fielded queries 211 is created through a “sequence enumeration” procedure that is performed once for each input query 209 . Each performance of a sequence enumeration procedure in turn comprises an iterative process of FIG. 4 (steps 405 - 409 ) that is performed once for each inverted index of a set of inverted indices 207 .

Reference number 213 identifies a set of candidate rules, which is a subset of rule set 201 and which comprises runtime rules that may be applicable to query Q. Candidate rules 213 are selected by matching the set of fielded queries 211 , which characterize query Q, against each index of the set of inverted indices 207 , and then merging the results for all indices in the set of inverted indices 207 into a single candidate rule set.

Reference number 215 identifies the subset of rule set 201 that comprises runtime rules that are applicable to input query Q 209 . This set of applicable rules 215 is determined by matching the set of candidate rules 213 to input query Q 209 .

FIG. 3 is a flow chart that illustrates the steps of a method for the efficient selection of runtime rules for programmable search in accordance with embodiments of the present invention. FIG. 3 contains steps 301 - 311 which may be performed by embodiments that incorporate the data structures of FIG. 2 . In these embodiments, a programmable search engine may perform steps 301 through 305 once for each runtime rule set R 201 and may perform steps 307 - 311 once for each input query 209 . Step 307 is described in greater detail in FIG. 4 .

In step 301 , a programmable search engine translates each runtime rule r i of a set of runtime rules ( 201 in FIG. 2 ) into a corresponding fielded document fd i of a set of fielded documents 203 . As explained in the examples and description of reference numeral 201 , each runtime rule r i comprises a pair of hedge expressions known as a rule pattern and a rewrite pattern, wherein each expression of the pair of hedge expressions comprises an ordered set of binary trees, and wherein each node of each binary tree comprises a concept token, a term token, or a variable token.

As explained in the description and examples of FIG. 2 , reference numeral 203 , each fielded document fd i is derived from the rule pattern hedge expression of a corresponding rule r i of rule set 201 and contains a set of fields that identify the tokens comprised by the rule pattern hedge expression of rule r i . In embodiments wherein rule r i comprises concept tokens, term tokens, and variable tokens, a fielded document fd i that corresponds to a rule r i may contain three fields that respectively enumerate the concept tokens, term tokens, and variable tokens that are comprised by rule r i .

In step 303 , the set of fielded documents 203 created in step 301 is partitioned into an optimized set of disjoint clusters of fielded documents 205 . In embodiments described in FIGS. 1-4 , the set 205 of clusters of fielded documents comprises all fielded documents of the set 203 of fielded documents. In other embodiments, the set 205 of clusters of fielded documents may comprise a proper subset of all fielded documents of the set 203 of fielded documents.

In some embodiments, step 303 may partition the set of runtime rules 201 into an analogous optimized set of disjoint clusters and, in such embodiments, subsequent steps of the method of the present invention that act upon clusters of fielded documents 205 instead perform analogous actions upon the clusters of rules.

In the embodiments described herein, the method of optimization comprised by step 303 may be a method of selecting a partitioning strategy that results in a lower total cost, wherein cost may be approximately inversely proportional to a number of applicable runtime rules 215 . In other embodiments, cost may be defined in other ways and optimization procedures may be chosen to satisfy other criteria.

The details of partitioning step 303 are implementation-dependent and are determined by a cost function SR that identifies the total cost of a particular choice of partitions, wherein each choice of partitions may comprise a particular division of a set of fielded documents 203 into a specific number of clusters, wherein each such cluster comprises a cluster-specific number of fielded documents, and wherein each such cluster comprises fielded documents that have lengths equal to or greater than the length of a minimum length-threshold value. Software engineers skilled in the art of search-engine design may use optimization techniques well-known in the art to implement the general implementation strategy of step 303 to select an optimal set of partitions.

A total cost function SR returns a total cost of partitioning a set 203 of fielded documents into a set 205 of k clusters of fielded documents C 1 , C 2 , . . . C k . A total cost SR is a sum of a set of a set of k individual cluster costs R i , wherein an individual cluster cost R i may be a function of parameters S i and u i , wherein S i is a number of fielded documents comprised by cluster C i , and wherein NS u.i is a length of a shortest fielded document in a cluster C i . In embodiments of the present invention, cost functions R i may be approximately proportional to S i and approximately inversely proportional to u i . In some embodiments, a cost function R i for a cluster C i may be as simple as R i =S i /u i or R i =(S i )**u i .

Given a particular choice of function R i , an optimal partitioning strategy may be identified as a partitioning strategy that results in the lowest value of a sum of a set of individual cluster costs R i for all clusters C i . In more formal terms, an optimal k-way partitioning strategy is a strategy that minimizes a total cost SR of searching through all k clusters by selecting from a set 203 of fielded documents or analogous runtime rules 201 an approximately smallest possible number of applicable runtime rules 215 :

In empirical testing, acceptable efficiencies have been observed and R i has been shown to be solvable in polynomial time when R i is chosen to be of the form:

R i =( S i +α)/ u i ,

wherein α is an implementation-dependent “penalty constant” that prevents a function R i from returning an unacceptably large number of unacceptably small clusters. The definition and use of penalty constants is well-known to those in skilled in fields of computer science and mathematics that are related to the present invention, such as machine learning and artificial intelligence, and to clustering methodologies like those of step 303 .

In an example, a rule set R x 201 comprised of 30 runtime rules r x might be translated by the procedure of FIG. 3 , step 301 , into a corresponding set of fielded documents FD x 203 , wherein FD x is comprised of 30 fielded documents fd x that are each analogous to one runtime rule r x .

In this example, a total cost function SR x computed for a partition of FD x into k clusters would return a value of a sum of a set of values of R 1 . . . R k , wherein each R i is a cost of one cluster C 1 . . . C k . If R i is defined as a function R i =(S i /u i ), wherein S i is a number of fielded documents contained in a cluster C i , and wherein u i is a length of a shortest fielded document in a cluster C i , numerical techniques well-known to those skilled in fields of computer science and mathematics related to the present invention may be used to select an optimal partitioning of the set of fielded documents FD x (and of its corresponding rule set R x ) into an optimized set of k clusters of fielded documents 205 , such that a corresponding value of total cost SR is minimized.

In an example wherein a desired number of clusters k is arbitrarily set to 4, a resulting optimal partition might result in an optimized set 205 of four clusters of fielded documents C 1 , C 2 , C 3 , C 4 . A minimum cost SR of this optimized partitioning is a lowest possible sum of costs R 1 , R 2 , R 3 , R 4 , wherein costs R 1 , R 2 , R 3 , R 4 are each associated with a corresponding cluster of the optimal set of clusters 205 C 1 , C 2 , C 3 , C 4 .

Other partitioning methods may not be optimal if they result in a higher value of SR. An optimal partitioning method is not unique for a particular rule set 201 because more than one set of partitions may result in a same minimum value of SR. In some embodiments, however, a minimum value of a cost SR may be identical for all rule sets R 201 that comprise a particular number of rules and a particular minimum rule-length and for all sets of fielded documents 205 that comprise the same particular number of rules and the same particular minimum rule-length.

In step 305 , each cluster of the set of clusters of fielded documents 205 is translated into one inverted index of the set of inverted indices 207 . As described in the description and examples of reference numeral 207 in FIG. 2 , an inverted index Ind, created from cluster C i , wherein cluster C i comprises fielded documents fd j . . . fd k , comprises a set of lists that each correspond to a token t contained in any of fielded documents fd j . . . fd k in cluster C i . As explained in the description and examples of step 207 , a list that corresponds to a token t, wherein token t is comprised by any fielded document comprised by cluster C i , enumerates every fielded document in cluster C i that comprises token t. In an embodiment, an inverted index associated with a cluster C i of fielded documents must contain one list for each token comprised by any fielded document of cluster C i .

A programmable search engine may performs steps 301 through 305 once for a runtime rule set 201 , but may perform steps 307 through 311 once each time a user submits a user input query 209 .

In step 307 , the programmable search engine translates an input query Q 209 into a set of fielded queries 211 as a function of the contents and embedded logic of a set of inverted indices 207 . This step is known as “sequence enumeration” and is further described in FIG. 4 .

In step 309 , a set of candidate runtime rules 213 is selected from rule set R 201 as a function of a set of inverted indices 207 , a set of fielded queries 211 , and a set of other conditions. This step may be implemented by procedures well-known to those skilled in the art of search-engine design.

In step 311 , the rules comprised by the set of candidate rules 213 are matched against input query 209 to determine a set of applicable rules 215 that are applicable to input query 209 . The programmable search engine will then use this set of applicable rules 215 to select search results for query 209 . This step may be implemented by procedures well-known to those skilled in the art of search-engine design.

FIG. 4 is a flow chart that elaborates the step of sequence enumeration described in FIG. 3 , step 307 , in accordance with embodiments of the present invention. FIG. 4 comprises steps 401 through 409 .

As described in FIG. 2 , reference numeral 211 , a fielded query associated with an input query Q 209 comprises an ordered sequence of three sets of tokens (Q′ c.i , Q′ t.i , Q′ v.i ), wherein a token of any of these three sets is comprised by input query Q 209 and wherein a token of any of these three sets is comprised by one inverted index Ind, of the set of inverted indices 207 , and wherein Q′ c.i is a set of concept tokens, Q′ t.i is a set of term tokens, and Q′ v.i is a set of variable tokens. All fielded queries must contain one set of concept tokens, one set of term tokens, and one set of variable tokens in a consistent, implementation-specific order.

The process of sequence enumeration comprises the creation of a set FQ of fielded queries 211 , wherein FQ comprises i subsets FQ i of fielded queries, and wherein each subset FQ i comprises a set of all possible ordered sequences s i for an inverted index Ind i of a set of inverted indices 207 . Each ordered sequence s i of a set FQ i of ordered sequences comprises an ordered sequence of a set Q′ c.i of concept tokens, a set Q′ t.i of term tokens, and a set Q′ v.i of variable tokens, wherein tokens comprised by Q′ c.i , Q′ t.i , and Q′ v.i are comprised by both inverted index Ind i and by input query Q 209 , and wherein each set FQ i of ordered sequences comprises a set of all possible ordered sequences that satisfy these conditions for Ind i and that may further satisfy additional conditions described in step 409 . Some or all sets of tokens Q′ c.i , Q′ t.i , and Q′ v.i identified by this process may be empty.

In step 401 , the programmable search engine receives an input query Q 209 . As described above, a query 209 may comprise concept tokens and term tokens, but may not comprise variable tokens.

In step 403 , the search engine identifies the elements of sets Q c and Q t , wherein Q c is the set of all concept tokens comprised by query 209 and Q t is the set of all term tokens comprised by a query 209 . In some embodiments, Q c may comprise a proper subset of the set of all concept tokens comprised by query 209 and Q t may comprise a proper subset of the set of all term tokens comprised by query 209 .

Step 405 initiates an iterative process that comprises steps 405 through 409 and that executes once for every inverted index Ind i of a set of inverted indices 207 .

Step 407 selects token sets Q′ c.i , Q′ t.i , and Q′ v.i , wherein token sets Q′ c.i comprise all possible subsets of the intersection of Q c and inverted index Ind i , token sets Q′ t.i comprise all possible subsets of the intersection of Q t and inverted index Ind i , and token sets Q′ v.i comprise all possible subsets of the set of all variable tokens comprised by inverted index Ind i .

Step 409 generates a set FQ i of all possible fielded queries (Q′ c.i , Q′ t.i , Q′ v.i ) associated with input query Q 209 and with an inverted index Ind i . The set FQ i comprises the set of all possible ordered triplets of token subsets Q′ c.i , Q′ t.i , and Q′ v.i , subject to some or all of the conditions described below.

The selection of ordered sequences (Q′ c.i , Q′ t.i , Q′ v.i ) that comprise set FQ i is further constrained by boundary conditions that are functions of variables Min c.i , Max c.i , Min t.i , Max t.i , Min v.i , Max v.i , NS u.i , and NS l.i defined in the description of the set of clusters of fielded documents 205 of FIG. 2 , and wherein these variables describe properties of a set of fielded documents fd i comprised by a cluster C i , wherein C i is associated with an inverted index Ind i . These conditions may comprise length operators, wherein a length of an entity that comprises a set of tokens is defined as a number of tokens that are comprised by that set of tokens.

In embodiments, an ordered sequence (Q′ c.i , Q′ t.i , Q′ v.i ) may thus be required to further satisfy the following conditions, wherein inverted index Ind i is generated from a cluster of fielded documents C i .

i) a number of concept tokens comprised by set Q′ c.i may be no greater than MAX c.i , wherein MAX c.i is a largest number of concept tokens comprised by a fielded document of a set of fielded documents comprised by cluster C i , and may be no less than MIN c.i , wherein MIN c.i is a smallest number of concept tokens comprised by a fielded document of a set of fielded documents comprised by cluster C i ; ii) a number of term tokens comprised by set Q′ t.i may be no greater than MAX t.i , wherein MAX t.i is a largest number of concept tokens comprised by a fielded document of a set of fielded documents comprised by cluster C i , and may be no less than MIN t.i , wherein MK t.i is a smallest number of term tokens comprised by a fielded document of a set of fielded documents comprised by cluster C i ; iii) a number of variable tokens comprised by set Q′ v.i may be no greater than MAX v.i , wherein MAX v.i is a largest number of concept tokens comprised by a fielded document of a set of fielded documents comprised by cluster C i , and may be no less than MIN v.i , wherein MIN v.i is a smallest number of variable tokens comprised by a fielded document of a set of fielded documents comprised by cluster C i ; iv) a sum of the lengths of Q′ c.i , Q′ t.i , and Q′ v.i may be no less than a sum MIN c.i +MIN t.i+ MIN v.i ; and v) a sum of the lengths of Q′ c.i , Q′ t.i , and Q′ v.i may be no greater than a smallest number of tokens comprised by a fielded document of a set of fielded documents comprised by cluster C i .

These boundary conditions may be expressed formally as:

i) MIN c.i ≦|Q′ c.i |≦MIN c.i , ii) MIN t.i ≦|Q′ t.i |≦MAX t.i , iii) MIN v.i ≦|Q′ v.i |≦MAX v.i iv-v) NS l.i ≦|Q′ c.i |+|Q′ t.i |+|Q′ v.i |≦NS u.i

In some embodiments, tokens or sequences may be selected by conditions that may complement, replace, or partially replace the conditions described here.

Upon completion of an iteration of the iterative process of steps 405 - 409 , step 405 is executed and the iterative process repeats for the next instance of inverted index Ind i . If the iterative process has been performed for all inverted indices Ind i of the set of inverted indices 207 , then the procedure of FIG. 4 terminates and the method of the present invention continues with step 309 of FIG. 3 .

Upon completion of steps 401 through 409 for all inverted indices Ind i , embodiments of the present invention will have selected a set of fielded queries 211 that comprise all possible ordered sequences (Q′ c , Q′ t , Q′ v ) of token sets that satisfy the conditions described in step 409 .