Best way to structure data for efficient searching

[Roy Smith]

> On 3/28/2012 11:39 AM, Larry.Martell at gmail.com wrote:
> > I have a set of data that is contains 3 fields, K1, K2 and a
> > timestamp. There are duplicates in the data set, and they all have to
> > processed.
> >
> > Then I have another set of data with 4 fields: K3, K4, K5, and a
> > timestamp. There are also duplicates in that data set, and they also
> > all have to be processed.
> >
> > I need to find all the items in the second data set where K1==K3 and
> > K2==K4 and the 2 timestamps are within 20 seconds of each other.

In article <jlf92p$8dv$1 at dont-email.me>, John Nagle <nagle at animats.com> 
wrote:
> [some good ideas]
>    All of these approaches are roughly O(N log N), which
> beats the O(N^2) approach you have now.

If the timestamps are sparse enough, I can think of a way that's O(N), 
or pretty close to it.