 <p>Suppose your <code>dataObj</code> contains a unique ID field, then any set data structure would be fine for your job. The immutable data structures are primarily used for functional style code or persistency. If you don't need these two, you can use <code>HashSet&lt;T&gt;</code> or <code>SortedSet&lt;T&gt;</code> in the .Net collection library. </p> <p>Some stream specific optimization may be useful, e.g., keeping a fixed-size <code>Queue&lt;T&gt;</code>for the most recent data objects in the stream and store older objects in the more heavy weight set. I would suggest a benchmarking before switching to such hybrid data structure solutions. </p> <p><strong>Edit:</strong> </p> <p>After reading your requirements more carefully, I found that what you want is a queue with user-accessible indexing or backward enumerator. Under this data structure, your feature extraction operations (e.g. average/sum, etc) cost O(n). If you want to do some of the operations in O(log n), you can use more advanced data structures, e.g. interval trees or skip lists. However, you will have to implement these data structures yourself as you need to store meta information in the tree nodes which are behind collection API. </p>