Duplicate detection on very large data

Question

I'm very new to Java so forgive me if I'm doing something terribly wrong.

I'm working on a project where I need to quickly scan a very large volume of data (CSV with 50 million lines or more, 5 entries per line) for repeats. I've resorted to using a HashMap, since its .contains() method is fast.

However, I end up having to store a million keys or more in the map. Each key is associated with an int[] array, which would have from 1 to 100 entries as well. So obviously, I end up getting an OutOfMemory error unless I'm using a laptop with ~16 GB of RAM.

I was thinking that once the HashMap gets more than N keys or a key gets more than N entries, I could write it somewhere and clear it. However, not all keys or values are found at once, so I need to be able to add to the written hashmap, and not overwrite it.

I've searched far and wide and still can't find a way to do it, so thanks a lot to whoever can help!

Answer 1

You have quite a lot of options here, I'll list some of them:

1. More Memory: It sounds like you've already tried giving Java more memory, but if not, using the -Xmx compiler flag - e.g. -Xmx3G as Dimitry suggests will give you three gigabytes of heap, vs. the default which is <= 1GB.

2. Store Less Data: You're currently storing the whole row of "1 to 100 entries", when really all we need is to know if the data is unique or not. The Arrays.hashCode() function gives you a reasonably accurate indication that a row is unique in a single int, so we can put this to use to limit the amount of data you need to hold in memory:

   1. Construct two HashSet<Integer> objects, called seen and seenTwice. Loop over your data, and add each array's hash to seen, and to seenTwice if it was already in seen, like so:

      int[] arr = ... // construct the row's array
      int hash = Arrays.hashCode(arr);
      if(!seen.add(hash)) {
        // add returns false if we've already seen this hash
        seenTwice.add(hash);
      }
      

   2. Now we have a set of hashes that we saw two or more times; in theory, this will be a much smaller set than the number of rows in our file. We can let seen get garbage collected, and re-read the file using seenTwice to populate the HashSet<int[]> rows of actual data, like you were first trying to do:

      int[] arr = ... // construct the row's array
      int hash = Arrays.hashCode(arr);
      if(seenTwice.contains(hash)) {
        // If the hash isn't in seenTwice, we know it's not a duplicate
        if(!rows.add(arr)) {
          System.out.println("Row "+Arrays.toString(arr))+" is a duplicate!");
        }
      }
      

3. Use Bash: If you're willing to forgo Java, you can find duplicates very easily with a basic bash command:

   cat filename | sort | uniq -d
   

4. Use a Database: You can, like you were alluding, use some out-of-memory solution, notably a database. A good, easy to use Java database is H2, but covering using it is outside the scope of this answer. Suffice to say, you could load your data from the file into a database, and then simply query for duplicate rows: Finding duplicate values in a SQL table

   But setting up a DB simply to find duplicates in 50 million lines is overkill. I wouldn't reccomend this option.

---

See also: Script to find duplicates in a csv file

Answer 2

I am not aware of what exactly you want to do. But would it be of help if you used a SQL database? Then you could save your values externally, and you would not need this large amount of RAM.

If this is not applicable to you, it's unfortunate. When I read your question, I was sure that using a db would solve all your problems.

Answer 3

use phpmyadmin oe heideiSQL to upload data from CSV file

you can change the upload limit of phpmyadmin in .ini file Simple data insertion into database.

Fetch data from from database as java pojo objects and process it. Saves your memory