Missing values in Geographic Information Systems (GIS) datasets present significant challenges for spatial analysis and decision-making. We introduce a set-based framework that represents missing entries as domain-consistent sets and imputes them through statistical sampling, clustering-guided evaluation, and local search refinement. To avoid the computational intractability of exploring all possible value combinations, candidate datasets are generated using key statistical measures derived from both global domains and spatial neighborhoods. This sampling strategy preserves essential distributional properties while keeping complexity manageable. Each candidate dataset is evaluated using clustering quality metrics, under the assumption that suitable imputations should reinforce natural groupings and spatial patterns. A local search layer is applied to further refine produced imputations without significantly affecting efficiency. Applications on real-world GIS datasets illustrate the practical value of the framework.