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?
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ 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. $\endgroup$– holfJun 10 at 15:41
-
1$\begingroup$ Cross-posted: cs.stackexchange.com/q/152230/755, cstheory.stackexchange.com/q/51572/5038. Please do not post the same question on multiple sites. If you post on the wrong site, I would recommend you delete the copy on the wrong site before posting on a new one. $\endgroup$– D.W.Jun 10 at 18:29
-
$\begingroup$ Would you be able to share such a (real) data set? I would be interested to run some experiments on it... $\endgroup$– JérémyJun 23 at 10:14
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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 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, or Barbay et al. synergistic sorting algoritm (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!
