Efficiently finding spatially scored best entities

摘要

In one embodiment, a particular number of best entities are found in a database with a spatial index that satisfy both spatial criteria and entity filtering criteria. For each of a set of targets in the spatial index whose bounding box meets the spatial criteria, a spatial score is calculated. If the spatial score is less than a minimum spatial score in a current map of best entities and the current map is full, the target is excluded from further consideration. If the spatial score is not less than the minimum spatial score, when the target is an entity that meets the entity filtering criteria, the current map is updated to store the entity and the spatial score for the entity. When each of the targets in the spatial index has been subject to test or excluded from consideration, the current map is returned as a final result.

主权项

1. A method for finding a particular number of best entities in a relational database with a spatial index that satisfy both spatial criteria and entity filtering criteria, where best is determined based on upon a spatial score relative to spatial scores of other entities in the relational database, the method comprising:
receiving, by a relational database system executing on an electronic device, a query statement indicating an entity filtering criteria and the particular number of best entities desired; maintaining a current map of best entities that represents a potential result for the query statement, the current map being initially empty; for each of a set of targets in the spatial index whose bounding box meets the spatial criteria, starting at a root node of the index,
calculating the spatial score for the target,if the spatial score for the target is less than a minimum spatial score in the current map of best entities and the current map is full, excluding the target from consideration for inclusion in the current map,if the spatial score for the target is not less than the minimum spatial score in the current map of best entities and the current map is full, when the target is an entity that meets the entity filtering criteria, updating the current map to drop a lowest scoring entity in the current map and store the entity and the spatial score for the entity, andif the current map is not full, when the target is an entity that meets the entity filtering criteria, updating the current map to store the entity and the spatial score for the entity; andwhen each of the targets in the spatial index has been subject to test or excluded from consideration for inclusion in the current map, returning the current map as a final result for the query statement.