Big data nowadays is a fashionable topic, independently of what people mean when they use this term. The challenges include how to capture, transfer, store, clean, analyze, lter, search, share, and visualize such data. But being big is just a matter of volume, although there is no clear agreement in the size threshold where big starts. Indeed, it is easy to capture large amounts of data using a brute force approach. So the real goal should not be big data but to ask ourselves, for a given problem, what is the right data and how much of it is needed.1 For some problems this would imply big data, but for the majority of the problems much less data is necessary. In this position paper we explore the trade-o s involved and the main problems that come with big data: scalability, redundancy, bias, noise, spam, and privacy.
According to Wikipedia, \big data is a collection of data sets so large and complex that it becomes di cult to process using on-hand database management tools or traditional data processing applications". However, what really means on-hand database management tools or traditional data processing applications? Are we talking about terabytes or petabytes? In fact, a de nition of volume threshold based on current storing and processing capacities might be more reasonable. This de nition then may depend on the device. For example, big in the mobile world will be smaller than big in the desktop world.
Big data can be used in many applications. In the context of the Web, it can
be used to do Web search, to extract information, and many other data mining
problems. Clearly for Web search, big data is needed as we need to search over
the whole content of the Web. Hence, in the sequel, we will focus on data mining
problems, using the Web as main example. This is now called wisdom of crowds
when the data comes from people [
Recently we see a lot of data mining for the sake of it. This has been triggered by the availability of big data. Sometimes is valid to ask ourselves what is really interesting in a new data set. However, when people hammer a data set over and over again just because it is available, newer results become usually less meaningful. In some cases the results also belong to other disciplines (e.g. social insights) and there is no contribution to computer science (CS), but still people try to publish it in CS venues.
Good data mining is usually problem driven. For this we need to answer questions such as: What data we need? How much data we need? How the data can be collected? Today collecting data might be cheap and hence big data can be just an artifact of this step. After we have the data we need to worry about transferring and storing the data. In fact, transferring one petabyte even over a fast Internet link (say 100 Mbps) needs more than two years, too much time for most applications. On the other hand, today several companies store hundreds of petabytes and process dozens of terabytes per day.
When we have the data in place, another set of questions appears: Is all the data unique or we need to lter duplicates? Is the data trustworthy or there is spam? How much noise there is? Is the data distribution valid or there is a hidden bias that needs to be corrected? Which privacy issues must be taken care of? Do we need to anonymize the data?
After answering these questions we focus on the speci c mining task: Can we process all our data? How well our algorithm scale? The ultimate question will be related to the results and the usefulness of them. This last step is clearly application dependent.
Another subtle issue is that most of the time when we need to use big data, the problem is to nd the right data inside our large data. Many times this golden subset is hard to determine, as we need to discard huge amounts of data, where we have to deal again with bias, noise or spam. Hence, another relevant question is: How we process and lter our data to obtain the right data?
Hence, handling large amounts of data poses several challenges related to the questions and issues above. The rst obvious one is scalability, our last step. Privacy is also very relevant as it deals with legal and ethical restrictions. Other challenges come with the data content and its intrinsic quality, such as redundancy, bias, sparsity, noise, or spam. We brie y cover all these issues in the following sections.
There are many other aspects of big data that we do not cover, such as the complexity and heterogeneity of data, as they are outside the scope of this paper. 2
We can always collect and use more data thinking that more data will give improved results. In many cases that is true, but then transferring, storing, and processing larger amounts of data may not be feasible, as we challenge the bandwidth of the communication channels, the disk space of the computer infrastructure, and the performance of the algorithms used. As Internet bandwidth and storage has become cheaper, scaling the communication and hardware does not imply a proportional increase in cost. More data can also imply more noise as we discuss later.
On the other hand, the algorithms used to analyze the data may not scale. If the algorithm is linear, doubling the data, without modifying the system architecture, implies doubling the time. This might still be feasible, but for super linear algorithms most surely it will not. In this case, typical solutions are to parallelize and/or distribute the processing. As all big data solutions already run on distributed platforms, increasing the amount of data requires increasing the number of machines, which is clearly costly and proportional to the increase needed.
How else we can deal with more data? Well, another solution consists of developing faster (sometimes approximate) algorithms, at the cost of probably decreasing the quality of the solution. This becomes a clear option when the loss in quality is inferior to the improvements obtained with more data. That is, the time performance improvements should be larger than the loss in the solution quality. This opens a new interesting trade-o challenge in algorithm design and analysis for data mining problems.
One interesting example of the trade-o mentioned above is in lexical
tagging. That is, recognize all named entities in a text. The best algorithms are
super-linear but in [
Another important aspect of scalability is the processing paradigm that we
can use to speed-up our algorithms. This is application dependent, as the
degree of parallelization depends on the problem being solved. For example, not
all problems are suitable for the popular map-reduce paradigm [
Data can be redundant. Worse, usually it is. For example, in any sensor network
that tracks mobile objects, there will be redundant data for all sensors that are
nearby. In the case of the Web this is even worse, as we have lexical redundancy
(plagiarism) estimated in 25% [
In many cases when we use data samples, the sample can have some speci c
bias. Sometimes this bias can be very hard to notice or to correct. One of the
most well-known examples is click data in search engines, where the data is
biased by the ranking and the user interface (see for example [
Another interesting example of algorithm bias is tag recommendation. Imagine that we can recommend tags to new objects contributed by people (e.g. images). If we do so, in the long run, the recommendation algorithm will generate most tags, not the people. Hence, the resulting tag space is not really a folksonomy; it is a combination of a folksonomy and a machine-sonomy. This is a problem not only because we do not have a folksonomy anymore, but also because the algorithm will not be able to learn if there is not enough new data coming from users. 4
Many measures in the Web and other types of data follow a power law; so mining
big data works very well for the head of the power law distribution without
needing much data. This stops being true when the long tail is considered, because
the data is sparser. Serving long tail needs is critical to all users, as all users have
their shares of head and long tails needs as demonstrated in [
We can always try to improve results by adding more data, if available. Doing so, however, might not always be bene cial. For example, if the added data increases the noise level, results get worse. We could also reach a saturation point without seeing any improvements, so in this case more data is worthless.
Worsen results can also be due to Web spam. That is, actions done by users
in the form of content, links or usage, that are targeted to manipulate some
measurement in the Web. The main example nowadays is Web spam to improve
the ranking of a given website in a Web search engine [
Currently, most institutions that deal with personal data guarantee that this data is not shared with third parties. They also employ as much secure communication and storage as possible to promise their clients or users that personal information cannot be stolen away. In some cases, such as in Web search engines, they have devised data retention policies to reassure regulators, the media and, naturally, their users, that they comply with all legal regulations. For example, they anonymize usage logs after six months and they de-identify them after 18 months (that is, for example queries cannot be mapped to anonymized users). One of the problematic twists of data, even more for big data, is that in many cases a speci c user would prefer to forget past facts, especially in the context of the Web. This privacy concern keeps rising, especially with the advent of social networks.
Companies that use any kind of data are accountable to regulators such as the
Federal Trade Commission (FTC) in the United States or should comply with the
Data Protection Directive legislated in 1995 by the European Union Parliament.
Indeed, the FTC has de ned several frameworks for protecting consumer privacy,
especially online [
Numerous research e orts have been dedicated to data anonymization. A
favored one in large data sets is k-anonymity, introduced by Sweeney [
However, sometimes anonymizing data is not enough. One of the main
examples appears in the context of Web search engines. In this case, users are
concerned that their queries expose certain facets of their life, interests,
personality, etc. that they might not want to share. This includes sexual preferences,
health issues or even some seemingly minor details such as hobbies or taste in
movies that they might not be comfortable sharing with everybody. Queries and
3 We distinguish between noise that comes from the data itself, e.g., due to the
measurement mechanism, from spam, which can be considered as arti cial noise added
by humans.
clicks on speci c pages indeed provide so much information that the entire
business of computational advertising rely on these. Query logs and click data reveal
so much about users that most search engines stopped releasing logs to the
research community due to the infamous AOL incident. Indeed, a privacy breach
in query logs was exposed by two New York Times journalists who managed
to identify one speci c user in the anonymized log [
Today big data is certainly a trendy keyword. For this reason we have explored
many fundamental questions that we need to address when handling large
volumes of data. For the same reason this year the rst Big Data conferences are
being held, in particular the rst IEEE Big Data conference4. What is not clear
is the real impact that these conferences will have, and which researchers will be
attracted to them. As [
Acknowledgements We thank Paolo Boldi for his helpful comments. This research was partially supported by MICINN (Spain) through Grant TIN2009-14560-C03-01.