Efficient data structure for matching 3D lines
Any line can be represented in the form $\{p + xv : x \in \mathbb{R}\}$, or in other words, by a point $p$ on the line and a vector $v$ parallel to the line.  Without loss of generality, we can take $v$ to have norm 1 (if not, replace $v$ with $v/\|v\|_2$).  Also, if we ignore lines where the $z$-component of $v$ is zero, then without loss of generality we can take $p$ to be a point whose $z$-component is zero.

So, let's represent any line by the pair $p,v$, where $v$ is chosen to have norm 1 and where $p$ is chosen to have its $z$-component be zero.  Then this is a canonical representation of the line: each line has a unique representation, and two lines coincide iff their $p,v$-representations are identical.

This means that you can store each line in a hash table, where you store the pair $p,v$.  Thus, it is a hash table where each key is a 6-tuple.  You could compress it so each key is a 4-tuple (you can represent $v$ with 2 dimensions, and you only need to store the $x$- and $y$-components of $p$), but this probably doesn't gain you much.

To deal with floating-point errors, you could round $p,v$ to the nearest multiple of $\epsilon$ before storing it in the hashtable.  Or, you could store it in a data structure that supports nearest neighbor queries, such as a k-d tree.