# A Linear Fitting Algorithm Based on Modified Random Sample Consensus
## 3 Modified Random Sample Consensus-Based Linear Fitting Algorithm  
### Locality-Sensitive Hashing  
In the field of outlier data processing, effectively obtaining and analyzing the correlation information between data in high-dimensional space is crucial. Given that the correlation among data can be translated into neighborhood relationships, the local vicinity information of the data can be leveraged to deduce the associations between data points. Hashing techniques represent a common method for approximate nearest neighbor searches. The method first identifies a hash function that maps similar data points to the same hash table, and then performs a data search around the query position in the hash table to find the nearest neighbors of the target data. Among these, Locality-Sensitive Hashing is one of the most commonly used methods. The core idea of LSH is that in high-dimensional space, if two data points are close to each other, the hash function is likely to produce the same hash values for them with a high probability; conversely, for points that are not close together, the hash function tends to generate different hash values with a high probability. LSH is a hashing technique designed for efficient approximate nearest neighbor search, focusing on constructing a family of hash functions that preserve the similarity between points. In the context of line fitting, the similarity between points is typically measured using Euclidean distance or cosine similarity. For data points \(v\) in the dataset, let \(v_{i}(x_{i},y_{i})\) and \(v_{j}(x_{j},y_{j})\) represent a pair of points. The formulas for Euclidean distance and cosine similarity are given by Equations (10) and (11), respectively.  
\[\|v_{i}-v_{j}\|^{2}=\sqrt{(x_{i}-x_{j})^{2}+(y_{i}-y_{j})^{2}} \tag{10}\]  
\[sim(v_{i},v_{j})=\frac{v_{i}v_{j}}{\|v_{i}\|\|v_{j}\|} \tag{11}\]  
Construct a family of hash functions \(\mathcal{H}\) that satisfies the locality-sensitive property, such that similar points are mapped into the same bucket with a high probability, while dissimilar points are mapped into the same bucket with a low probability.  
In two-dimensional or higher-dimensional spaces, the distribution of data points is often quite complex, necessitating the design of effective hash functions that ensure that highly similar data points are mapped to the same bucket, while less similar data points are mapped to different buckets. One approach to designing hash functions is through random hyperplane projection, where the basic idea is to use hyperplanes to divide the space into two parts, with the projection of data points on the hyperplane determining their  
Figure 1: Iterative process of the random sample consensus. (**a**) 2D data points. (**b**) First iteration process. (**c**) Final iteration result. Red points: nearest line fitting points. Black points: original data.  
hash values. By constructing multiple random hyperplanes, data points are projected onto multiple hash values, thereby improving classification accuracy.  
The specific process of Locality-Sensitive Hashing for finding similar data is as follows:  
1. Construct appropriate locality-sensitive hash functions to ensure that similar data points are mapped into the same or adjacent hash buckets.
2. Utilize the constructed hash functions to map all data points in the dataset into their corresponding buckets in the hash table, with each bucket containing similar data points.
3. Retrieve points mapped to the same or adjacent buckets, treating these points as candidate neighbors. By further calculating the similarities of these candidate points, the final neighbors can be determined.