  We study first-order logic over unordered structures whose elements carry a
finite number of data values from an infinite domain which can be compared wrt.
equality. As the satisfiability problem for this logic is undecidable in
general, in a previous work, we have introduced a family of local fragments
that restrict quantification to neighbourhoods of a given reference point. We
provide here the precise complexity characterisation of the satisfiability
problem for the existential fragments of this local logic depending on the
number of data values carried by each element and the radius of the considered
neighbourhoods.
