Data streams produced by positioning systems such as Global Positioning System (GPS) or RFID readers can be considered as location streams[12]. Location streams are usually generated in a distributed fashion by a large scale distributed system covering a wide range of areas. Computing on distributed location streams is both practically useful and theoretically challenging. The results of computation could be used to schedule the traffic in a metropolis to avoid traffic jam, dispatch taxis to serve the passengers more quickly and display the current position of goods in supply chain management, etc. Since location streams are usually generated with very high rate in uncertain ways over hostile environments, the collected updates of location are probably redundant and inconsistent in a wide positioning system. To process distributed location streams with redundancy and inconsistency, this paper proposes a novel method based on min-wise hash. With this method, redundant updates of distributed location streams can be effiectively filtered out, while the true location could be derived from inconsistent ones. Consequently, globally uniform samples can be obtained. Based on the uniform samples, an algorithm for computing the approximate k-median of huge number of moving objects is presented in this paper. Furthermore, it is demonstrated that sketch-based methods are not necessarily effiective in processing location streams with redundancy and inconsistency. In addition to theoretical analysis, some extensive experiments are conducted to validate the efficiency and effiectiveness of the proposed approach.