Described is a technology by which GPS-capable devices work with a cloud service to receive satellite visibility-related data. The satellite visibility-related data may be used to determine a location, and/or to abort a search for satellites. The cloud service may use crowd data from other GPS-capable devices. In one aspect, line-of-sight satellites are differentiated from other satellites, and used to determine which satellite signals are more trustworthy. Reflected signals also may be determined.