Gabriel graph based models approach large margin classifiers by obtaining support vectors from geometric properties. However, they have been limited to small and medium-sized applications, mainly due to the cost of computing the graph. This work presents an algorithm to compute the graph optimizing computational and memory costs. For the former, we exploit a distance matrix computed in advance and for the latter we use a bootstrap approach to construct the graph from batches of the dataset, with upper bound convergence analysis. Our approach aims to enable applications with large datasets for these models.