Patent ID: 7912839

Claim:
A method for creating a non-uniform index structure for data having a plurality of objects, comprising: setting a threshold for a number of objects in a cell and a threshold for a maximum number of decompositions for a cell; creating a plurality of cells by overlaying a grid over the plurality of objects; decomposing each of the plurality of cells until either the threshold for the maximum number of decompositions is reached, or the number of objects in each cell is below the threshold for a number of objects in a cell, wherein the decomposing is performed by a processor, and wherein the decomposing each of the plurality of cells is performed based on unequal subdivision of cells; creating a key for each cell, wherein the key for each cell is created by creating a n-ary string representing each cell; performing zero-padding for each cell that has not reached the threshold for the maximum number of decompositions; and creating an index structure for the data using the key for each cell.