Good data structure for finding all points in one set a distance from each point in another set
Sort the big set $Y$ into a regular grid, then for any query point $x_i,$ find its cell and you only have to check the adjacent cells to determine $E_i$ very quickly. For sorting, indeed, some parallel algorithms are faster than others, see this poster for an overview and example of using fast GPU radix and count sort.