Timeline for Set combination data structure (And storage complexity)
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 23, 2017 at 12:37 | history | edited | CommunityBot |
replaced http://stackoverflow.com/ with https://stackoverflow.com/
|
|
| Sep 9, 2013 at 12:06 | history | edited | Raphael |
edited tags
|
|
| Sep 9, 2013 at 7:06 | vote | accept | firas | ||
| Sep 9, 2013 at 2:25 | answer | added | D.W.♦ | timeline score: 2 | |
| Sep 9, 2013 at 2:21 | comment | added | D.W.♦ | Please don't cross-post/duplicate the same question on two sites. This is especially frowned upon when (1) you are posting the same question on two sites within a short time period, or (2) you have already gotten answers on one site. Here, you asked on SO only yesterday, and you already got at least one answer. Instead of cross-posting, you should click the "flag" button underneath your question to ask the moderators to migrate the question to another site. | |
| Sep 8, 2013 at 22:04 | comment | added | firas | Please keep in mind that K is fixed but N changes over time. | |
| Sep 8, 2013 at 21:27 | comment | added | firas | Cool, but how did you calculate the complexity? And when you gave $$k\lceil {log}_{2}N \rceil$$, does it mean that the complexity is $$O(k {log}_{2}N)$$ ? (If you can post it as an answer it would be great ... I can tick it as accepted :) ) | |
| Sep 8, 2013 at 15:11 | comment | added | András Salamon | If you know that the keys come from some set with at most $N$ elements, and there are $k$ elements in each subset, then you may have to use $k\lceil \log_2 N\rceil$ bits for the unique subset identifiers in the worst case. A small saving is possible, but this is essentially tight from the information-theoretic bounds; it corresponds to simply running together the bit strings representing key identifiers. However, if the number $S$ of subsets is much smaller than $\binom{N}{k}$, then you could use $\lceil \log_2 S \rceil$ bits and this is optimal. | |
| Sep 8, 2013 at 5:53 | review | First posts | |||
| Sep 8, 2013 at 10:01 | |||||
| Sep 8, 2013 at 5:34 | history | asked | firas | CC BY-SA 3.0 |