Indexing spatial data with a quadtree index having cost-based query decomposition
US8892569B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Dec 23, 2010 |
| Grant date | Nov 18, 2014 |
| Priority date | — |
| Expiry date | Sep 18, 2033 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/2246
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Approaches for indexing and retrieving spatial data with a quadtree index in database management systems are described. In an embodiment, data objects are stored without decomposition within a linearized quadtree stored within a B-tree index. In another embodiment, a method determines an optimal execution plan for a spatial query by parsing it to determine a query type and geometry object associated with the query. The method tessellates the query object by recursively decomposing the quadtree blocks that cover it. Cost-based decomposition decisions are made by consulting a cost model furnished by the database management system to minimize the cost of the resulting index range plan on the B-tree storage. Thus, data-directed query decomposition enacted by the method results in the optimal cost index range plan for the current data distribution and system context. In another embodiment, a system identifies and displays an optimal index range plan in a user interface.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.