||Taxi is a major transportation in urban area, offering great benefits and convenience to our daily life. But one of the major business frauds in taxi is the charging fraud, specifically, charging more fees than the actual service distance. In practice, it is hard for us to always monitor taxis and detect such fraud. Thanks to the Global Position System (GPS) embedded in taxis, we can collect the GPS reports from the taxis, having the location, time, and driving information. Intuitively, we can utilize such data to compute the actual service distance of taxis in the city map. But due to the extremely limited report, notable location errors, complex city map and road networks, our task to detect the taxi fraud faces great challenges and the naive method does not work well. In this thesis, we have a basic observation that fraudulent taxi always changes the taximeter in a much larger scale, and as a result it not only makes the service distance larger, but also the reported taxi speed much larger. Fortunately, the speed information collected from the GPS report is accurate. Hence, we utilize the speed information to design a novel speed-based clustering model to detect the taxi fraud, which is robust to the location errors, and independent of the map and road networks. The experiments on the real life data sets confirm the better accuracy, scalability and more efficient computation of our method, comparing to the current map-matching methods. Keywords— speed, clustering, taxi fraud detection.