System and method for efficient representation of dynamic ranges of numeric values

Embodiments of the present invention describe using a data structure to represent variable domains in solving a constraint problem. The data structure includes nodes that are configured to represent ranges of values in order to save memory space and processor power. Ranges of values and single values may be both added to and removed from the data structure such that the data structure does not include duplicate values. Operations may include detecting multiple nodes with adjacent or overlapping ranges that may be combined into a single node, and adding or removing all the values in the structure that are beyond a threshold value. In one embodiment the data structure may be a balanced binary tree. Constraint solvers may either add values to the data structure as the values are eliminated from the solution, or they may remove those values.

BACKGROUND OF THE INVENTION

Embodiments of the present invention relate generally to data representation, and more particularly to solving constraint problems using efficient methods and systems for representing variable domains.

Constraint programming is a discipline that deals with the representation of a problem in a manner that allows for solutions to be formulated. Each variable in a constraint problem may be modeled as a solution space comprising a range of discrete or continuous values. The relations and limitations between these variables may be expressed as constraints. The constraints act to limit the values in a variable's solution space. A solution is a state in which each variable has had its domain limited to a single value without violating any of the constraints. Often, software programs known as constraint solvers may be used to find one or more solutions to a given constraint problem, or alternatively, to prove that no solution exists.

Computer systems may use a method for solving constraint problems known as Arc Consistency. Arc Consistency ensures that every value in the domain of each variable has a supporting value in the other variables that satisfies all of the constraints. Values that are not consistent may be removed from the domain of each variable. The inference power of Arc Consistency ensures that every value of a variable is consistent with its constrained neighbor variables, thus eliminating inconsistent values from each solution.

For a computer system to efficiently perform the key functionality of reasoning over valid values and eliminating invalid values, the computer system must be able to efficiently represent to the domains of each variable. Existing methods for representing variable domains are limited. Hence, there is a need for improved methods and systems for efficiently representing data for solving constraint problems.

BRIEF SUMMARY OF THE INVENTION

Some embodiments of the present invention describe using a data structure to represent variable domains in solving a constraint problem. The data structure includes nodes that are configured to represent ranges of values in order to save memory space and processor power. Ranges of values and single values may be both added to and removed from the data structure such that the data structure does not include duplicate values. Operations may include detecting multiple nodes with adjacent or overlapping ranges that may be combined into a single node, and adding or removing all the values in the structure that are beyond a threshold value. In one embodiment the data structure may be a balanced binary tree. Constraint solvers may either add values to the data structure as the values are eliminated from the solution, or they may remove those values.

In one embodiment, a method of selecting an optimal value from a solution space for a constraint problem is presented. The method may comprise mapping the solution space to a range of finite sequential values, and storing a data structure comprising a plurality of nodes. The plurality of nodes including a first node, the first node having a first node range of one or more values, and the first node range having a first bound and a second bound. The method may also include receiving a selection range of one or more values to be excluded as the optimal value from the range of finite sequential values, where the selection range has a first bound and a second bound. The method may further include determining whether the selection range should be merged with the first node range, and in response to a determination that the selection range should be merged with the first node range, updating the second bound of the first node range to be equivalent to the second bound of the selection range. The method may additionally include adding a second node to the data structure in response to a determination that the selection range should not be merged with the first node range, where the second node has a second node range, the second node range with a first bound and a second bound, and where the second node range is equivalent to the selection range, the first bound of the second node range is equivalent to the first bound of the selection range, and the second bound of the second node range is equivalent to the second bound of the selection range.

In another embodiment, a method of selecting an optimal value from a solution space for a constraint problem is presented. The method may include mapping the solution space to a range of finite sequential values, and storing a data structure comprising a plurality of nodes. The plurality of nodes may include a first node with a first node range of one or more values and a first bound and a second bound, and a second node with a second node range of one or more values and a first bound and a second bound. The method may also include receiving a selection range of one or more values to be excluded as the optimal value from the range of finite sequential values, where the selection range has a first bound and a second bound. The method may further include determining whether the selection range, the first node range, and the second node range should be merged into a single range. The method may additionally include updating the first node to represent the single range in response to a determination that the selection range, the first node range, and the second node range should be merged into the single range, and removing the second node from the data structure. The method may also include adding a third node to the data structure in response to a determination that the selection range, the first node range, and the second node range should be merged into the single range, with the third node comprising a third node range, the third node range comprising a first bound and a second bound, wherein the third node range is equivalent to the selection range, the first bound of the third node range is equivalent to the first bound of the selection range, and the second bound of the third node range is equivalent to the second bound of the selection range.

In another embodiment, a computer-readable medium having stored thereon a sequence of instructions is presented. The instructions which, when executed by a processor, may cause the processor to select an optimal value from a solution space for constraint problem by mapping, using the processor, the solution space to a range of finite sequential values, and storing, in a memory, a data structure comprising a first node, the first node comprising a first node range of one or more values equivalent to the range of finite sequential values, the first node range comprising a first bound and a second bound. The instructions may also cause the processor to receive a selection range of one or more values to be excluded as the optimal value from the range of finite sequential values, where the selection range has a first bound and a second bound, and remove the selection range from the data structure by splitting the first node into two nodes that exclude the selection range.

DETAILED DESCRIPTION OF THE INVENTION

When solving constraint problems, each variable represented in the problem may be modeled as a solution space comprising a range of discrete values. Relationships between these variables may be used to constrain the possible solution spaces for each variable. Finding a set of solutions for the problem may often involve subjecting the solution spaces of each variable to limiting algorithms that enforce the various constraint rules until the domain of each variable is limited to a single value without violating any of the constraints. Because of the complexity of the algorithms involved, and because of the large number of possible solution values, software programs known as constraint solvers may be used to both represent the variable solution spaces and run the solver algorithms.

To solve a constraint problem using a computer system, the domain of one or more of the variables may be converted into a range of finite sequential values that may be represented digitally.FIG. 1illustrates the partial setup100of a constraint problem that includes a variable, for example, for the thickness120of a piece of glass110in a wave transmission application.

The domain of the variable for the thickness120of the glass110could be between 10 inches and 20 inches. To solve this problem using a constraint solver in a computer system, the domain of the thickness120could be mapped to a first range130of finite sequential values130representing incremental thicknesses120of the glass110, such as {10″, 11″, 12″, . . . 18″, 19″, 20″}. Values with this range could then be systematically removed according to various algorithms known in the art until only an optimal solution remains.

While the first range of finite sequential values130in this simple example only includes 10 values, more complex constraint problems may contain millions of values. The size of a variable's domain may increase, and/or there may need to be increased resolution in the range of values. For example, the resolution of a second range of values140described above could be increased, resulting in a sequence with thousands of values, such as {10″, 10.0001″, 10.0002″, . . . 19.9998″, 19.9999″, 20″}. Furthermore, a constraint problem may contain many different variables, each having its own range of values that need to be analyzed in order to arrive at an optimal solution. Therefore, one challenge is to provide a system that allows for the representation of and reasoning over very large numeric sets, and to do so in a manner that allows for optimal performance while minimizing memory utilization.

In order to run a constraint solver algorithm, it is usually advantageous to represent the domain of each variable within a data structure stored in a memory. One embodiment stores the range of discrete numbers used to represent the domain of each variable in a data structure. Then, as values are eliminated by the algorithm as possible solutions, those values are removed from the data structure. When the solver algorithm finishes running, any values that remain in the data structure may be considered to not violate any of the constraint rules in conjunction with the values for the other variables, and may thus be considered possible solutions. For example, inFIG. 1, the range of finite sequential values130comprising the values of {10″, 11″, 12″, . . . 18″, 19″, 20″} may be stored in a data structure such as an array150. As values160are removed from the data structure, the remaining values may be considered candidates for solutions. Eventually, all of the values in the array150may be removed that violate the constraints, and the remaining values may be considered to be solutions. Alternatively, if no values remain, then no solutions may exist.

In another embodiment, the constraint solver algorithm may add values to a data structure as they are eliminated from the solution space for each variable. For example, a simple range may be used to describe the domain of each variable, and then add the values that are removed from that range in a data structure. For example, inFIG. 1, the first range130representing the thickness of the thickness120of the piece of glass110may be represented as {10 . . . 20}. Instead of storing each integer value between 10 inches and 20 inches in a data structure, the constraint solver may store values in the data structure as they are removed from the range. Thus, values160that are removed such as {12}, {14}, and {17} would be inserted in to the data structure. When the constraint solver finished its iterations, the solutions could be identified by the gaps in the data structure. Or, if no gaps are found in the data structure, then no solutions may exist.

Either of these methods (removing values from or adding values to a data structure) may benefit from the use of a data structure that provides efficient access to values and minimizes the use of memory space. One method of representing ranges of values in a constraint problem is the use of bit vectors. Here, each value may be represented by a single bit in a bit vector. Each bit is associated with a single value in the range, and the “1” or “0” designates whether the value has been excluded from the solution space by the solution algorithm. However, the bit vector method, along with other similar methods, requires at least one memory location to represent each value. Therefore, as the size of the range expands, the size of the bit vector increases at the same rate of O(n). This may render bit vectors unsuitable to efficiently represent large data sets.

In addition to the solution methods described above, embodiments of the present invention provide systems, methods, and devices that may be used to compactly represent large ranges of sequential numeric values. A data structure may be used to represent sub-ranges within a finite range of sequential values. In contrast to existing range/interval trees, these embodiments use a data structure that is designed to optimize its time and space complexity by consolidating adjacent and overlapping ranges within the set. This self-optimizing data structure may consolidate redundant values into single nodes. Therefore, single nodes within the data structure may store multiple sequential values by representing them as a single range. Some embodiments efficiently represent ranges by storing an upper and lower bound on the range, with access methods that may be designed around the degree of quantization used to define the spacing between sequential values (i.e., integers, even numbers, etc.).

The self-optimizing data-structure discussed herein may be implemented in any existing data storage mechanism. These may include, but are not limited to, trees, graphs, arrays, vectors, lists, linked lists, queues, stacks, heaps, hash tables, and/or the like. Various embodiments may use a binary tree structure wherein each node in the binary tree stores a value or a range of values. These binary trees may use a balancing procedure to minimize the time associated with traversing the tree when adding values. Balancing procedures such as those found in AA tress, AVL trees, red-black trees, scapegoat trees, splay trees, treaps, and/or the like may be used in conjunction with certain embodiments. For example, one embodiment utilizes a red-black tree configuration to balance the tree nodes as they are added and removed from the data structure.

FIG. 2illustrates one embodiment of a self-optimizing data structure200. Each of the nodes in the data structure200may represent either a single value or range of sequential values. Nodes210,250, and260of the data structure200represent ranges of sequential values. For example, node210represents the integers between −100 and 100 inclusive, node250represents the integers between 150 and 200 inclusive, and node260represents the integers between 275 and 300, inclusive. These ranges may be represented using an upper bound and a lower bound. For example, node210includes a lower bound215and an upper bound217that represent the boundaries of the represented range. Note that inFIG. 2, the data structure200is represented as a binary tree structure. This is merely illustrative, and the data structure200may be implemented as any other data of data structure that could perform similar functions.

In addition to nodes210,250, and260representing ranges of numbers, nodes,220,230, and240represent single values. Node220represents the value of {−500}, node230represents the value of {250}, and node240represents the value of {−1000}. The single values may be represented within the node as a single value. For instance, node200may store the value of −500 as a single value {225} in a single memory location. However, in some embodiments, the single value225may be stored in the same type of node used to represent a range of numbers. Although not shown explicitly inFIG. 2, the single value225of {−500} stored in node220may be represented by an upper and lower bound. Thus, node220could store an upper and lower bound, with each bound set to the same single value225of {−500 }. Therefore, a node that stores a single value may be considered to store a range of values, wherein the range is represented by the interval of {−500 . . . −500}, which amounts to a single value. This type of structure may simplify operations by allowing the tree200to use a single node type to store all ranges of values, whether they include a single value or a sequence of multiple values.

As used herein, the term “range” may include both single values and multiple values. Therefore, when a range is selected from a variable's domain, this may include both single values and multiple sequential values. Likewise, when comparing the range of a selection to the range of one or more nodes in a data structure, this comparison may include comparing both single values and ranges of multiple values.

Adding nodes to the data structure200that do not overlap with any of the ranges already in the tree may result in the simple addition of nodes to the tree200. This process may be similar to the process of adding nodes to any other binary tree structures. However, adding nodes to the tree200that are adjacent to existing nodes may involve a more complex procedure. As used herein, the term “adjacent” means that the two values or ranges follow one after the other in a finite sequence of values that represent a solution space for a variable in a constraint problem. For example, if a finite sequence of values includes even integers {−2, 0, 2, 4, 6, 8, 10}, then the range {0 . . . 4} would be adjacent to the single values of {−2} and {6} The range {0 . . . 4} would also be adjacent to the ranges {6 . . . 8} and {6 . . . 10}. However, the range {0 . . . 4} would not be adjacent to the single values of {8} and {10}, and would not be adjacent to the range {8 . . . 10}. Thus, adjacency should be considered in the context of the finite sequence of values. In the data structure200inFIG. 2, the finite sequence of values may be all of the integers between a value less than or equal to −1000 and greater than or equal to 300.

FIG. 3illustrates the addition of a node that is adjacent to an existing node in the embodiment of a self-optimizing data structure200. Node310representing a single value of {−499} may be added to the data structure200. In this case, the value of {−500} represented by node220is adjacent to the value of {−499} represented by node310that is being added to the data structure200. Instead of adding a new node representing {−499}, this value may be added to node220with the adjacent value of {−500}. The upper bound of node220may be changed from {−500} to be {−499}, while the lower bound may stay at {−500}. Thus the upper bound of node220may change as reflected by node320inFIG. 3.

This same procedure may be followed for adding a single value that is adjacent to a range of values represented by a node in the tree. For example, (not shown) the value of −101 would be adjacent to the range of {−100 . . . 100} represented by node210. If the value of {−101} were to be added to the data structure200, the lower bound of node210could be change to be {−101} instead of forming a new node. Node210would then represent the range of {−101 . . . 100}. It is worthy of note that in these last two cases (adding adjacent single values) the number of values represented by the data structure200is increased without increasing the size or complexity of the data structure200.

FIG. 4illustrates the addition of a range of values that is adjacent to an existing node in the embodiment of a self-optimizing data structure200shown inFIG. 3. Node410representing a range of {201 . . . 248} may be added to the data structure200. In this case, the range of {150 . . . 200} represented by node250is adjacent to the range of {201 . . . 248} represented by node410that is being added to the data structure200. Instead of simply adding node410to the data structure200, the range of {210 . . . 248} may be added to node250's adjacent range. The upper bound of node250may be changed from {200} to be {248}, while the lower bound may stay at {150}. The changed upper bound of node250may change as reflected by node450inFIG. 4.

This same procedure may be followed for adding a range that is adjacent to a single values represented by a node in the data structure200. For example, (not shown) the range of {−999 . . . 990} could be adjacent to the single value of {−1000} represented by node240. If the range of {−999 . . . 990} were to be added to the data structure200, instead of forming a new node, the upper bound of node240could be changed from {−1000} to be {−990}. Node250would then represent the range of {−1000 . . . −990}. Again, in these last two cases (adding adjacent ranges) the number of values represented by the data structure200is increased, sometimes significantly so, without increasing the size or complexity of the data structure200.

In some cases, adding single values or ranges to a self-optimizing data structure may in fact decrease the size and complexity of the tree.FIG. 5illustrates the addition of a single value that is adjacent to two existing nodes in an embodiment of a self-optimizing data structure200. Node510represents the single value of {249}, which is adjacent to the single values of {250} represented by node230and the range of {150 . . . 248} represented by node450. By inserting a node with a value that is adjacent to two different existing nodes, the new node may collapse all three nodes into a single node representing a range of values. Here, the range of {150 . . . 248} and the single values of {249} and {250} are all adjacent. These the nodes may collapse into a single node530representing the range of {150 . . . 250}. By determining that a new node is adjacent to other existing nodes, the complexity and size of the data structure may be reduced. This is a significant improvement over other types of data structures that may exist.

Similarly, if a new node representing a range of values is added to the data structure200, and the new node represents a range of values that is adjacent to the values of two existing nodes, each of these three nodes may be collapsed into a single node.FIG. 6illustrates the addition of a range of values that are adjacent to two other nodes in the data structure200. New node610representing a range of values of {−999 . . . 501} is an example of another type of node that may be added to the data structure200. The range represented by the new node610is adjacent to the value of {−1000} represented by node240, and it is adjacent to the range of {−500 . . . −499} represented by node320. Because each of these values and/or ranges are adjacent, these three nodes may be collapsed into a single node620representing the range of {−1000 . . . −499}. Again, this operation adds 499 values to the tree, yet reduces the size and complexity of the tree by at least one node.

In addition to determining whether new nodes contain adjacent values or ranges, some embodiments also determine whether new nodes contain values or ranges that overlap with one or more existing nodes in the data structure. Ranges can overlap in at least three different ways. The first way that ranges can overlap is for the added range to fall within an existing range.FIG. 7illustrates an example of adding a range that is within one of the existing nodes. A new node710representing the range {280 . . . 290} may be added to the data structure200. This new range falls completely within the range of {275 . . . 300} represented by node260. Therefore, addition of the new node710may have no effect on the tree because this range is already represented by the existing node710.

There are a number of ways to determine whether the range of the new node710falls within the existing node260. For example, in one embodiment, it may be determined whether the upper bound of the new node710is less than or equal to the upper bound of the existing node260. Also, it may be determined whether the lower bound of the new node710is greater than or equal to the lower bound of the existing node260. Referring to the upper and lower bounds generically as a first bound and a second bound, another embodiment may determine whether both the first and second bounds of the new node fall within the first and second bounds of the existing node. Various embodiments may use different mathematical operators and programming language features to make this determination.

As used herein, the terms “first bound” and “second bound” are used to merely designate that two distinct bounds may exist. However, these term do not always indicate an ordering of these bounds. For example, the first bound may be the upper bound and the second bound may be the lower bound in some embodiments, and vice versa.

A second way for the range of a new node to overlap with the range of an existing node is for the two ranges to partially overlap, such that the intersection of the two ranges is less than the complete range of either node.FIG. 8illustrates and example of adding a range that partially overlaps with the range of an existing node260. A new node810representing the range {280 . . . 310} may be added to the data structure200. This new range partially overlaps with the range of {275 . . . 300} represented by node260. Adding the range of the new node810may not require the addition of an actual node to the tree, because one of the bounds of the existing node260may be updated to reflect the combined range. In this case, the upper bound of the existing node260may be updated to be {310}, which would effectively incorporate the added range to the updated node860. As was the case with adding adjacent ranges/values, adding partially overlapping ranges can add a significant number of values to the data structure200without adding any complexity or size.

There are in number of ways to determine whether the range of the new node810partially overlaps with the existing node260. For example, in one embodiment, it may be determined that the upper bound of the new node810is greater than the upper bound of the existing node260. Also, it may be determined that the lower bound of the new node810is within the range of the existing node260(i.e., greater than or equal to the lower bound and less than or equal to the upper bound). Referring to the upper and lower bounds generically as a first bound and a second bound, another embodiment may determine whether either the first or second bound of the new node falls between the first and second bounds of the existing node, and then whether the other bound of the new node810falls outside of the range of the existing node260. Various embodiments may use different mathematical operators and programming language features to make this determination. Additionally, other mathematical or logical functions may also be used in order to make this determination as effectively as possible.

A third way for the range of a new node to overlap with the range of an existing node is for the new range to completely overlap the existing node's range. In case where the new node completely overlaps only a single node, the bounds of the existing node may be simply updated to reflect the bounds of the new node. More complex situations may arise wherein the new node overlaps multiple nodes.FIG. 9illustrates an example of adding a range that completely overlaps with the range of an existing node530. A new node910representing the range {101 . . . 285} may be added to the data structure200. This new range completely overlaps with the range of {150 . . . 250} represented by node530. Additionally, the range of the new node also partially overlaps with the range of {275 . . . 310} represented by node860, and the range of the new node910is adjacent to the range of {−100 . . . 100} represented by node210. In this case, each of the three existing nodes210,530, and860that are adjacent to or overlap with the new node910may be collapsed into one node920with a range of {−100 . . . 310}. It should be clear that adding node910with a range that overlaps or is adjacent to the ranges of multiple nodes in the tree may significantly reduce the complexity and/or size of the tree while adding a large number of values.

Depending on the type of data structure various embodiments may use, there may be different methods for updating the data structure when a new range overlaps or is adjacent to multiple existing nodes. For a data structure200that uses a balanced binary tree, the process may involve updating the bounds of one of the existing nodes. In the example ofFIG. 9, the upper bound of node201was set to the upper bound of the highest node860range that partially overlapped with the range of the new node910. Additionally, the nodes,530and860, that were completely overlapped by the range of the new node910were removed from the tree. For a tree such as data structure200, removing nodes and adjusting the bounds of other nodes may also require rearranging some of the tree's branches and performing a balancing algorithm such as those found in a red-black binary tree. Other types of data structures may use different methods to balance or otherwise increase the efficiency of accessing their data.

There are a number of ways to determine whether the range of the new node910completely overlaps with the existing node530. For example, in one embodiment, it may be determined that the upper bound of the new node910is greater than the upper bound of the existing node530. Next, it may be determined that the lower bound of the new node910is less than the lower bound of the existing node260. Referring to the upper and lower bounds generically as a first bound and a second bound, another embodiment may determine that the first bound of the new node910is less than both bounds of the existing node530, and that the second bound of the new node910is greater that both bounds of the existing node530. Various embodiments may use different mathematical operators and programming language features to make this determination. Additionally, other mathematical or logical functions may also be used in order to make this determination as effectively as possible.

It should be clear that there are multiple ways for a new range that is added to the data structure to reduce the number of nodes in the tree. Some of these have been discussed above, and others should be readily apparent in light of this disclosure. For example, a new range could be adjacent to two existing ranges; the new range could be adjacent to one existing range and partially overlap another existing range; the new range could be adjacent to one existing range and completely overlap a second existing range; the new range could partially overlap two existing ranges; the new range could partially overlap one existing range and completely overlap another existing range; and the new range could completely overlap two existing ranges. This listing is merely exemplary, and is not meant to be limiting. For example, the new range may be adjacent to or overlap three or more existing ranges. In most cases, the more existing ranges that are affected by the new range, the more the complexity and size of the tree may be reduced.

As discussed above, rather than adding values to a data structure, some embodiments may remove values from the data structure as they are eliminated as possible solutions by a constraint solver algorithm. To accommodate this type of solution procedure, embodiments of the self-optimizing data structure may accommodate the removal of values and/or ranges.FIG. 10illustrates an example of a self-optimizing data structure1000representing a single range of values. Again, in this case the self-optimizing data structure1000is represented in the figures as a binary tree; however, this is not meant to be limiting. The self-optimizing data structure1000may also be implemented as a number of other data structures according to various embodiments. These may include, but are not limited to, trees, graphs, arrays, vectors, lists, linked lists, queues, stacks, heaps, hash tables, and/or the like. The root node1010of the data structure1000represents the range of {4 . . . 20}. This may correspond to the domain of a variable in a constraint problem. The finite range of sequential values may be the integers between the values of {4} and {20}. The constraint solver may use the data structure1000to represent the values that are still possible candidates to be solutions for the variable.

As the solver iterates through the possible solutions, the constraints of the problem may eliminate single values or ranges of multiple values from the solution space. When this occurs, these values may be removed from the data structure1000. For example, the constraint solver may eliminate the value of {14} represented by node1040. Removing this value may split the root node1010into two nodes, namely nodes1020and1030. In the binary tree example ofFIG. 10, the either of the two new nodes1020and1030may remain the root node, while the other could become a child of the new root node. Note that in this case, removing a value from the data structure1000actually increased the size and complexity of the data structure1000. Generally, removing single values from a data structure comprised mostly of nodes representing ranges will increase the size of the data structure until single values begin to predominate. At that point, removing single values will again tend to reduce the size and/or complexity of the data structure.

FIG. 11illustrates the removal of another value from the data structure1000. In this case, the single value {13} represented by node1110that is being removed by the data structure1000may be an upper or lower bound of a range represented by an existing node. Because {13} is also the upper bound of the range {4 . . . 13} represented by node1020, removing {13} from the data structure1000may only require adjusting the upper bound of the existing node1020to be equal to the removed value. Thus, node1020may be updated, and the range of {4 . . . 12} may be represented by updated node1120. Of course, although not shown inFIG. 11, this same analysis may hold true for single values that equal a lower bound of an existing node. Broadly, any removed value that equals a first or second bound of an existing node may be removed by updating the corresponding bound of the existing node.

Similarly, removing a range of values from the data structure1000may also have a similar effect as removing a single value. For example (not shown) if instead of removing the value of {13} from the data structure1000inFIG. 11, a range of {13 . . . 14} were removed, the effect on the data structure1000may ultimately be the same. Of note is the fact that in both of these cases where values—whether multiple or single values—are removed that share a bound with an existing node, the overall complexity and/or size of the data structure1000should not increase.

FIG. 12illustrates an example of removing a range of values from the data structure1000, according to one embodiment. In this case, the range of values {17 . . . 18} represented by node1210may be removed, which splits one of the ranges of an existing node into two parts. The range {17 . . . 18} occurs completely within the range {15 . . . 20} represented by node1030. Node1030may be split into two nodes: node1220representing the range {15 . . . 16} and node1230representing range {19 . . . 20}. Although not required by some embodiments, this embodiment using a binary tree rebalances the tree according to a red-black balancing algorithm. Therefore, the tree may “rotate” such that node1220becomes the root node and node1120becomes a child of node1220.

FIG. 13illustrates the removal of a range of values from the data structure1000wherein the range overlaps multiple existing nodes, according to one embodiment. This embodiment also illustrates a special function that may be implemented to remove values from the data structure1000called “pruning” Often in a constraint solver, a new upper bound be determined for the domain of the represented variable. In other words, the algorithm may determine that all values greater than (or less than) a certain value may be eliminated from the possible solution set. To efficiently remove these values from the data structure1000, it may be given a command to prune all of the values that are greater than (or less than) a certain value.FIG. 13illustrates a command to prune all values less than the value of {16}. Two nodes exist with values that must be pruned: node1120representing the range {4 . . . 12} could be removed entirely, and node1220representing the range {15 . . . 16} could be reduced. Coincidentally, this is also an example of removing a range of values that overlaps with the ranges of multiple existing nodes. Much like the multiple-overlap case when adding values to the tree, removing overlapping ranges may actually reduce the size and/or complexity of the data structure1000.

Here, the node1120may be removed completely, and one of the bounds of node1220may be updated to equal the value below which the pruning takes place. The pruning action may be accomplished in one embodiment by having the data structure1000locate the node that equals or contains the pruning value, possibly adjusting the bounds of that node, and then removing all nodes including lesser values. In the embodiment ofFIG. 13which uses a binary tree, the pruning operation may include altering the a node containing the pruning value, and then removing the left child node and all of its descendents. In another embodiment, the data structure may use the bounds of the range of finite sequential values to turn the prune command into a regular removal of a range. For example, if the lower bound of the range of finite sequential values inFIG. 13is {4}, then the prune command could be reformulated to remove the range of {4 . . . 15}.

FIG. 14illustrates a flowchart1400of a method for solving a constraint problem using a self-optimizing data structure, according to one embodiment. At process block1410, the domain of each variable in the constraint problem may be mapped to a range a finite sequential values. At process block1420, the constraint solver algorithm may begin analyzing the constraint problem to enforce the constraint rules on the various variable domains. As the algorithm determines that certain variable values violate one or more of the constraints, these values may be eliminated as possible solutions. A range of multiple values or a single value may be designated for removal from the solution space of the variable. At decision block1430, a self-optimizing data structure may be stored in a memory. If no nodes currently exist in the data structure, i.e., the data structure is empty and this is the first set of values to be excluded as solutions, then the a new node may be created and the excluded range of values may be added to the data structure.

On the other hand, if it is determined that other nodes already exist in the data structure at decision block1430, then a determination must be made as to whether the excluded range should be merged with one or more of the existing nodes in the data structure at decision block1440. If it is determined that the excluded range should not be merged with any existing nodes, i.e., the excluded range does not overlap with and is not adjacent to any existing nodes, then the excluded range may be added to the data structure as a new node at process block1470. However, if the excluded range does overlap with or is adjacent to one or more existing nodes, then it may be merged with those nodes. At process block1450nodes may be removed from the data structure that are completely overlapped by the excluded range. At process block1460, any nodes that partially overlap with or are adjacent to the excluded range should have their bounds adjusted to incorporate the excluded range. The operations of process blocks1450and1460may be used in various combinations in order to properly add the excluded range. For example, an excluded range that completely overlaps two existing nodes, partially overlaps a third existing node, and is adjacent to a fourth existing node may lead to the removal of three of these existing nodes and updating the remaining existing node.

At process block1480, it may be determined whether more values may be removed from the range of finite sequential values to be excluded as solutions. If more values may be removed, then the a new excluded range may be determined by returning to process block1420. If no more values can be removed, then the values not in the data structure may be designated as solutions to the constraint problem by process block1490. Additionally, if no values may remain, then process block1490may determine that no solution exists for the constraint problem. At this point, the constraints or variable domains may be reformulated and the method illustrated by the flowchart1400may be executed again.

FIG. 15illustrates a flowchart1500of a method for solving a constraint problem using a self-optimizing data structure, according to one embodiment. At process block1510, the domain of each variable in the constraint problem may be mapped to a range a finite sequential values. At process block1520, a self-optimizing data structure may be stored in a memory. The initial range of values representing the domain of a variable may also be added to the data structure. In one embodiment, this may be a single node representing the range. In another embodiment, this may be a number of separate ranges, each containing a range of sequential values. At process block1530, the constraint solver algorithm may begin analyzing the constraint problem to enforce the constraint rules on the various variable domains. As the algorithm determines that certain variable values violate one or more of the constraints, these values may be eliminated as possible solutions. Consequently, a range of multiple values or a single value may be designated for removal from the solution space of the variable. At decision block1540, the range of excluded values may be removed from the data structure by first determining if the existing range overlaps with one or more existing nodes. In one embodiment, each excluded range would overlap with at least one node in the data structure. However, in another embodiment, the algorithm may generate excluded ranges that overlap with each other, and could therefore lead to some ranges that would not overlap with any node in the data structure.

On the other hand, if it is determined that the excluded range completely overlaps one or more existing nodes at decision block1540, then the overlapped existing nodes may be removed from the data structure at process bock1550. If one or more of the existing nodes is only partially overlapped by the excluded range, then the bounds of the existing nodes may be updated to reflect the overlapping portion of the removed range at process block1560. If instead of overlapping existing nodes, the excluded range is overlapped by an existing node, i.e., if the excluded range falls within an existing node, as determined by decision block1570, then the existing node maybe split into two nodes at process block1575. Note that at this stage the data structure may be rebalanced. Rebalancing may also take place after any operation that adds or removes nodes from the data structure.

At process block1580, it may be determined whether more values may be removed from the range of finite sequential values to be excluded as solutions. If more values may be removed, then a new excluded range may be determined by returning to process block1530. If no more values can be removed, then the remaining values may be designated as solutions to the constraint problem by process block1590. Additionally, if no values may remain, then process block1490may determine that no solution exists for the constraint problem. At this point, the constraints or variable domains may be reformulated and the method illustrated by the flowchart1500may be executed again.

Although many of the examples used herein to provide an enabling disclosure have illustrated single dimensional ranges, other embodiments may also multi-dimensional representations of variable domains. In one embodiment, at least one variable may be represented by a two-, three- or four-dimensional coordinate system. In another embodiment, multiple single-dimensional variables may be combined into a multi-dimensional representation and used as a single variable in the algorithm. Multi-dimensional variables may be represented by multiple single-dimensional data structures, or multi-dimensional data structures may be used.

FIG. 16is a block diagram illustrating components of an exemplary operating environment in which various embodiments of the present invention may be implemented. The system1600can include one or more user computers1605,1610, which may be used to operate a client, whether a dedicated application, web browser, etc. The user computers1605,1610can be general purpose personal computers (including, merely by way of example, personal computers and/or laptop computers running various versions of Microsoft Corp.'s Windows and/or Apple Corp.'s Macintosh operating systems) and/or workstation computers running any of a variety of commercially-available UNIX or UNIX-like operating systems (including without limitation, the variety of GNU/Linux operating systems). These user computers1605,1610may also have any of a variety of applications, including one or more development systems, database client and/or server applications, and web browser applications. Alternatively, the user computers1605,1610may be any other electronic device, such as a thin-client computer, Internet-enabled mobile telephone, and/or personal digital assistant, capable of communicating via a network (e.g., the network1615described below) and/or displaying and navigating web pages or other types of electronic documents. Although the exemplary system1600is shown with two user computers, any number of user computers may be supported.

The system may also include one or more server computers1620,1625,1630which can be general purpose computers and/or specialized server computers (including, merely by way of example, PC servers, UNIX servers, mid-range servers, mainframe computers rack-mounted servers, etc.). One or more of the servers (e.g.,1630) may be dedicated to running applications, such as a business application, a web server, application server, etc. Such servers may be used to process requests from user computers1605,1610. The applications can also include any number of applications for controlling access to resources of the servers1620,1625,1630.

In some embodiments, an application server may create web pages dynamically for displaying on an end-user (client) system. The web pages created by the web application server may be forwarded to a user computer1605via a web server. Similarly, the web server can receive web page requests and/or input data from a user computer and can forward the web page requests and/or input data to an application and/or a database server. Those skilled in the art will recognize that the functions described with respect to various types of servers may be performed by a single server and/or a plurality of specialized servers, depending on implementation-specific needs and parameters.

The system1600may also include one or more databases1635. The database(s)1635may reside in a variety of locations. By way of example, a database1635may reside on a storage medium local to (and/or resident in) one or more of the computers1605,1610,1615,1625,1630. Alternatively, it may be remote from any or all of the computers1605,1610,1615,1625,1630, and/or in communication (e.g., via the network1620) with one or more of these. In a particular set of embodiments, the database1635may reside in a storage-area network (“SAN”) familiar to those skilled in the art. Similarly, any necessary files for performing the functions attributed to the computers1605,1610,1615,1625,1630may be stored locally on the respective computer and/or remotely, as appropriate. In one set of embodiments, the database1635may be a relational database, such as Oracle 10g, that is adapted to store, update, and retrieve data in response to SQL-formatted commands.

FIG. 17illustrates an exemplary computer system1700, in which various embodiments of the present invention may be implemented. The system1700may be used to implement any of the computer systems described above. The computer system1700is shown comprising hardware elements that may be electrically coupled via a bus1755. The hardware elements may include one or more central processing units (CPUs)1705, one or more input devices1710(e.g., a mouse, a keyboard, etc.), and one or more output devices1715(e.g., a display device, a printer, etc.). The computer system1700may also include one or more storage device1720. By way of example, storage device(s)1720may be disk drives, optical storage devices, solid-state storage device such as a random access memory (“RAM”) and/or a read-only memory (“ROM”), which can be programmable, flash-updateable and/or the like.

The computer system1700may additionally include a computer-readable storage media reader1725a, a communications system1730(e.g., a modem, a network card (wireless or wired), an infra-red communication device, etc.), and working memory1740, which may include RAM and ROM devices as described above. In some embodiments, the computer system1700may also include a processing acceleration unit1735, which can include a DSP, a special-purpose processor and/or the like.

The computer-readable storage media reader1725acan further be connected to a computer-readable storage medium1725b, together (and, optionally, in combination with storage device(s)1720) comprehensively representing remote, local, fixed, and/or removable storage devices plus storage media for temporarily and/or more permanently containing computer-readable information. The communications system1730may permit data to be exchanged with the network1720and/or any other computer described above with respect to the system1700.

The computer system1700may also comprise software elements, shown as being currently located within a working memory1740, including an operating system1745and/or other code1750, such as an application program (which may be a client application, web browser, mid-tier application, RDBMS, etc.). It should be appreciated that alternate embodiments of a computer system1700may have numerous variations from that described above. For example, customized hardware might also be used and/or particular elements might be implemented in hardware, software (including portable software, such as applets), or both. Further, connection to other computing devices such as network input/output devices may be employed. Software of computer system1700may include code1750for implementing embodiments of the present invention as described herein.