Quickly finding nearest time observation I'm looking to speed up some of the analysis I need to do on a regular basis. Basically, I have many datasets comprised of millions or more records, and for each record I need to calculate the nearest time observation to another dataset. Currently, I have this working like such:
##RecordSet1Million is a record set with > 1million rows, each with distinct time observation
##RecordSet50K is a smaller record set with ~ 50k unique records
NearestTimeObs <- foreach(i=1:nrow(RecordSet1Million), .combine=c) %dopar% {
    which.min(abs(RecordSet1Million$DateTime[i]- RecordSet50K$DateTime))
}

Currently, it takes over 50 mins on my 4 core workstation in Windows to do this, I'm wondering if there are some 'hacks' I  can do to make the computations faster. Something with data.table perhaps? 
 A: This can be done in a few seconds by exploiting sorting.
Such an algorithm takes $O(n+m)$ space and $O(n\log(n) + m\log(m))$ time for an array $X$ of $m$ "probe" times searching within an array $Y$ of $n$ "target" times.
Solution
The idea is that after sorting the concatenated vector $(Y;X)$, a nearest time to each element $x\in X$ will be located in one of two places: it will either be the greatest value of $Y$ appearing before $x$ or the least value of $Y$ appearing after $x$.  A quick check determines which place is closest.
(Notice that any algorithm to find the greatest value to the left of $x$ will easily yield the least value to its right, merely by negating both $x$ and $y$ and reversing their sort order.)
Implementation considerations
When working on a platform (such as R) that cannot scan rapidly over arrays, the challenge is to find some native function that is equivalent to the search to the left.  One that will do it in R is cummax, the cumulative maximum function.  I will therefore use this to demonstrate the algorithm. 
As a running example, represent all times as real numbers (which they always are internally, in terms of seconds, days, or years after some conventional starting date).  Suppose 
$$X = 0.16, 0.97, 0.47, 0.78, 0.41; \quad Y = 0.5, 0.2, 0.2.$$


*

*First sort $X$ and $Y$ separately.  (This is needed so that cummax will work out correctly.)  To make sure there will always be some elements of $Y$ less than all elements of $X$ and some others greater than all elements of $X$, pad $Y$ with $-\infty$ and $+\infty$.  Now
$$X = 0.16, 0.41, 0.47, 0.78, 0.97;\quad Y = -\infty, 0.2, 0.2, 0.5, +\infty.$$

*Identify the ordering of $(Y;X)$.  (Since both $Y$ and $X$ are already sorted, this merge takes only $O(m+n)$ time.)  Its indexes, in sort order, are
$$i = (1,6,2,3,7,8,4,9,10,5).$$
Notice in the example that all indexes greater than $5$ (the length of the padded $Y$) correspond to elements of $X$.

*Replace the indexes corresponding to elements of $X$ with negative indexes so they will be skipped by cummax:
$$i = (1,-1,2,3,-1,-1,4,-1,-1,5).$$
Notice that one positive index for each position in $Y$ appears and one index of $-1$ has been place in each position in $X$.

*Compute the cumulative maximum of what's left.  This scans from left to right, recording the largest value seen so far.  In the example it will be
$$(1,1,2,3,3,3,4,4,4,5).$$
This process basically propagates all indexes corresponding to elements of $Y$ forward.

*Associate with each element of $X$ the cumulative maximum in the same position.  Since in the sorted version of $(Y;X)$ the values of $X$ occur in positions $2,5,6,8,9$ (see the result of step 2), the associated indexes into $Y$ are $1,3,3,4,4$.  The associated values of $Y$ are $-\infty, 0.2, 0.2, 0.5, 0.5$.  You may confirm these are the greatest values of $Y$ found to the left of $X$.
The reason to compute indexes into $Y$ is that often the elements of $Y$ are complex data structures, such as records in a database, and what is wanted is not only the nearest time, but also attributes of the record associated with that time.

The figure plots some probe points (lower, in blue) and a set of target points (upper, in red).  Midpoints of the target points are shown as vertical gray segments: they partition the horizontal axis into the Voronoi cells for the targets.  Because some of the targets are duplicated, the area of each target point is proportional to the number of replicates (1, 2, or 3).  The arrows display the assignment of each probe to its nearest target.  That they do not cross the gray lines attests to the correctness of this result.
Working code
The R code implementing this algorithm (dubbed glb below, for "greatest lower bound") takes under two seconds (running on one 3.3 GHz core) to perform $10^6$ probes into $10^6$ targets.
#
# Return an array `i` of indexes into `target`, parallel to array `probe`.
# For each index `j` in `target`, probe[i[j]] is nearest to target[j].
#
nearest <- function(probe, target, ends=c(-Inf,Inf)) {
  #
  # Both `probe` and `target` must be vectors of numbers in ascending order.
  #
  glb <- function(u, v) {
    n <- length(v)
    z <- c(v, u)
    j <- i <- order(z)
    j[j > n] <- -1
    k <- cummax(j)
    return (k[i > n])
  }
  y <- c(ends[1], target, ends[2])

  i.lower <- glb(probe, y)
  i.upper <- length(y) + 1 - rev(glb(rev(-probe), rev(-y)))
  y.lower <- y[i.lower]
  y.upper <- y[i.upper]
  lower.nearest <- probe - y.lower < y.upper - probe
  i <- ifelse(lower.nearest, i.lower, i.upper) - 1
  i[i < 1 | i > length(target)] <- NA
  return (i)
}
#
# Graphical illustration.
#
set.seed(17)
x <- sort(round(runif(8), 3))
y <- sort(round(runif(12), 1))
i <- nearest(x, y)
plot(c(0,1), c(3/4,9/4), type="n", bty="n", yaxt="n", xlab="Values", ylab="")
abline(v = (y[-1] + y[-length(y)])/2, col="Gray", lty=3)
invisible(apply(rbind(x, y[i]), 2, function(a) arrows(a[1], 1, a[2], 2, length=0.15)))
points(x, rep(1, length(x)), pch=21, bg="Blue")
points(y, rep(2, length(y)), pch=21, bg="Red", cex=sqrt(table(y)[as.character(y)]))
text(c(1,1), c(1,2), c("x","y"), pos=4)
#
# Timing.
#
x <- runif(1e6)
y <- runif(1e6)
system.time({
  x <- sort(x); y <- sort(y)
  nearest(x,y)
  })

A: You may make it faster by finding the nearest observation approximately, and for that you may use Locality Sensitive Hashing.
So you need to index the bigger dataset, and then see each row of the smaller dataset as a query. I'm not familiar with any R implementations of LSH, but there are libraries for C++ and python.
