The motion of a star relative to the Sun is referred to as its space velocity, and is divided into its radial velocity toward or away from the Sun, and its tangential velocity perpendicular to the radial velocity (that is, in the plane of the "sky"), as shown in the diagram below:

     Most of the stars in the vicinity of the Sun, including the Sun, are moving in more or less elliptical paths around the center of our Galaxy at speeds of around a hundred and fifty miles per second. Their motions relative to each other are usually only ten to fifteen percent of their overall motions, or fifteen to twenty-five miles per second, in much the same way as cars on a freeway, though moving very rapidly relative to their surroundings, have slow motions relative to each other. Some stars, however, are moving in a very different direction from their neighbors, such as straight in or out relative to the center of the Galaxy. Even if such stars have overall velocities identical to those of their neighbors, their different direction of motion will give them very high relative velocities, often exceeding two hundred miles per second. Such stars are referred to as high-velocity stars.

Measuring Space Velocities
     To measure the space velocity of a star we measure its radial and tangential velocities, then use the Pythagorean Theorem to calculate the overall motion. Unfortunately, in most cases only the radial velocity of a star can be measured, and its tangential and space velocities are unknown.
     The radial velocity of a star can be measured by the Doppler effect that its motion produces in its spectrum, and is more or less instantly determined by measuring the wavelengths of absorption lines in its spectrum, which can be accomplished regardless of its distance from the Sun, providing that it is bright enough to observe its spectrum in the first place. The only way that its distance affects the measurement is that the further away it is the fainter it appears, so the longer it takes to collect enough light to observe its spectrum.
     To measure the tangential velocity, however, we must wait for the star's apparent position in the sky to change due to the proper motion produced by its tangential velocity. If the star has a large tangential velocity and is relatively close to the Sun, it may have a large proper motion. Barnard's Star, a red dwarf which happens to be a high-velocity star and is also the second closest star to the Sun (counting the Alpha Centauri system as a single object), has a proper motion of more than ten seconds of arc per year, so its tangential velocity can be measured in just a few months. But only half a dozen or so stars have proper motions even half that large, and for the vast majority of stars proper motions are measured in hundredths or thousandths of a second of arc per year, so it takes decades or even millenia to measure their tangential velocity. For stars in other galaxies the proper motions are so small that so far, only satellites of our Galaxy and M33, a spiral galaxy in Triangulum, have been observed to have any proper motion. The proper motions and tangential velocities of the tens of billions of other galaxies are completely unknown.