<p>In the context of Theoretical Computer Science, there are various strategies to (quickly) select the unique elements of a list, mainly comparison based and value based.</p>
<ul>
<li><strong>Value based</strong>: If computing a hash value of each record is cheap (i.e. constant time), the fastest solution is likely to be using a hash table of 2M records, and to process the 10M records in linear time.</li>
<li><strong>Comparison based</strong>: If computing a (good) hash value is more problematic (e.g. the records are very large), using a multi set sorting algorithm which is faster when there are many repetitions might be advantageous.</li>
</ul>
<p>See any algorithmic textbook (e.g. <a href="https://infolearners.com/ebooks/introduction-to-algorithms-clrs-pdf-free-download/" rel="nofollow noreferrer">CLRS</a> comes to mind) for an introduction to Hash tables. For sorting multisets while taking advantage of repetitions (and even of the entropy of the distribution of the frequencies of the elements), see <a href="https://www.semanticscholar.org/paper/Sorting-and-Searching-in-Multisets-Munro-Spira/6820064b996ecc361754d517c7007aae6106ab3f" rel="nofollow noreferrer">Munro and Spira's 1976 seminal article</a>, or <a href="https://arxiv.org/abs/1608.06666" rel="nofollow noreferrer">Barbay et al. synergistic sorting algoritm</a> (shameless self plug!) which takes optimally advantage of both (some measures of) input order and structure (i.e. the repetitions, down to the entropy of the distribution of frequencies).</p>
<p>I hope it helps! Take care!</p>

CC BY-SA 4.0
2022-06-23T10:11:27.463Z
2022-06-23T10:11:27.463Z
J.y B.y
<p>Suppose we have a dataframe with ~10M rows with ~9M duplicate records. What is the most time efficient way of selecting the unique records from this dataframe?</p>
<p>Some sort of sampling algorithm?</p>

CC BY-SA 4.0
2022-06-10T15:41:24.263Z
Your question does not seem to be about research in theoretical computer science and is thus off-topic here. You may try cs.SE. I would personally try hash-based techniques such as Bloom filter to solve this kind of problem.
holf
CC BY-SA 4.0
2022-06-10T18:29:43.953Z
Cross-posted: https://cs.stackexchange.com/q/152230/755, https://cstheory.stackexchange.com/q/51572/5038.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).  If you post on the wrong site, I would recommend you delete the copy on the wrong site before posting on a new one.
D.W.
CC BY-SA 4.0
2022-06-23T10:14:32.417Z
Would you be able to share such a (real) data set? I would be interested to run some experiments on it...
J.y B.y
<time-complexity><sorting><dc.distributed-comp>
Selecting unique records from a large dataframe with many duplicate records
Timeguy322
# Selecting unique records from a large dataframe with many duplicate records

(Asked by: username_0 on 2022-06-10)

Suppose we have a dataframe with ~10M rows with ~9M duplicate records. What is the most time efficient way of selecting the unique records from this dataframe?

Some sort of sampling algorithm?

**Tags:** time-complexity, sorting, dc.distributed-comp

> **Comments:**
> **username_1**: Your question does not seem to be about research in theoretical computer science and is thus off-topic here. You may try cs.SE. I would personally try hash-based techniques such as Bloom filter to solve this kind of problem.  
> **username_2**: Cross-posted: https://cs.stackexchange.com/q/152230/755, https://cstheory.stackexchange.com/q/51572/5038.  Please [do not post the same question on multiple sites](https://meta.stackexchange.com/q/64068).  If you post on the wrong site, I would recommend you delete the copy on the wrong site before posting on a new one.  
> **username_3**: Would you be able to share such a (real) data set? I would be interested to run some experiments on it...  

---

## 1 answers

### Answer by username_3 on 2022-06-23. Score: 1

In the context of Theoretical Computer Science, there are various strategies to (quickly) select the unique elements of a list, mainly comparison based and value based.

* **Value based**: If computing a hash value of each record is cheap (i.e. constant time), the fastest solution is likely to be using a hash table of 2M records, and to process the 10M records in linear time.
* **Comparison based**: If computing a (good) hash value is more problematic (e.g. the records are very large), using a multi set sorting algorithm which is faster when there are many repetitions might be advantageous.

See any algorithmic textbook (e.g. [CLRS](https://infolearners.com/ebooks/introduction-to-algorithms-clrs-pdf-free-download/) comes to mind) for an introduction to Hash tables. For sorting multisets while taking advantage of repetitions (and even of the entropy of the distribution of the frequencies of the elements), see [Munro and Spira's 1976 seminal article](https://www.semanticscholar.org/paper/Sorting-and-Searching-in-Multisets-Munro-Spira/6820064b996ecc361754d517c7007aae6106ab3f), or [Barbay et al. synergistic sorting algoritm](https://arxiv.org/abs/1608.06666) (shameless self plug!) which takes optimally advantage of both (some measures of) input order and structure (i.e. the repetitions, down to the entropy of the distribution of frequencies).

I hope it helps! Take care!


---

