Evaluar las consultas de rutas regulares (RPQs) ha sido de interés desde que se usaron como una forma poderosa de explorar caminos y patrones en las bases de datos de gráficos. Los enfoques tradicionales basados en autómatas están restringidos en el tamaño del gráfico y/o en consultas altamente complejas, lo que causa un alto costo de evaluación (por ejemplo, espacio de memoria y tiempo de respuesta) en gráficos grandes. Recientemente, aunque el uso del enfoque basado en la etiqueta rara de umbral para gráficos grandes ha logrado cierto éxito, a menudo no pueden garantizar el costo mínimo de búsqueda. Alternativamente, se ha estudiado la Matriz de Costo de Subconsulta Unitaria (USCM) y se ha obtenido la viabilidad del uso de subconsultas. Sin embargo, este método tiene un problema, que es, no acumula el costo entre subconsultas que causa un largo tiempo de respuesta en un gráfico grande. Para superar este problema, este documento propone un método para estimar el costo de unión de subconsultas para acelerar la evaluación paralela basada en USCM de RPQs en un gráfico grande, es decir, USCM-Join. A través de conjuntos de datos del mundo real, demostramos experimentalmente que USCM-Join supera a otros y que la estimación del costo de unión mejora el enfoque basado en USCM hasta alrededor del 20% en términos de tiempo de respuesta.