A good starting point may be a simplified version of iDistance. The full algorithm works by defining (central) cluster nodes, which are used to reduce the multiple dimensions to one. That one dimensional scalar is used to search a B+ tree. There are other algorithms like it, but they basically use the same approach. (Indexing High-Dimensional Data
for Efficient In-Memory Similarity Search gives a nice overview of several algorithms and their performance.)
However, if we allow some approximations and discarding of nodes, then it may be enough to just have a tree of cluster nodes, perhaps a few layers deep. Search that tree for the nearest cluster node, and then search for the 5 nearest points attached to that node. All brute force calculations of the distance between points in N-dimensional space. Or however you want to optimize it.
Consider the following algorithm in pseudo code:
for (i = 0; i < 10000; ++i)
Vector v = randomVector();
cluster = clusters.findNearestCluster(v); // brute force search on distance squared
PointArray points = cluster.sortPointsOnDistanceSquared(v);
Implemented in Java, 100 dimensions, each dimension between 0.0 and 10.0, runs in 5-8 seconds, on an Intel i7, second generation. Which means, well below the 1000/s stream speed. There is a lot of room for optimization. (I'd share the code, but really, it won't add anything.)
There is more than enough time to do something about rebalancing your cluster tree. Clusters that are in the middle of nowhere and get no hits can be removed. Clusters that have too many hits might be split or otherwise reduced. There should be some radius attached, some overlap tested, etcetera.
In this example code, these were some of the timings:
Minimum: 0, Maximum: 1067, #Clusters_having_points: 96, Average: 104, Time: 7498ms
Minimum: 0, Maximum: 1095, #Clusters_having_points: 97, Average: 103, Time: 7241ms
Minimum: 0, Maximum: 1010, #Clusters_having_points: 99, Average: 101, Time: 6465ms
Minimum: 0, Maximum: 832, #Clusters_having_points: 99, Average: 101, Time: 5688ms
With Min/Max/Avg the min/max/avg points per cluster node. It's programmed in no time, and easy to play around with, to get some picture of how the data handles itself.
The way I see it, most algorithms offer exactness, and keep all their data. They spent their time on the reduction of the N-dimensional point to one dimension. They need that one dimension, to use all kinds of balancing data structures, so they can sift through gazillions of data. By letting go of that exactness (and history), you free up time to use more mundane methods to balance your search tree. "Too many points for this cluster? Throw away half, as long as we can find 5 points that are (nearly) as close as any other we'd find." That's a bit crude, but you get the idea, I hope.
It's the same principle as used in games. If you can't do the real thing, fake it. It's okay as long as it looks good.
If that's not satisfactory, though, then you may go for the more exact algorithms that are known. Searching for some of them, as mentioned in the article I linked, will easily lead to interesting reading material, including algorithms.