Abstract: Particle tracing methods are a fundamental class of techniques for vector field visualization. Specifically, interactive particle advection allows the user to rapidly gain an intuitive understanding of flow structures. Yet, it poses challenges in terms of computational cost and memory bandwidth. This is particularly true if the underlying data is time-dependent and represented by a series of unstructured meshes. In this paper, we propose a novel approach which maps the aforementioned computations to modern many-core compute devices in order to achieve parallel, interactive particle advection. The problem of cell location on unstructured tetrahedral meshes is addressed by a two-phase search scheme which is performed entirely on the compute device. In order to cope with limited device memory, the use of data reduction techniques is proposed. A CUDA implementation of the proposed algorithm is evaluated on the basis of one synthetic and two real-world data sets. This particularly includes an assessment of the effects of data reduction on the advection process' accuracy and its performance.