Patent ID: 8214371

Claim:
A method for creating a global spatial index for use in a partitioned parallel environment including P partitions, each partition residing on one or more parallel processing systems, the global spatial index including: creating a linear quad-tree structure dividing an n-dimensional space into linear quad-tree cells (QTCs), each QTC having a designator, the designators having an order; creating a set of spatial objects, each spatial object being assigned to one or more of the QTCs depending on the location of the spatial object in the n-dimensional space; creating one or more index entries for each spatial object, each index entry including the designator for the QTC to which the spatial object was assigned and a pointer to the spatial object; and storing the index entries in substantially equal numbers among the P partitions, at least one of the P partitions being stored on a different data storage facility than the other P-1 partitions, the partition where an index entry is stored being determined by: sorting the index entries by QTC designator into QTC bins, each QTC bin corresponding to one of the QTCs, each QTC bin containing the index entries for the spatial objects that were assigned to that QTC; working through the QTC bins in order of the QTCs' designators, dividing the index entries in the QTC bins into P substantially equal parts, even when the index entries are not uniformly distributed among the QTC bins; storing the index entries associated with each part of the list in a different partition; and duplicating an index entry in two or more partitions only if the location of the spatial object falls into two or more QTCs for which index entries are stored in more than one partition.