Proposals to establish a 'science of interaction' have been forwarded from Information Visualization and Visual Analytics, as well as Cartography, Geovisualization, and GIScience. This paper reports on two studies to contribute to this call for an interaction science, with the goal of developing a functional taxonomy of interaction primitives for map-based visualization. A semi-structured interview study first was conducted with 21 expert interactive map users to understand the way in which map-based visualizations currently are employed. The interviews were transcribed and coded to identify statements representative of either the task the user wished to accomplish (i.e., objective primitives) or the interactive functionality included in the visualization to achieve this task (i.e., operator primitives). A card sorting study then was conducted with 15 expert interactive map designers to organize these example statements into logical structures based on their experience translating client requests into interaction designs. Example statements were supplemented with primitive definitions in the literature and were separated into two sorting exercises: objectives and operators. The objective sort suggested five objectives that increase in cognitive sophistication (identify, compare, rank, associate, & delineate), but exhibited a large amount of variation across participants due to consideration of broader user goals (procure, predict, & prescribe) and interaction operands (space-alone, attributes-in-space, & space-in-time; elementary & general). The operator sort suggested five enabling operators (import, export, save, edit, & annotate) and twelve work operators (reexpress, arrange, sequence, resymbolize, overlay, pan, zoom, reproject, search, filter, retrieve, & calculate). This taxonomy offers an empirically-derived and ecologically-valid structure to inform future research and design on interaction.