Results 1 to 8 of 8
Thread: Incremental Deletion
- 05-17-2010, 02:23 PM #1
Incremental Deletion
Hi everyone
I'm looking for any ideas on Incremental Deletion with the min() aggregate. This is not a homework question if you're wondering. ;) Anyways, here it goes:
Let's say that we have a set of numbers and a data structure is used to store the minimum value such it can be recalculated after incremental deletion. In other words, if I've got one billion values, I don't want to rescan all of them to find the minimum.
I thought of storing the values in a binary search tree as the set grows. When a value is removed the minimum is just the left most leaf. It will not be O(logn) if it's not balanced however. I'm wondering if anyone has a better idea. ;)
Thank you :p
TimLast edited by tim; 05-17-2010 at 03:27 PM.
Eyes dwelling into the past are blind to what lies in the future. Step carefully.
- 05-17-2010, 02:32 PM #2
- Join Date
- Sep 2008
- Location
- Voorschoten, the Netherlands
- Posts
- 14,422
- Blog Entries
- 7
- Rep Power
- 29
Store them in a SortedMap (a TreeMap) where the key is the number itself and the value is the frequency the number occurrred in your sequence. I wonder if it can store a billion numbers though ...
kind regards,
Jos
- 05-17-2010, 02:36 PM #3
Hi Jos
So the SortedMap implements a tree structure sorted on keys. And if an element is removed and the frequency is zero, what then? How would you find the new minimum? This kind of problem is in terms of data warehouses, so one billion should be reasonable for a parallel machine. ;)
Thank you. ;)
TimLast edited by tim; 05-17-2010 at 02:47 PM.
Eyes dwelling into the past are blind to what lies in the future. Step carefully.
- 05-17-2010, 03:44 PM #4
Okay, we can have a frequency value to reduce the tree size. Now there will be a node for each unique value. Nodes can be stored in an AVL tree.
Wikipedia
In computer science, an AVL tree is a self-balancing binary search treeEyes dwelling into the past are blind to what lies in the future. Step carefully.
- 05-17-2010, 05:18 PM #5
- Join Date
- Sep 2008
- Location
- Voorschoten, the Netherlands
- Posts
- 14,422
- Blog Entries
- 7
- Rep Power
- 29
- 05-17-2010, 08:19 PM #6
Hi Jos
Ah, yes. Red-black trees have the balanced height property. A tree seems to be the way to go then. I was hoping for some simple method similar to binning or something, but for min/max problems, the leaves are handy. Keeping a sorted list is out of the question. :D But anyways.
Thank you Jos
TimEyes dwelling into the past are blind to what lies in the future. Step carefully.
- 05-17-2010, 08:58 PM #7
- Join Date
- Sep 2008
- Location
- Voorschoten, the Netherlands
- Posts
- 14,422
- Blog Entries
- 7
- Rep Power
- 29
- 05-18-2010, 08:39 AM #8
Hi Jos
I just thought of some hypothetical scenario. A data cube constructed from 1 TB of data will have large aggregates. I'm not sure if a billion could be in a cell, but the main issue is scalability.
Thanks for the ideas. ;)
TimEyes dwelling into the past are blind to what lies in the future. Step carefully.
Similar Threads
-
regarding deletion of spoon-feeding post
By Fubarable in forum Forum LobbyReplies: 7Last Post: 03-18-2010, 01:46 PM -
[SOLVED] Append an incremental number to variable name
By porchrat in forum New To JavaReplies: 7Last Post: 05-06-2009, 04:32 PM -
Deletion Servlet
By Java Tip in forum Java TipReplies: 0Last Post: 12-25-2007, 11:23 AM -
Massive Hit Deletion Help please
By quickfingers in forum Java 2DReplies: 1Last Post: 12-24-2007, 07:49 AM
Bookmarks