In this paper we propose a new efficient interpolation tool, extremely suitable for large scattered data sets. The partition of unity method is used and performed by blending Radial Basis Functions (RBFs) as local approximants and using locally supported weight functions. In particular we present a new space-partitioning data structure based on a partition of the underlying generic domain in blocks. This approach allows us to examine only a reduced number of blocks in the search process of the nearest neighbour points, leading to an optimized searching routine. Complexity analysis and numerical experiments in two- and three-dimensional interpolation support our findings. Some applications to geometric modelling are also considered. Moreover, the associated software package written in \textsc{Matlab} is here discussed and made available to the scientific community.