Patent ID: 7904486

Claim:
A method of building an index to a plurality of entities, wherein each entity is represented by data identifying a point defined in a space, by creating a hierarchy of sub-area data structures, the method comprising: (i) creating a region around the points representing the entities; (ii) performing a process in respect of the created region or sub-region, the process comprising: creating an area or sub-area data structure; storing, within the area or sub-area data structure, data specifying the extent of the respective region or sub-region; storing, within the area or sub-area data structure, links to points falling within the respective region or sub-region; dividing the region or sub-region to create a plurality of sub-regions; and for each of the plurality of sub-regions that contains points, reducing the sub-region until further reduction thereof would result in one of the points falling outside of the sub-region; and (iii) repeatedly performing the process in respect of each created sub-region that contains points until a predetermined criterion has been satisfied; wherein the method further comprises storing, within each area or sub-area data structure, links to sub-area data structures corresponding to its respective plurality of sub-regions; and wherein the hierarchy of sub-area data structures provides the index to the entities.