Filtering a sub set of (potentially) 1.000.000+ items

Question

I have a large dataset with possibly over a million entries. All items have an assigned time stamp and items are added to the set at runtime (usually, but not always, with a newer time stamp). I need to show a sub set of this data given a certain time range. This time range is usually quite small compared to the total data set, i.e. of the 1.000.000+ items not more than about 1000 are in that given time range. This time range moves at a constant pace, e.g. every second the time range is moved by one second. Additionally, the user may adjust the time range at any time ("move" through the data set) or set additional filters (e.g. filter by some text).

So far I wasn't worried about performance, trying to get the other things right, and only worked with smaller test sets. I am not quite sure how to tackle this problem efficiently and would be glad for every input. Thanks.

Edit: Used language is C# 4.

Update: I am now using a interval tree, implementation can be found here: https://github.com/mbuchetics/RangeTree

It also comes with an asynchronous version which rebuilds the tree using the Task Parallel Library (TPL).

What data structure you are using to store 1000000 + items ? — TalentTuner, Dec 10 '10 at 09:05
Is this a `DataSet` object or are you referring to a database when you say Dataset? — jvanrhyn, Dec 10 '10 at 09:06
mtrw: Yes. However, additional items are added constantly so it needs to be re-sorted. Saurabh: right now a simple Dictionary and a SortedList. jvanrhyn: neither, the data set is loaded from a file. — mbuchetics, Dec 10 '10 at 09:08
On the 8th day God created SQL. It was ugly at times, but worked. — , Dec 10 '10 at 09:13
why are you using SortedList ? and i assume you store items in the dictionary correct? — TalentTuner, Dec 10 '10 at 09:13
If you need to find bounds on a `SortedList` in `log(n)` time look at this code --> http://stackoverflow.com/questions/594518/is-there-a-lower-bound-function-in-c-on-a-sortedlist — digEmAll, Dec 10 '10 at 09:17
Multiple items are added every second. I am using a SortedList so I can view the "last XX items" faster. — mbuchetics, Dec 10 '10 at 09:19

Daniel Mošmondor · Answer 1 · 2010-12-10T10:34:56.970

3

We had similar problem in our development - had to collect several million items sorted by some key and then export one page on demand from it. I see that your problem is somehow similar.

For the purpose, we adapted the red-black tree structure, in the following ways:

we added the iterator to it, so we could get 'next' item in o(1)
we added finding the iterator from the 'index', and managed to do that in O(log n)

RB Tree has O(log n) insertion complexity, so I guess that your insertions will fit in there nicely.

next() on the iterator was implemented by adding and maintaining the linked list of all leaf nodes - our original adopted RB Tree implementation didn't include this.

RB Tree is also cool because it allows you to fine-tune the node size according to your needs. By experimenting you'll be able to figure right numbers that just fit your problem.

edited Dec 10 '10 at 10:34

answered Dec 10 '10 at 09:20

Daniel Mošmondor

19,718
12
58
99

1

+1 for mentioning the complexity and providing scientific background. – Aliostad Dec 10 '10 at 09:26
@Aliostad: I was keen to share my experience with it - we had a constraint that said that we should be able to get any page from it in less then 100 ms – Daniel Mošmondor Dec 10 '10 at 10:36
There's really no need to build your own data structure, though - any standard library should come with a sorted map primitive of some sort. – Nick Johnson Dec 13 '10 at 05:15
@NickJohnson there really was a need to roll-our-own, since every little bit of domain specific knowledge was able to help us squeeze some more, both from memory usage and CPU load. – Daniel Mošmondor Jul 21 '12 at 19:57
daniel how do you pronounce the funny looking S in your name? – Alex Gordon Oct 10 '12 at 20:21
@АртёмЦарионов sh -> as in haSH – Daniel Mošmondor Oct 10 '12 at 20:55

Aliostad · Answer 2 · 2010-12-10T09:26:13.973

1

Use SortedList sorted by timestamp.

All you have to is to have a implement a binary search on the sorted keys inside the sorted list to find the boundary of your selection which is pretty easy.

edited Dec 10 '10 at 09:26

answered Dec 10 '10 at 09:13

Aliostad

80,612
21
160
208

score 0 · Answer 3 · answered Dec 10 '10 at 09:08

0

Insert new items into a sorted list. This would let you select a range pretty easily. You could potentially use linq as well if you're familiar with it.

answered Dec 10 '10 at 09:08

JeffE

794
2
9
15

Filtering a sub set of (potentially) 1.000.000+ items

3 Answers3