Methods and apparatus to provide cluster-based fingerprinting algorithms are described. In one embodiment, m closest fingerprints from k fingerprints are determined. The k fingerprints may be determined as closest fingerprints to a scan s in a signal strength domain, where the scan s is of an environment surrounding a wireless device. The center of mass of the m fingerprints may be used to determine a location estimation for the wireless device. Other embodiments are also described.