Systems, methods, and computer products that improve the techniques used to search multidimensional databases over techniques of the past. The preferred embodiment of the present invention advantageously improves the technique of determining a grid index that is used to locate a geometric shape in a spatial database. More particularly, the preferred embodiment of the present invention improves the technique of sampling data for defining the grid cell size in a grid for a given data set, thereby improving the grid indexing process that locates a particular minimum-bounding rectangle and the associated geometric shape.