  In this paper, we propose a paradigm for processing in parallel graph joins
in road networks. The methodology we present can be used for distance join
processing among the elements of two disjoint sets R,S of nodes from the road
network, with R preceding S, and we are in search for the pairs of vertices
(u,v), where u in R and v in S, such that dist(u,v) < {\theta}. Another
variation of the problem would involve retrieving the k closest pairs (u,v) in
the road network with u in R and v in S, such that dist(u,v) <= dist(w,y),
where w,y do not belong in the result.
  We reckon that this is an extremely useful paradigm with many practical
applications. A typical example of usage of our methods would be to find the
pairs of restaurants and bars (in that order) from which to select for a night
out, that either fall within walking distance for example, or just the k
closest pairs, depending on the parameters. Another entirely different scenario
would involve finding the points of two distinct trajectories that are within a
certain distance predicate, or the k closest such points. For example, we would
like to transfer from one train to another a few tones of freight, and hence,
we want to minimize the distance we have to cover for moving the cargo from the
carrying train to the other. We reckon that this endeavor of ours covers
exactly those needs for processing such queries efficiently.
  Moreover, for the specific purposes of this paper, we also propose a novel
heuristic graph partitioning scheme. It resembles a recursive bisection method,
and is tailored to the requirements of the problem, targeting at establishing
well separated partitions, so as to allow computations to be performed
simultaneously and independently within each partition, unlike hitherto work
that aims at minimizing either the number of edges among different partitions,
or the number of nodes thereof.
