Drawing Many Objects to Screen

Question

I'm working on a project in which we need to summarize a substantial amount of data in the form of a heat map. This data will be kept in a database for as long as possible. At some point, we will need to store a summary in a matrix (possibly?) before we can draw the blocks for the heat map to the screen. We are creating a windows form application with C#.

Let's assume the heat map is going to summarize a log file for an online mapping program such as google maps. It will assign a color to a particular address or region based on the number of times a request was made to that region/address. It can summarize the data at differing levels of detail. That is, each block on the heat map can summarize data for a particular address (max detail, therefore billions/millions of blocks) or it can summarize for requests to a street, city, or country (minimum detail -- few blocks as they each represent a country). Imagine that millions of requests were made for addresses. We have considered summarizing this with a database. The problem is that we need to draw so many blocks to the screen (up to billions, but usually much less). Let's assume this data is summarized in a database table that stores the number of hits to the larger regions. Can we draw the blocks to the window without constructing an object for each region or even bringing in all of the information from the db table? That's my primary concern, because if we did construct a matrix, it could be around 10 GB for a demanding request.

I'm curious to know how many blocks we can draw to the screen and what the best approach to this may be (i.e. direct3d, XNA). From above, you can see the range will vary substantially and we expect the potential for billions of squares that need to be drawn. We will have a vertical scroll bar to scroll down quickly to see other blocks.

Overall, I'm wondering how we might accomplish this with C#? Creating the matrix for the demanding request could require around 10 Gigabytes. Is there a way to draw to the screen that will not require a substantial amount of memory (i.e. creating an object for each block). If we could have the results of a SQL query be translated directly into rendered blocks on the screen, that would be ideal (i.e. not constructing objects, etc etc). All we need are squares and their only property is color and we might need to maintain a number for each block.

Note: We are pretty sure about how we will draw the heat map (how zooming, scrolling, etc should appear to user). To clarify, I'm more concerned about how we will implement our idea. Is there a library or some method that allows us to draw this many objects without constructing a billion objects and using Gigabytes of data. Each block is essentially a group of pixels (20x20) that are the same color. I don't believe this should necessitate constructing 1 billion objects.

Thanks!

Answer 1

I think technique you are looking for is called "virtualization". Now I don't mean hardware virtualization, but technique, where you create concrete visual object only for items, that are visible. Many grids and lists use this technique to show thousands of hundreds of items at normal speeds and memory consumption. You can also reuse those visual objects while swaping concrete data objects.

I would also question necesity of displaying bilions of details. You should make it similiar to zooming or agregation of data to show only few items and then let the user choose specific part or pice of data. But I guess you have that thought out.

Answer 2

If this is really for a graphic heat map, then I agree with the comments that an image that's at least 780 laptop screens wide is impractical. If you have this information in a SQL(?) database somewhere, then you can do a fancy query that partitions your results into buckets of a certain widths. The database should be able to aggregate these records into 1680 (pixels wide) buckets efficiently.

Furthermore, if your buckets are of a fixed width (yielding a fixed width heat-map image) you could pre-generate the bucket numbers for the "addresses" in your database. Indexed properly, grouping by this would be very fast.

If you DO need to see a 1:1 image, you might consider only rendering a section of the image that you're scrolled to. This would significantly reduce the amount of memory necessary to store the current view. Assuming you don't need to actually view all 780 screens worth of data at 100% (especially if you couple this with the "big picture view" strategy above) then you'll save on processing too.

The aggregate function for the "big picture view" might be MAX, SUM, AVG. If these functions aren't appropriate, please explain more about the particular features you'd be looking for in the heat-map.

As far as the drawing itself, you don't need "objects" for each box, you just need to draw the pixels on a graphics object.