In recent years, massive amount of spatial data described by using texts (labels or sentences) are generated by modern applications. Because of wide use of such data in various applications, many researches focus on how to efficiently retrieve desired data points. Skyline operator that has different types and is based on the concept of dominance, is one of the available responses to this challenge. A data point dominates another one, if it is not worse than another one in all dimensions and better in at least one dimension. Spatio-textual Skyline query uses skyline operator, and retrieves the desired data points (spatially close and textually relevant to the query point) that are not dominated by other data points. The heavy computatios required for this type of queries, as well as big data phenomenon turnes out optimal and efficient answering to these queries to be a serious challenge. Consequently, most of the solutions proposed in this area suffer from lack of scalability. In this research, we proposed two approaches to deal with the scalability challenges. The first solution is an approximate algorithm that offers a compromise between accuracy and efficiency by pruning the search space. The second solution is an efficient distributed approach that uses the map-reduce distributed programming model. Extensive evaluations confirm the high scalability of proposed algorithms. Keywords Spatio-Textual data, Map-Reduce model, Distributed approach, Approximate approach