Data volume is not the only criterion for using Hadoop. Big Data is often characterized by the 3 V's:
- velocity, and
More V's than these 3 have been invented since. I suppose the V's were a catchy way to characterize what is Big Data.
But as hinted, computational intensity is a perfect reason for using Hadoop (if your algorithm is computationally expensive). And, as hinted, the problem you describe is perfect for Hadoop, especially since it is embarrassingly parallel in nature.
Is Hadoop a good choice for you? I would argue, yes. Why? Because
- Hadoop is open source (compared with proprietary systems which may be expensive and black boxes),
- your problem lends itself well to the MapReduce paradigm (embarassingly parallel, shared-nothing),
- Hadoop is easily scalable with commodity hardware (as opposed to specialized hardware, and you should get linear speed-up in your performance with just throwing hardware at the problem, and you can just spin a cluster as needed on cloud service providers),
- Hadoop allows multiple client languages (Java is only one of many supported languages),
- there might be a library available already to do your cross-product operation, and
- you're shipping compute code, not data, around the network (which you should benefit from, and as opposed to other distributed platforms where you are shipping data to compute nodes which is the bottleneck).
Please note, Hadoop is not a distributed file system (as mentioned, and corrected already). Hadoop is distributed storage and processing platform. The distributed storage component of Hadoop is called the Hadoop Distributed File System (HDFS), and the distributed processing component is called MapReduce.
Hadoop has now evolved slightly. They keep the HDFS part for distributed storage. But they have a new component called YARN (Yet Another Resource Negotiator), which serves to appropriate resources (CPU, RAM) for any compute task (including MapReduce).
On the "overhead" part, there is noticeable overhead with starting/stopping a Java Virtual Machine (JVM) per tasks (map tasks, reduce tasks). You can specify for your MapReduce Jobs to reuse JVMs to mitigate this issue.
If "overhead" is really an issue, look into Apache Spark, which is part of the Hadoop ecosystem, and they are orders of magnitude faster than MapReduce, especially for iterative algorithms.
I have used Hadoop to compute pairwise comparisons (e.g. correlation matrix, similarity matrix) that are O(N^2) (n choose 2) in worst case running time complexity. Imagine computing the correlations between 16,000 variables (16,000 choose 2); Hadoop can easily process and store the results if you have the commodity resources to support the cluster. I did this using the preeminent cloud service provider (I won't name it, but you can surely guess who it is), and it cost me < $100 and under 18 hours.