<p>I'm looking for a <a href="http://en.wikipedia.org/wiki/Term-frequency" rel="nofollow">term-frequency analysis</a> 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 <strong>insert</strong> and <strong>delete</strong>.</p>

<p>Some alternatives might be</p>

<ul>
<li><a href="http://en.wikipedia.org/wiki/VList" rel="nofollow">VList</a></li>
<li><a href="http://en.wikipedia.org/wiki/Radix_tree" rel="nofollow">Radix tree</a></li>
<li><a href="http://en.wikipedia.org/wiki/Beap" rel="nofollow">beap</a></li>
<li><a href="http://en.wikipedia.org/wiki/Soft_heap" rel="nofollow">soft heap</a></li>
<li><a href="http://en.wikipedia.org/wiki/2-3_heap" rel="nofollow">2-3 heap</a></li>
<li><a href="http://en.wikipedia.org/wiki/Brodal_queue" rel="nofollow">Brodal queue</a></li>
<li><a href="http://en.wikipedia.org/wiki/Binary_heap" rel="nofollow">Binary heap</a></li>
<li><a href="http://en.wikipedia.org/wiki/Threaded_binary_tree" rel="nofollow">Threaded binary trees</a></li>
<li><a href="http://en.wikipedia.org/wiki/Ctrie" rel="nofollow">Ctries</a></li>
</ul>

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

CC BY-SA 3.0
2012-03-04T22:40:06.357Z
@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.
Joe
CC BY-SA 3.0
2012-03-05T13:46:30.813Z
Joe: But if inserts are guaranteed `O(1)` and nodes are guaranteed to be unique then I should be able to gather term-frequency statistics in `O(1)` by editing **insert()** to increment a node-unioned counter before adding or dropping said node.
A T
CC BY-SA 3.0
2012-03-03T09:53:44.313Z
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?
Juho
CC BY-SA 3.0
2012-03-03T11:23:34.300Z
Radix trees are a good alternative. 
I guess you read this: http://en.wikipedia.org/wiki/Radix_tree#Comparison_to_other_data_structures ?
George
CC BY-SA 3.0
2012-03-03T11:38:18.053Z
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.
A T
CC BY-SA 3.0
2012-03-03T11:59:38.103Z
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?
Juho
CC BY-SA 3.0
2012-03-03T12:54:52.217Z
[tf wikipedia article](http://en.wikipedia.org/wiki/Term-frequency). I plan on measuring and testing the two structures performance, this question is to figure out which structure would be best to test against.
A T
CC BY-SA 3.0
2012-03-03T13:15:51.323Z
@AT have you already seen chapter 22 on text classification on Russell & Norvig and the literature references therein? In addition, if a hash table supports all the operations you require, try it out first without comparing it with anything. There is no one hash table, but rather aspects you can tweak. I also think your question is too subjective. In my opinion anyone's intuition on what is good _in practice_ is as good as yours.
Juho
CC BY-SA 3.0
2012-03-03T14:29:02.320Z
I don't want to rely on there intuition, especially when there experience is from before these structures I'm advocating were invented. My intuition would be equally arbitrary. This is why I am using proper (industry-standard) metrics.
A T
CC BY-SA 3.0
2012-03-04T07:16:36.827Z
A lot of the data structures you listed have pretty poor insert / delete performance compared to, say http://en.wikipedia.org/wiki/Dynamic_perfect_hashing
Joe
CC BY-SA 3.0
2012-03-04T07:18:25.593Z
Also, a lot of the data structures you listed are implementations of priority queues... do you need a delete_min() operation?
Joe
CC BY-SA 3.0
2012-03-04T12:43:33.637Z
No I don't. The only reason I am looking at these priority-queues is that nodes are unique, and both lookup & insert are `O(1)` amortized worst-case.
A T
<ds.data-structures><time-complexity>
Optimal term frequency analysis
A T
# Optimal term frequency analysis

(Asked by: username_0 on 2012-03-03)

I'm looking for a [term-frequency analysis](http://en.wikipedia.org/wiki/Term-frequency) 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

* [VList](http://en.wikipedia.org/wiki/VList)
* [Radix tree](http://en.wikipedia.org/wiki/Radix_tree)
* [beap](http://en.wikipedia.org/wiki/Beap)
* [soft heap](http://en.wikipedia.org/wiki/Soft_heap)
* [2-3 heap](http://en.wikipedia.org/wiki/2-3_heap)
* [Brodal queue](http://en.wikipedia.org/wiki/Brodal_queue)
* [Binary heap](http://en.wikipedia.org/wiki/Binary_heap)
* [Threaded binary trees](http://en.wikipedia.org/wiki/Threaded_binary_tree)
* [Ctries](http://en.wikipedia.org/wiki/Ctrie)

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

**Tags:** ds.data-structures, time-complexity
> **Comments:**
> **username_2**: 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?  
> **username_3**: Radix trees are a good alternative.  I guess you read this: http://en.wikipedia.org/wiki/Radix_tree#Comparison_to_other_data_structures ?  
> **username_0**: 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.  
> **username_2**: 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?  
> **username_0**: [tf wikipedia article](http://en.wikipedia.org/wiki/Term-frequency). I plan on measuring and testing the two structures performance, this question is to figure out which structure would be best to test against.  
> **username_2**: @AT have you already seen chapter 22 on text classification on Russell & Norvig and the literature references therein? In addition, if a hash table supports all the operations you require, try it out first without comparing it with anything. There is no one hash table, but rather aspects you can tweak. I also think your question is too subjective. In my opinion anyone's intuition on what is good _in practice_ is as good as yours.  
> **username_0**: I don't want to rely on there intuition, especially when there experience is from before these structures I'm advocating were invented. My intuition would be equally arbitrary. This is why I am using proper (industry-standard) metrics.  
> **username_1**: A lot of the data structures you listed have pretty poor insert / delete performance compared to, say http://en.wikipedia.org/wiki/Dynamic_perfect_hashing  
> **username_1**: Also, a lot of the data structures you listed are implementations of priority queues... do you need a delete_min() operation?  
> **username_0**: No I don't. The only reason I am looking at these priority-queues is that nodes are unique, and both lookup & insert are `O(1)` amortized worst-case.  
> **username_1**: @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.  
> **username_0**: Joe: But if inserts are guaranteed `O(1)` and nodes are guaranteed to be unique then I should be able to gather term-frequency statistics in `O(1)` by editing **insert()** to increment a node-unioned counter before adding or dropping said node.  

---

## 0 answers

