System and method of optimizing database queries in two or more dimensions
First Claim
Patent Images
1. A system for searching a map database, the system comprising:
- a computer memory storing a map database comprising a plurality of sub-regions and a plurality of map objects, wherein the sub-regions comprise a central portion and a predetermined overlap portion, wherein the overlap portion is shared between multiple adjacent sub-regions, wherein each of the sub-regions is identified with one of a plurality of index keys, and wherein the spatial map objects comprise spatial coordinates and are associated with one or more of the index keys; and
a computer system configured to;
receive a query for map objects within a region of spatial coordinates;
identify in the computer memory at least one index key associated with the region; and
select from the computer memory at least one map object associated with the at least one index key.
12 Assignments
0 Petitions
Accused Products
Abstract
A method and system for storing and retrieving spatial data objects from a spatial database is discussed. The system stores multi-dimensional objects within the database by determining their position in a multi-tiered coordinate system. One each object has been assigned to a particular coordinate, the object is further assigned to one of many overlapping sections within the coordinate system. Each object is assigned to a particular section of the coordinate system depending on its overall size and position.
-
Citations
44 Claims
-
1. A system for searching a map database, the system comprising:
-
a computer memory storing a map database comprising a plurality of sub-regions and a plurality of map objects, wherein the sub-regions comprise a central portion and a predetermined overlap portion, wherein the overlap portion is shared between multiple adjacent sub-regions, wherein each of the sub-regions is identified with one of a plurality of index keys, and wherein the spatial map objects comprise spatial coordinates and are associated with one or more of the index keys; and a computer system configured to; receive a query for map objects within a region of spatial coordinates; identify in the computer memory at least one index key associated with the region; and select from the computer memory at least one map object associated with the at least one index key. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A method of searching a map database for objects within a specified spatial region, the method executed by a computer system and comprising:
-
storing in a computer memory a map database comprising a plurality of sub-regions and a plurality of map objects, wherein the sub-regions comprise a central portion and a predetermined overlap portion, wherein the overlap portion is shared between multiple adjacent sub-regions, wherein each of the sub-regions is identified with one of a plurality of index keys, and wherein each of the map objects comprises spatial coordinates and is associated with one or more of the index keys; receiving by the computer system a query for one or more map objects within a region of spatial coordinates; identifying by the computer system one or more index keys index the computer memory associated with the region, wherein each of the index keys identifies a sub-regions in the map database; selecting from the computer memory at least one map object associated with one of the set of index keys. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19)
-
-
20. A system for storing spatial data objects, the system comprising:
-
a computer memory storing a spatial database comprising a plurality of shingles, each shingle adjacent to at least one other shingle, each shingle overlapping each of its adjacent shingles by a predetermined portion of the shingle, the shingles arranged in a plurality of levels, from a lowest level to a highest, top level, the shingles within each level having a same size; a computer system configured to perform the steps of; determining from the computer memory a location of a data object within a coordinate system; assigning the data object that is not larger than the size of the shingles in a level to the shingle in that level that completely contains the data object, including any portion of the data object that is within the portion of the shingle overlapping an adjacent shingle, and storing the assignment in the computer memory; and storing the data object along with a reference to the shingle to which it is assigned in the computer memory. - View Dependent Claims (21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 38)
-
-
35. A method of organizing spatial data objects in a spatial database, the spatial database stored in a computer memory, the method executed by a computer system and comprising:
-
storing in the spatial database a plurality of shingles, each shingle adjacent to at least one other shingle, each shingle overlapping each of its adjacent shingles by a predetermined portion of the shingle, the shingles logically arranged in a plurality of levels, from a lowest level to a highest, top level, the shingles within each level having a same size; determining by the computer system for the data objects respective locations in a coordinate system; assigning by the computer system each data object that is not larger than the size of the shingles in a level to the shingle in that level that completely contains the data object, including any portion of the data object that is within the portion of the shingle overlapping an adjacent shingle. - View Dependent Claims (36, 37, 39, 40, 41, 42, 43, 44)
-
Specification