I'm looking for a term-frequency analysis structure which is more efficient than a hash table in terms of worst-case performance and speed in practice. I specifically care about the operations insert and delete.

Some alternatives might be

Is there research using other data structures for the problem of gathering term-frequency statistics from a large corpus?

  • 1
    $\begingroup$ You can improve your chances of getting your question answered by being more specific and clear. What is term-frequency analysis and have you looked into what has usually been used? The data structures you list are very different, what are your requirements? Must it be persistent, thread-safe, space-efficient, ... ? Why can't you use a hash table? $\endgroup$ – Juho Mar 3 '12 at 9:53
  • $\begingroup$ Radix trees are a good alternative. I guess you read this: en.wikipedia.org/wiki/… ? $\endgroup$ – George Mar 3 '12 at 11:23
  • $\begingroup$ Space efficiency isn't at a requirement, all I care about theoretically is amortized worst-case asymptotic-complexity and practically speed. My lemma is that hashmaps are less efficient than a tree or trie structure for this specific tf calculation problem. $\endgroup$ – A T Mar 3 '12 at 11:38
  • 2
    $\begingroup$ When it comes to things running in practice, we tend to have our own conceptions, ideas and intuition of what is fast and what is not. However compilers and other systems are so complex, that we often don't really know unless we measure and test. Therefore I suggest starting with the hash table. If it doesn't meet your needs, then find out why that is, and try to improve on that. It might even give you a better idea of what your requirements really are and what is happening in your particular case. Could you explain or point me somewhere to understand your "tf calculation" problem? $\endgroup$ – Juho Mar 3 '12 at 11:59
  • 1
    $\begingroup$ @AT Find-Min will be O(1) worst-case, but arbitrary lookups in e.g. a binary heap may be O(n), since they aren't designed for that. $\endgroup$ – Joe Mar 4 '12 at 22:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.