Abstract: Since GPS cannot be used under in-building environment and current in-building localization approaches require pre-installed infrastructure, in-building localization becomes a problem demanding prompt solutions for location-based services. Therefore, this paper proposes a novel room-level in-building localization algorithm R-kNN (relativity k-nearest neighbor), which solves the localization problem by leveraging MAC address and RSSI (received signal strength indication) of Wi-Fi access points (APs) deployed in buildings. R-kNN falls into category of property-weighted k-nearest neighbor algorithm. By assigning the weight of each AP according to the relativity between AP pairs, R-kNN can reduce the negative effect of dimension redundancy. Moreover, since it makes no assumption on the physical distribution of rooms and APs, R-kNN can work well with existing APs without deploying any new infrastructure or modifying the existing ones. Experimental results demonstrate that when a large number of APs are available, the localization accuracy of R-kNN is bigger than those of the original kNN algorithm and nave Bayes classifier, while its false positive ratio and false negative ratio is smaller than those of the original kNN algorithm and Nave Bayes classifier in most cases.