Systems, methods, and software are disclosed herein for enhancing entity classification operations for digital maps. In an implementation, an entity classification system associates tiles in a grid overlaying a map with discrete positioning records produced by devices operating in areas represented in the map. For each tile in an area of interest in the grid, the system produces a scalar description based on a subset of the discrete positioning records associated with the tile. The system then performs a binary classification of each tile as a type of entity (e.g. a road, business, or residence) based on the scalar description of the tile and the scalar descriptions of other tiles in the area of interest.