Timeline for An efficient data structure supporting Insert, Delete, and MostFrequent
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 23, 2013 at 15:48 | answer | added | A T | timeline score: -3 | |
| Jan 12, 2013 at 5:47 | answer | added | jbapple | timeline score: 2 | |
| Nov 4, 2012 at 0:01 | comment | added | Joe | There are also some interesting structures in the streaming model. springerlink.com/content/t17nhd9hwwry909p | |
| Nov 3, 2012 at 18:15 | comment | added | vzn | there is not really a "most efficient solution" because there are usually only tradeoffs between which operations to optimize. ie you can pick which operation(s) you want to optimize. it also depends on characteristics of the data eg how much keys repeat etc. also usage profile eg are you doing a lot of one operation followed by intermittent occurrences of another, etc. your choice seems like an overall reasonable scheme. by strict stackexchange stds there is not really a "problem" stated here... | |
| Nov 3, 2012 at 18:08 | comment | added | Kaveh | @A.Schulz, mostly from data structures perspective. | |
| Nov 3, 2012 at 12:18 | comment | added | A.Schulz | Are you interested in a practical (implementable) solution or in theoretical bounds? | |
| Nov 3, 2012 at 10:13 | answer | added | Massimo Cafaro | timeline score: 7 | |
| Nov 3, 2012 at 8:14 | comment | added | Joe | @kaveh in place of the hash table, not the priority queue. MostFrequent should use the priority queue operation and still be O(1). | |
| Nov 3, 2012 at 2:27 | comment | added | Aryabhata | If using comparisons only, at least one of Insert/MostFrequent has to be amortized $\Omega(\log n)$, because of the lower bounds for element distinctness problem. | |
| Nov 2, 2012 at 22:48 | history | tweeted | twitter.com/#!/StackCompSci/status/264499337093070849 | ||
| Nov 2, 2012 at 21:52 | comment | added | Kaveh | @Bartek, hash table is for looking up and finding a data given a key, I don't see how priority queue is helpful there. Note that if we only cared about insert and delete then the standard solution would be a hash table giving Θ(1) for insert and delete. | |
| Nov 2, 2012 at 21:39 | history | edited | Kaveh | CC BY-SA 3.0 |
added 26 characters in body
|
| Nov 2, 2012 at 21:34 | comment | added | Kaveh | @Joe, using a BST in place of a hash table would make MostFrequent operations less efficient, but that might be a reasonable trade-off for memory. | |
| Nov 2, 2012 at 21:03 | comment | added | Bartosz Przybylski | Hash table uses a lot of unnessesary space, i would propose priority queue. It would give you the same time complexity on insert and delete but memory complexity would be better. | |
| Nov 2, 2012 at 20:00 | comment | added | Joe | You could use a simple balanced binary search tree instead of a hash table if you want. | |
| Nov 2, 2012 at 17:00 | history | asked | Kaveh | CC BY-SA 3.0 |