it will be be helpful if you know the nature of the data set. In many cases, the median of a big data set is no much difference than the median of its subset. In network traffic analysis, we have observed that the median becomes stable fairly quickly, when we counted the sizes of transferred objects on network. So usually, we need only compute the median for the data objects in a small time window, and use it to represent the media for the whole day, or other long time ranges.