Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I would like to do a following: I have a fairly large data set, say billions of rows, each row having multiple binary columns. I would like to generate estimated stats with some certainty about those rows. Stats would have a simple form: how many rows are there with columns 1, 7 and 10 set.

Obviously going through entries is not a viable solution. To be honest, I would prefer not touch the data set at all when I have to provide an estimation. I would like to precompute everything and then used precomputed data to answer questions about the data set. Do you know of any algorithms/techniques of solving such problem?

share|improve this question
1  
The crucial information you forgot to add is: in which physical form is this data set available? In a file or list of files (non-indexed)? In a (properly indexed) database? If you have the data set in non-indexed files, you cannot know how many rows there are with a certain property without reading them all. If the data is in a properly indexed relational data base, the task is a trivial SQL statement. If you are looking for a more general approach on creating stats for huge data sets, google for OLAP and "data warehouse". –  Doc Brown Mar 28 '13 at 7:23
    
Assume it's in a file and you can run a job over it, that should generate stats. Afterwards I don't want to touch the data set anymore to provide stats to users. –  gruszczy Mar 28 '13 at 16:43
    
if the rows are all the same size, then you can randomly address the data (advance reader to "X * size-of-row" bytes from beginning of each file). At that point you have a statistics problem, not a programming one. As you noted in your question, you only want to pull the samples once and save them for reuse. –  Dan Pichelman Mar 29 '13 at 15:20
    
One way of precomputation would be to create index tables. As all (?) of your columns are of type boolean, every index table would have one section with all "false" row-IDs, and one section with all "true" row-IDs. If the row-IDs are sorted, you can retrieve all relevant row-IDs faster than with a complete scan of your data. According to my recent experience, it takes less than 100s to evaluate some 6 million data records stored in a CSV file with a full scan. "billions of rows" would take several hours. You could use memory caching and concatenated multi-column indices to get this down. –  Axel Kemper Mar 29 '13 at 23:58
    
Thanks for ideas, guys! –  gruszczy Mar 30 '13 at 2:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.