How has [or will] the prevalence of “big data” – the exploding plethora of information and computing power to correlate it – impact[ed] (i) the scientific method’s theory/hypothesis formation, (ii) the underdetermination thesis, and (iii) the realist/relativist/ constructivist debate? The question might profitably be bifurcated in terms of the social sciences and the physical sciences.
This is a partial answer only to (i), but its more than I can put in a comment:
I have seen work done on generating hypothesis from data mining the texts of large databases of biomedical papers in the bio-medical filed. The idea is pretty straight forward: Establish correlations between medical conditions on one hand and certain substances/enzymes/proteins etc... on the other hand, based on connections found in the literature that a human researcher wouldn't have time to discover systematically and could only stumble upon by accident. This allows researchers to search for previously unknown potential causes and/or cures for these conditions.
This doesn't challenge any epistemological principle per se, but the systemization of hypothesis formation ("That x molecule has an effect on y condition") does have interesting implications for the way science is conducted and the role of the scientist in the process.
There are some caveats: When I spoke to the researchers working on this in 2009, it was still a work in progress - no actual cures or solutions had been discovered using this method yet.
I asked can it be applied to other sciences besides the biomedical domain and was told that the format of biomedical publications was much more amenable to such procedures than other fields. Presumably at some point text mining technology will be advanced enough to be able to do this for domains such as physics or mathematics, etc.....
More recently, researchers at MIT, created a Data Science machine which "replaces" human intuition in the process of creating predictive models, again by mining correlations between the data in a systematic way. Their machine was able to compete against human data scientists, and beat most (but not all of them).
On a similar note, I've always wondered why mathematics and theoretical physics departments didn't hire a bunch of developers to set up large clusters churning through potential theorems (suitably encoded) and trying to prove or disprove them with genetic algorithms, simulated annealing or survey propagation. Whenever they stumbled upon a positive (i.e. a theorem that is true), they would bring in their human mathematicians to verify and then edit and publish the result if it is relevant.
This is a very interesting question that would seem to have both obvious answers and deeper ones. Since I know little about it, I can only pass along what amounts to hearsay.
Obviously, massive data crunching impacts the sorts of questions that can be asked and potentially falsified, more or less across the board. One interesting case is practical or "experimental" mathematics. Paul Erdos, it is said, refused to believe the "logically correct" answer to the "Monty Hall Problem" until the results of massively repeated trials were computed by brute force. And this seems epistemologically a very peculiar sort of development, a confirmation of a prediction not by "nature" but by a machine replication of the logic that proposed it.
Science is partly pattern recognition and partially observation of "objects." Like the telescope or microscope, data crunching "reveals" things that could not be seen before. But what are these things? The ontological status of a "correlation" that is purely statistical rather than linear and causal is now mainstream science, since Darwin or Boltzmann, but was still an unsettling development for many, such as Einstein.
As @AlexanderKing astutely points out, "correlations" are infinite and may have some potential to subvert the sort of "enabling constraint" offered by experiment. There was originally some question for his contemporaries as to whether Galileo's telescope was purely transmitting or actually constructing the "evidence" it presented. Since very little science can now be done without the "sensory apparatus" of massive data crunching, we seem to be slipping unavoidably into a more "constructivist" circle of confirming-predicting. Sorry, these are more musings than answers. I hope more are forthcoming.