Patent ID: 6879980

Claim:
A method for locating neighbor objects of a query geometry in a database, the method comprising: 1) tiling a query geometry at a tiling level t; 2) conducting a search of a search area comprising interior and boundary tiles of the query geometry for neighbors among objects in the database, wherein the objects in the database are indexed using a linear quadtree index, if the search does not produce a result set that includes a target number of neighbors, then the following steps are carried out starting with a radius r of 1: 3) expanding the search area to a radius r tiles at a distance d from the boundary tiles and conducting a search for neighbors in the expanded search area, where (r−1)*tw<d≦r*tw, wherein tw is the maximum or minimum of the x-width, y-width of a tile at level t and r is the query radius; 4) using each tile in the expanded search area it is determined if there are any geometries at distance≦r*tw that are to be included in the result set; 5) if a target number of neighbors is not found, steps 3-4 are repeated with a query radius of 2 tile widths followed by 3 tile widths; 6) if the target number still is not reached retiling the query geometry at a higher level of tiling; and 7) repeating steps 1-7 until either the target number is reached or all objects in the database are searched.