Jaroslav Pokorný
email: pokorny@ksi.mff.cuni.cz

Big Data Storage and Management: Challenges and Opportunities

Keywords: Big Data, NoSQL databases, MapReduce, Hadoop, Big Data 2.0, Big Analytics

The paper is focused on today's very popular theme -Big Data. We describe and discuss its characteristics by eleven V's (Volume, Velocity, Variety, Veracity, etc.) and Big Data quality. These characteristics represent both data and process challenges. Then we continue with problems of Big Data storage and management. Principles of NoSQL databases are explained including their categorization. We also shortly describe Hadoop and MapReduce technologies as well as their inefficiency for some interactive queries and applications within the domain of large-scale graph processing and streaming data. NoSQL databases and Hadoop M/R are designed to take advantage of cloud computing architectures and allow massive computations to be run inexpensively and efficiently. The term of Big Data 1.0 was introduced for these technologies. We continue with some new approaches called currently Big Data 2.0 processing systems. Particularly their four categories are introduced and discussed: General purpose Big Data Processing Systems, Big SQL Processing Systems, Big Graph Processing Systems, and Big Stream Processing Systems. Then, an attention is devoted to Big Analytics -the main application area for Big Data storage and processing. We argue that enterprises with complex, heterogeneous environments no longer want to adopt a BI access point just for one data source (Hadoop). More heterogeneous software platforms are needed. Even Hadoop has become a multi-purpose engine for ad hoc analysis. Finally, we mention some problems with Big Data. We also remind that Big Data creates a new type of digital divide. Having access and knowledge of Big Data technologies gives companies and people a competitive edge in today's data driven world.

Introduction

One rather subjective definition by Kushal Agraval1 says that Big Data can be as data that exceeds the processing capacity of conventional database systems. Consequently, its storage and processing require

• new data architectures, analytic environments,

• new analytical methods,

• new tools. In the business sphere, Big Data is data whose scale, distribution, diversity, and/or timelines require the use these new technologies to enable insights to new sources of business value.

Usually some examples from the commercial world are presented for documenting the size of Big Data. The most known example concerning the Google's database mentions gross total estimate of all data Google saved by 2016 as approximately 10EBytes 2 . A. Orlova stated in 2015 3 that Facebook generates about 10 TBytes every day, Twitter generates about 7 TBytes and some enterprises generate TBytes every single hour. In general, the digital universe is doubling in size every two years, and by 2020 -the data we create and copy annually -will reach 44 ZBytes or 44 trillion GBytes 4 . In the near future, the "Big Data" problem will begin to emerge in every enterprise.

We will consider Big Data for both data-at-rest as well as data-in-motion. For Big Data at rest we describe two kinds of systems: (1) NoSQL systems for interactive data processing; (2) systems for large scale analytics, e.g. decision support, based on MapReduce paradigm, represented by tools such as Hadoop. Hadoop-based systems enable to run long running decision support and analytical queries consuming and possible producing bulk data. Data-in-motion is the process of analyzing data on the fly without storing it. We utilize real-time processing methods in this case.

Today, users have a number of options associated with the above mentioned issues [START_REF] Pokorny | Database technologies in the world of Big Data[END_REF]. For storing and processing large datasets they can use:

• traditional parallel database systems (shared nothing architectures),

• distributed file systems and Hadoop technologies,

• key-value datastores (so-called NoSQL databases),

• new database architectures (e.g., NewSQL databases). The Big Data landscape is dominated by two classes of technologies: systems that provide operational capabilities, i.e. operation systems for real-time, interactive workloads where data is primarily captured and stored; and analytical systems that provide analytical capabilities for retrospective, complex analysis that may use most of all the data. Usually we talk about Big Data analytics (shortly Big Analytics). These classes of Big Data technology are complementary and frequently deployed together.

Big Data storage and processing are appropriate for cloud services. This approach reinforces requirements on the availability and scalability of computational resources offered by cloud services. Authors of [START_REF] Gupta | Cloud Computing and Big Data Analytics: What Is New from Databases Perspective[END_REF] highlight this role of cloud computing. Cloud has given enterprises the opportunity to fundamentally shift the way data is created, processed and shared.

The rest of the paper is organized as follows. Section 2 introduces traditionally some V´s characterizing Big Data and some immediate challenges arising from them. Section 3 provides basic characteristics of NoSQL databases. Section 4 shortly introduces principles of MapReduce and Hadoop technology (Big Data 1.0). Big Data 2.0 processing systems are discussed in Section 5. Section 6 is devoted to the most important part of Big Data application domain -Big Analytics. Some problems with the Big Data are presented in Section 7. Section 8 gives the conclusion.

Big Data Characteristics

Big Data is most often characterized by several V's. In [START_REF] Pokorný | Chapter 1 in Managing Big Data in Cloud Computing Environments[END_REF] we discussed eight such characteristics:

• Volume: Volume refers to the quantity of data generated and stored from various sources. Data scale in the range of TBytes to PBytes and even more. The big volume is not only a storage issue but also influences Big Analytics. Not only data samples, but often all data is captured for analysis. • Velocity: Both how quickly data is being produced and how quickly the data must be processed to meet demand (e.g. streaming data). For many applications, the speed of data creation is more important than the volume. For example, a well-known source of high-velocity data is social media. Twitter users are estimated to generate nearly 100,000 tweets every 60 seconds. what point is data no longer relevant to the current analysis. For example, an online e-commerce company may not want to keep a one year customer purchase history. The first three V's have been introduced by Gartner in [START_REF] Laney | 3D data management: Controlling data volume, velocity and variety[END_REF], the V associated with Veracity has been added by D. Snow in his blog [START_REF] Snow | Dwaine Snow's Thoughts on Databases and Data Management[END_REF]. The fifth V was introduced by Gamble and Goble in [START_REF] Gamble | Quality, Trust and Utility of Scientific Data on the Web: Toward a Joint model[END_REF]. Borne adds three other V's in [START_REF] Borne | Top 10 Big Data Challenges -A Serious Look at 10 Big Data V's[END_REF]:

• Venue: Considers distributed, heterogeneous data from multiple platforms, from different owners' systems, with different access and formatting requirements, private vs. public cloud. • Vocabulary: Includes schema, data models, semantics, ontologies, taxonomies, and other content-and context-based metadata that describe the data's structure, syntax, content, and provenance. • Vagueness: Concerns a confusion over the meaning of Big Data. Is it Hadoop?

Is it something that we've always had? What's new about it? What are the tools? Which tools should I use? etc. Not only V´s characterize Big Data. Often a quality is accentuated [START_REF] Nasser | Big Data Challenges[END_REF].

• Quality: Quality characteristic measures how the data is reliable to be used for making decisions. Saying that the quality of data is high or low is basically dependent on four parameters: a) Complete: all relevant data is available, for example all details of vendors like name, address, bank account, etc., exist b) Accurate: data is free of misspelling, typos, wrong terms and abbreviations c) Available: data is available when requested and easy to find d) Timely: data is up to date and ready to support decision. These characteristics are not independent. For example, veracity (confidence or trust in the data) drops when volume, velocity, variety and variability increase. Sometimes, a validity (additional V) is considered. Similar to veracity, validity refers to how accurate and correct the data is for its intended use.

The characteristics represent challenges related to data itself, i.e. data challenges [START_REF] Nasser | Big Data Challenges[END_REF]. The tasks like data acquisition, cleaning, curation, integration, storage, processing, indexing, search, sharing, transfer, mining, analysis, and visualization are called process challenges in [START_REF] Nasser | Big Data Challenges[END_REF].

We can find a lot of other characteristics of Big Data. For example, Tyrone Systems6 company distinguishes 10 Big Data challenges in two categories: cultural and technological. The former tackles the legal and ethical issues related to accessing data, e.g. privacy, security, and governance. In [START_REF] Nasser | Big Data Challenges[END_REF] they are called management challenges. The latter includes, in addition to the continued development of effective dealing with Big Data, putting results of Big Data Analysis in a presentable form for making decisions, i.e. it emphasizes a visualization and visual models.

NoSQL Databases

Considering Big Data we do not suppose an architecture with a database stored on the large disk. We refer to a much wider technology environment, which is coined under the term of Big Data Ecosystem (BDE) and relates to all interconnected parts, ranging from required infrastructure to data itself. A part of the BDE is represented by the NoSQL distributed databases. They include four main categories: key-value, columnoriented, document stores, and graph databases (see, e.g., [START_REF] Pokorný | Graph Databases: Their Power and Limitations[END_REF]). Their data models are different and they can hardly be categorized in a precise way. Some typical user characteristics of these categories can be described as follows:

• Key-value. A user can store and retrieve data using keys in schema-less way. A key is a unique identifier for some data item. The data items, so-called values, are stored against these keys. They may be, e.g., a scalar (string), a hash, a list, a set, a sorted set, etc. Technically, a key-value store is just a distributed persistent associative array (map). It is suitable for rapid access to unstructured data, but it is inefficient when querying or updating part of a value is necessary. Examples of these databases are Redis7 and Memcached8 . • Column-oriented. A column is a key-value pair, where the key is a qualifier and the value is related to the qualifier. A data row has a sortable row key and an arbitrary number of columns. Columns are often grouped into columns families. These databases are suitable for very rapid access to structured or semi-structured data. Their examples include well-known systems Cassandra9 and HBase10 . • Document datastores. Data is stored as documents. Documents are data structures composed of key-value pairs. Documents can contain many different key-value pairs, or key-array pairs, or even hierarchically nested document parts (usually in JSON-style). Sometimes, a document database can contain a number of document collections. Examples of document databases include MongoDB 11 and Amazon DynamoDB 12 . • Graph databases. Graph databases allow to store information about entities and relationships between these entities. In graph-oriented terms these databases use edges and nodes to represent and store data. These nodes are organized by some relationships with one another, which is represented by edges between the nodes. Both the nodes and the relationships have some defined properties. The most known graph database available is Neo4j13 and OrientDB 14 . There is DB-Engines indicative 15 to collect and present information on DBMSs. It provides a DB-engines ranking service which ranks DBMSs according to their popularity. The ranking is updated monthly. The examples of DBMSs presented above come from the first two places of ranking lists for particular categories.

MapReduce and Hadoop

Google introduced the MapReduce (M/R) [START_REF] Dean | MapReduce: Simplified Data Processing on Large Clusters[END_REF] framework in 2004 for processing massive amounts of data over highly distributed clusters of nodes. M/R represents a generic framework to write massive scale data applications. It involves writing two user defined generic functions: map and reduce. In the map step, a master node takes the input data and the processing problem, divides it into smaller data chunks and subproblems and distributes them to worker nodes. A worker node processes one or more chunks using the sub-problem assigned to it. Specifically, each map process takes a set of {key, value} pairs as input and generates one or more intermediate {key, value} pairs for each input key. In the reduce step, intermediate {key, value} pairs are processed to produce the output of the input problem. Each reduce instance takes a key and a set of values as input and produces output after processing a smaller set of values:

Map(k1,v1) → list(k2,v2) Reduce(k2, list(v2)) → list(k3,v3) Consequently, one of the main advantages of this approach is that it isolates the application from the details of running a distributed program, such as issues on data distribution, scheduling and fault tolerance.

Many NoSQL databases are based on Apache™ Hadoop Distributed File System16 (HDFS), which is a part so-called Hadoop software stack. HDFS is a massively distributed file system designed to run on cheap commodity hardware. Open-source software Hadoop17 is based on the M/R implementation along with HDFS.

The stack enables to access data by three different sets of tools in particular layers which distinguishes it from the universal DBMS architecture with only SQL API in the outermost layer. The NoSQL HBase is available as a column-oriented key-value layer with Get/Put operations as input. Hadoop M/R system server in the middle layer enables to create M/R jobs, i.e., programs in a programming language. It is often emphasised that writing custom M/R jobs is difficult and time-consuming. Consequently, high-level languages HiveQL, PigLatin, and Jaql are at disposal for some users at the outermost layer. HiveQL is an SQL-like language representing a subset of SQL92, and therefore can be simply understood by SQL users. Jaql is a declarative scripting language for analysing large semi-structured datasets. Pig Latin is not declarative. Whose programs are series of assignments similar to an execution plan for relational operations in a relational DBMS.

NoSQL databases and Hadoop M/R are designed to take advantage of cloud computing architectures and allow massive computations to be run inexpensively and efficiently. This makes operational Big Data workloads much easier to manage, and cheaper and faster to implement. Some NoSQL systems provide native M/R functionality that allows for analytics to be performed on operational data in place. The term of Big Data 1.0 was introduced for these technologies. Hadoop is its main representative.

Big Data 2.0 processing systems

For at least 10 years the M/R framework has represented the de facto standard for Big Data processing. Its fundamental principle is to move analysis to the data, i.e. to program applications in a data-centric fashion and not moving the data to an analytical system.

On the other, the research and development in the last years recognized some limitations of this approach. It is extremely complex to integrate, deploy, operate, and manage massive Hadoop environments. Hadoop cluster thinking requires special programmer skills to deploy the system and process data. Also, in processing large-scale structured data, several studies reported on the significant inefficiency of the Hadoop framework. The reason is that Hadoop is a file system built on batch processing. The Hadoop framework has also been shown to be inefficient within the domain of largescale graph processing and streaming data [START_REF] Bajaber | Big Data 2.0 Processing Systems: Taxonomy and Open Challenges[END_REF]. It confirms a similar situation in data processing history analyzed by Stonebraker in his famous paper [START_REF] Stonebraker | Technical perspective -One size fits all: an idea whose time has come and gone[END_REF] in context of traditional relational DBMSs. He makes the argument that the relational DBMS cannot be extended ad infinitum, demonstrates how RDBMSs are inappropriate for several new applications, and argues that the DBMS market will fragment into a series of special-purpose engines. Thus a new wave of domain-specific systems for Big Data management has occurred in last years. They constitute a new generation of systems referred as Big Data 2.0 processing systems [START_REF] Bajaber | Big Data 2.0 Processing Systems: Taxonomy and Open Challenges[END_REF][START_REF] Sakr | Big Data 2.0 Processing Systems -A Survey[END_REF]. Bajaber, et al. [START_REF] Bajaber | Big Data 2.0 Processing Systems: Taxonomy and Open Challenges[END_REF] distinguish four categories of Big Data 2.0 processing systems. General purpose Big Data processing systems. For example, Apache Spark 18 , is an open source Big Data processing framework built around speed, ease of use, and sophisticated analytics. In a survey19 nearly 70% of the respondents favoured Spark over dominating MapReduce, which is not appropriate to interactive applications or realtime stream processing.

Apache Spark provides programmers with an application programming interface centred on a data structure called the resilient distributed dataset (RDD), a read-only multiset of data items distributed over a cluster of machines that is maintained in a fault-tolerant way. It was developed in response to limitations in the M/R computing paradigm, which forces a particular linear dataflow structure on distributed programs. Spark's RDDs serve as a working set for distributed programs that offers a (deliberately) restricted form of distributed shared memory. Most of the SQL-on-Hadoop solutions access directly HDFS, i.e. not through M/R jobs. Query accelerators based on SQL-on-Hadoop and OLAP-on-Hadoop technologies are blurring differences between traditional warehouses to the world of Big Data.

Big Graph Processing Systems. Although graph processing algorithms can be written with M/R, this approach is not appropriate for this purpose and leads to inefficient performance. Apache Giraph24 is a graph-processing framework built on top of Hadoop. Giraph is based on the graph processing system Pregel [START_REF] Malewicz | Pregel: a system for large-scale graph processing[END_REF] by Google.

Big Stream Processing Systems. Stream computing is a new paradigm occurring in context of scenarios like mobile devices, location services and sensor pervasiveness. Data is usually generated from multiple sources and are sent asynchronously to servers. Now, a new category of Data Stream Management Systems occurs. They are developed for real-time processing of data-in-motion, e.g. for analysis of data streams.

Big Analytics

Big Analytics is the process of examining large data sets to uncover hidden patterns, unknown correlations, market trends, customer preferences and other useful business information. The analytical findings can lead to more effective marketing, better customer service, new revenue opportunities, improved operational efficiency, competi-tive advantages over rival organizations and other business benefits. This definition of Amazon Web Services25 emphasises clearly a purpose such analytics. Authors of [START_REF] Wu | Big Data Analytics = Machine Learning + Cloud Computing[END_REF] talk about Big Analytics as of the execution of machine learning tasks on large data sets in cloud computing environments.

In the previous chapters, we saw that there are some technologies combining analytics of Big Data with Hadoop. But enterprises with complex, heterogeneous environments no longer want to adopt a BI access point just for one data source (Hadoop). Answers to their questions are buried in a host of sources ranging from systems of records to cloud warehouses, to structured and unstructured data from both Hadoop and non-Hadoop sources, as it is emphasized in trends Big Data formulated by Tableau 26 . Incidentally, even relational DBMSs are becoming Big Data-ready. SQL Server 2016, for instance, recently added JSON support.

As regards actual Hadoop software, Tableau also emphasizes that it is no longer just a batch-processing platform for some analytical tasks. Hadoop has become a multi-purpose engine for ad hoc analysis. It is even being used for operational reporting on day-to-day workloads -the kind traditionally handled by data warehouses. There is a growing trend of Hadoop becoming a core part of the enterprise IT landscape. Making Hadoop data accessible to business users is now one of the biggest challenges.

Problems with Big Data

Kushal Agraval27 mentioned in his blog the following problems connected to Big Data technologies:

• Bigger data is not always better data. Quantity does not necessarily mean quality, see, e.g., data from social networks. Hence, the data filtering for useful information is a challenge in this context. • Big Data is prone to data errors. Sometimes errors or bias are undetected owing to the size of the sample and thus produce inaccurate results [START_REF] Tivari | Professional NoSQL[END_REF]. • Big Analytics is often subjective. There can be multiple ways to look at the same information and to interpret it differently by different users. • Not all the data is useful. It means, collecting data which is never used or which does not answer a particular question is relatively useless. • Accessing Big Data raises ethical issues. Both in industry and in academics the issues of privacy and accountability with respect to Big Data have now raised important concerns. • Big Data creates a new type of digital divide. Having access and knowledge of Big Data technologies gives companies and people a competitive edge in today's data driven world.

Conclusions

We conclude with the 10 hottest Big Data technologies based on Forrester's analysis from 201628 . They concern continuing development of NoSQL databases, distributed datastores, in-memory data fabric (dynamic random access memory, flash, or SSD), data preparation (sourcing, shaping, cleansing, and sharing diverse and messy data sets), and data quality. Data virtualization and data integration should contribute to delivering information from various data sources and to data orchestration across various exiting solutions (Hadoop, NoSQL, Spark, etc.). Additional technologies, i.e. predictive analysis, search and knowledge discovery, and stream analytics should support Big Analytics applications. On the other hand, the biggest challenge does not seem the technology itself. The more important problem is, how to have enough skills to make effective use of these technologies at disposal and make sense out of the data collected29 .

  The different meanings/contexts associated with a given piece of data is considered. Variability even refers to data whose meaning is constantly changing. Thus, variability is different from variety.• Volatility: How long the data is valid and how long should be stored, i.e. at

	• Visualization: Concerns visual representations and insights for decision mak-
	ing. For example, SAS offers five Big Data challenges related to visualization
	and Big Data 5 :
	o meeting the need for speed,
	o understanding the data,
	o addressing data quality,
	o displaying meaningful results, and
	o dealing with outliers.
	• Variability:
	• Variety: Data is of many format types -structured (e.g., call detail records in a
	telecom company), unstructured (product reviews on twitter), semi-structured
	(e.g., graph data), media, etc. Data does not come only from business transac-
	tions, but also from machines, sensors, GPS signals from cell phones, and oth-
	er sources, making it much more complex to manage. There is a need to inte-
	grate this data together. From the analytics perspective, variety of data is the
	biggest challenge to effectively use it. It is becoming the single biggest driver
	of Big Data investments. Technically, some connectors are becoming crucial in
	integration of different data.
	• Veracity: Managing the reliability and predictability of inherently imprecise
	data, e.g. to test many different hypotheses, vast training samples, etc. It means
	data needs to be cleaned before it can be integrated.
	• Value: Indicates if the data is worthwhile and has value for business. Data val-
	ue vision includes creating social and economic added value based on the in-
	telligent use, management and re-uses of data sources with a view to increase
	business intelligence (BI). Also, an attention must be paid to the investment of
	storage for data. For example, storage may be cost effective and relatively
	cheaper at the time of purchase but it can be unreliable. Saving money can
	cause a risk in this case.

  Companies like ORACLE and SAP talk even about Big Data Management Systems. Big SQL Processing Systems. SQL-on-Hadoop is a class of analytical application tools that combine established SQL-style querying with newer Hadoop data framework elements. Some examples of this technology: • HadoopDB 20 is a hybrid combining a parallel database with Hadoop. It translates SQL queries into M/R jobs and optimizes query plans. It uses Postgres on a communication level and Hive on the translation level. • HPE Vertica SQL on Apache Hadoop® 21 offers to perform SQL queries on Hadoop data. • Splice Machine 22 is a Hadoop-relational DBMS. It uses HBase and HDFS as a file system. It supports real-time ACID transactions. • BigSQL 23 is PostgresSQL implemented on Hadoop.

https://kushalagrawal.com/blog/big-data/

https://www.quora.com/How-big-is-Googles-database/

http://blog.azoft.com/telcos-gain-valuable-insight-with-big-data/

https://www.emc.com/leadership/digital-universe/2014iview/executive-summary.htm

https://www.sas.com/resources/asset/five-big-data-challenges-article.pdf

http://blog.tyronesystems.com/the-top-10-big-data-challenges/

https://redis.io/

http://memcached.org/

http://cassandra.apache.org/

http://hbase.apache.org/

https://www.mongodb.com/

https://aws.amazon.com/dynamodb/

https://neo4j.com/

http://www.orientechnologies.com/

http://db-engines.com/en/

http://hadoop.apache.org/docs/r0.18.0/hdfs_design.pdf

http://hadoop.apache.org/

https://spark.apache.org/

http://www.syncsort.com/en/About/News-Center/Press-Release/New-Hadoop-Survey-Identifies-Big-Data-Trends

http://db.cs.yale.edu/hadoopdb/hadoopdb.html

https://www.vertica.com/

https://www.splicemachine.com/

https://www.bigsql.org/

http://giraph.apache.org/

http://searchbusinessanalytics.techtarget.com/definition/big-data-analytics

https://www.tableau.com/sites/default/files/media/Whitepapers/whitepaper_top_10_big_data_ trends_2017.pdf

https://kushalagrawal.com/

http://www.forbes.com/sites/gilpress/2016/03/14/top-10-hot-big-datatechnologies/#5b66b0327f26

29 http://www.ebusinessbook.nl/185

Acknowledgments. This work was supported by the Charles University project Q48.


Ahmed Kamoun
email: ahmed.kamoun@imt-atlantique.net

Patrick Maillé
email: patrick.maille@imt.fr

Bruno Tuffin
email: bruno.tuffin@inria.fr

Evaluating search engines and defining a consensus implementation

come

Introduction

Search Engines (SEs) play a crucial rule in the current Internet world. If you wish to reach some content, except if you have a specific target in mind, you dial keywords on an SE through a web browser to discover the (expected) most relevant content. The number of searches worldwide per year is not precisely known, but just talking about Google, it is thought that they handle at least two trillions of requests per year, and that it can even be much more than that1 . As a consequence, if you are a small content provider or a new comer, your visibility and business success will highly depend on your ranking on SEs.

SEs are regularly accused of biasing their rankings 2 by not only trying to provide as an output an ordered list of links based on relevance, but to also include criteria based on revenues it could drive. The problem was brought in 2009 by Adam Raff, co-founder of the price-comparison company Foundem, saying that Google was voluntarily penalizing his company in rankings with respect to Google's own services. Such a behavior would indeed be rational from the SE perspective, as it could yield significant revenue increases; a mathematical model highlighting the optimal non-neutral-i.e., not based on relevance only-strategies of SEs is for example described in [START_REF] L'ecuyer | Revenue-maximizing rankings for online platforms with quality-sensitive consumers[END_REF]. The issue led to the use of expression search neutrality debate, in relation to the net neutrality debate where Internet Service Providers are accused of differentiating service at the packet level to favor some applications, content, or users. Indeed, similarly, new valid content can hardly be reached if not properly considered by SEs. This is now an important debate worldwide [START_REF]Inria's response to ARCEP consultation about network neutrality[END_REF][START_REF] Maillé | Telecommunication Network Economics: From Theory to Applications[END_REF][START_REF] Wright | Defining and measuring search bias: Some preliminary evidence[END_REF]. But while defining a neutral behavior of ISPs at the network level is quite easy, a neutral behavior for SEs involves having a clear definition of relevance. Up to now this relevance is defined by SE-specific algorithms such as PageRank [START_REF] Page | The pagerank citation ranking: Bringing order to the web[END_REF], that can additionally be (and are claimed to be) refined by taking into account location, cookies, etc. The exact used algorithms and their relation to relevance are sometimes hard to know without requiring a total transparency of SEs and free access to their algorithms, which they are reluctant to disclose.

Because of the different used algorithms, it is interesting to compare search engines, for example by giving them a grade (or score). It is often said that if someone is not happy, she can just switch, she is just one click away from another SE. But while it could be true in a fully competitive market, it is not so easy in practice with SEs since most people just know one or two SEs and do not have a sufficient expertise to evaluate them and switch. As of May 2018, Statcounter Global Stats3 gives worldwide a market share of 90.14% to Google, 3.24% to Bing, 2.18% to Baidu, 2.08% to Yahoo!... Our paper has several goals:

• First, to propose a so-called consensus SE, defined such as some "average" behavior of SEs, based on the idea that this average SE should be closer to one truly based on relevance. Considering a list of several SEs, we give a score to all the provided links, by weighing them by the position click-through-rate on each SE, estimating the position-dependent probability to be clicked. The consensus SE then ranks links according to their score.

• To give a score to SEs, comparing their results to the consensus SE. From the score of links, we can give a score to SEs by summing the scores of the presented lists weighted by their positions. It then allows us to rank the SEs themselves and show which one seems the closest to the "optimal" consensus SE, for a single keyword and for a list of keywords.

• To discuss and compare the behavior of SEs with respect to requests in practice. We have implemented and tested our model, computing grades for SEs and distributions of scores in terms of requests. From the rankings of SEs for any keyword, we can also investigate if there is a suspect deviation of some SEs toward their own content with respect to competitors. This would help to detect violations to a (potential) search neutrality principle.

Note that algorithms comparing rankings exist in the literature, see [START_REF] Mowshowitz | Measuring search engine bias[END_REF] and references therein, based on differences between vectors, but there is to our knowledge no algorithm like ours taking into account the click-through-rates (weights) associated to positions. The rest of the paper is organized as follows. Section 2 presents the model: the definition of link scores for any keyword, the corresponding SE score as well as the consensus SE. Section 3 presents an implementation of this model in practice and compares the most notable SEs. Finally, Section 4 concludes this preliminary work and introduces the perspectives of extension.

Scoring model and consensus search engine

We consider n SEs, m keywords representative of real searches, and a finite set of ℓ pages/links corresponding to all the results displayed for the whole set of searches. When dialing a keyword, SEs rank links. We will limit ourselves to the first displayed page of each SE, considered here for simplicity the same number a for all SEs, but we could consider different values for each SE, and even a = ℓ.

The ranking is made according to a score assigned to each page for the considered keyword. This score is supposed to correspond the relevance of the page. According to their rank, pages are more or less likely to be seen and clicked. The probability to be clicked is called the clickthrough-rate (CTR) [START_REF] Maillé | An overview of research on sponsored search auctions[END_REF]; it is in general SE-, position-and link-dependent, but we assume here for convenience, and as commonly adopted in the literature, a separability property: the CTR of link i at position l is the product q ′ i q l of two factors, q ′ i depending on the link i only, and q l depending on the position l only. We typically have q 1 ≥ q 2 ≥ • • • ≥ q a . The difficulty is that the link-relative term q ′ i , upon which a "neutral" ranking would be based, is unknown. But the position-relative terms q l can be estimated, and we assume in this paper that they are known and the same on all SEs, i.e, that SEs' presentation does not influence the CTR. We then make the following reasoning:

• SEs favor the most relevant (according to them) links by ranking them high, that is, providing them with a good position and hence a high visibility, which can be quantified by the positionrelative term q l ;

• for a given keyword, a link that is given a high visibility by all SEs is likely to be "objectively relevant". Hence we use the average visibility offered by the set of SEs to a link, as an indication of the link relevance for that keyword. We will call that value the score of the link for the keyword, which includes the link-relative term q ′ i .

• We expect that considering several SEs will average out the possible biases introduced by individual SEs, when estimating relevance; also, the analysis may highlight some SEs that significantly differ from the consensus for some sensitive keywords, which would help us detect non-neutral behaviors.

Page score

The notion of score of the page as defined by SEs is (or should) be related to the notion of relevance for any keyword. As briefly explained in the introduction, the idea of relevance is subjective and depends on so many possible parameters that it can hardly be argued that SEs do not consider a valid definition without knowing the algorithm they use. But transparency is very unlikely because the algorithm is the key element of their business. In this paper, as explained above we use a different and original option for defining the score, as the exposition (or visibility) provided by all SEs, which can be easily computed.

Formally, for page i and keyword k, the score is the average visibility over all considered SEs:

R i,k := 1 n n j=1 q πj (i,k) (1)
where π j (i, k) denotes the position of page i on SE j for keyword k. In this definition, if a page is not displayed by an SE, the CTR is taken as 0. Another way to say it is to define a position a + 1 for non displayed pages, with q a+1 = 0.

Search engine score

Using the score of pages (corresponding to their importance), we can define the score of an SE j for a given keyword k as the total "page score visibility" of its results for that keyword. Mathematically, that SE score S j,k can be expressed as

S j,k := pages i q πj (i,k) R i,k ,
where again q p = 0 if a page is ranked at position p ≥ a + 1 (i.e., not shown), and for each page i, R i,k is computed as in Eq. ( 1).

The SE score can also be computed more simply, by just summing on the displayed pages:

S j,k = a p=1 q p R πj (p,k),k (2)
where πj (p, k) is the page ranked at the p th position by SE j for keyword k, i.e., πj (•, k) is the inverse permutation of π j (•, k).

The higher an SE ranks highly exposed pages, the higher its score. The score therefore corresponds to the exposition of pages that are well-exposed on average by SEs.

To define the score of SE j, for the whole set of keywords, we average over all keywords:

S j := 1 m m k=1 S j,k . (3)

Consensus search engine

From our definitions of scores in the previous subsection, we can define the consensus SE as the one maximizing the SE score for each keyword. Formally, for a given keyword k, the goal of the consensus SE is to find an ordered list of the ℓ pages (actually, getting the first a is sufficient), where π (k) (p) is for the page at position p, such that

π (k) (•) = argmax π(•) a p=1 q p R π(p),k .
Note that this maximization is easy to solve: it suffices to order the pages such that R π

(k) (1),k ≥ R π (k) (2),k ≥ • • • , i.e.
, to display pages in the decreasing order of their score (visibility). The total score of the consensus SE can then also be computed, and is straightforwardly maximal.

Analysis in practice

We have implement in Python a web crawler that looks, for a set of keywords, the results provided by nine different search engines. From those results, the scores can be computed as described in the previous section, as well as the results and score of a consensus SE. The brute results can be found at https://partage.mines-telecom.fr/index.php/s/aG3SYhVYPtRCBKH. The code to get page URLs is adapted to each SE, because they display the results differently. It also deals with results display that can group pages and subpages (that is, lower level pages on a same web site) that could be treated as different otherwise. Another solved issue is that a priori different URLs can lead to the same page. It is for example the case of http://www.maps.com/FunFacts.aspx, http://www.maps.com/funfacts.aspx, http://www.maps.com/FunFacts.aspx?nav=FF, http: //www.maps.com/FunFacts, etc. It can be checked that they actually lead to the same web page output when accessing the links proposed by the SEs. Note on the other hand that it requires a longer time for our crawler to get to each page and check whether the URL gets modified.

We (arbitrarily) consider the following set of nine SEs among the most popular, in terms of number of requests according to https://www.alexa.com/siteinfo:

• Google • Yahoo! • Bing • AOL • ask.com • duckduckgo • Ecosia • StartPage • Qwant.
We include SEs such as Qwant or StartPage, which are said to respect privacy and neutrality. We also clear the cookies to prevent them from affecting the results (most SEs use cookies to learn our preferences).

We consider 216 different queries included in February 2018 common searches. The choice is based on the so-called trending searches in various domains according to https://trends. google.fr/trends/topcharts. We arbitrarily chose keywords in different categories to cover a large range of possibilities.

We limit ourselves to the first page of search engines results, usually made of the first 10 links. That is, we let a = 10. The click-through rates q p are set as measured in [START_REF] Dejarnette | Click-through rate of top 10 search results in Google[END_REF] and displayed in Table 1.

q 1
q 2 q 3 q 4 q 5 q 6 q 7 q 8 q 9 q 10 0.364 0.125 0.095 0.079 0.061 0.041 0.038 0.035 0.03 0.022 Table 1: CTR values used in the simulations, taken from [START_REF] Dejarnette | Click-through rate of top 10 search results in Google[END_REF]

Search engines scores

Table 2 provides the average scores of the nine considered search engines, as well as that of the consensus SE, according to Eq. (3). We also include the 95% confidence intervals that would be obtained (abusively) assuming requests are independently drawn from a distribution on all possible requests. Under the same assumption, we can also implement statistical tests to determine whether the scores of search engines are significantly different. The corresponding p-values are given in Table 3. For two search engines, the p-value is the probability of error when rejecting the hypothesis they have similar scores. A small value indicates a statistically significant difference between both search engines (1% means 1% chance of error). We can remark a group of four SEs with scores above the others: DuckDuckGo, Yahoo!, Ecosia, and AOL, around 0.11. The statistical analysis using the p-value allows to differentiate even more, with DuckDuckGo and Yahoo! as a first group, and Ecosia, and AOL slightly below. Then, Bing and Qwant get scores around 0.09 (and can not be strongly differentiated from the p-value in Table 3)), and Google and StartPage around 0.082 (since StartPage is based on Google, close results were expected). Finally, quite far from the others, Ask.com has a score around 0.02.

The consensus SE has a score of 0.133, significantly above all the SEs as shown in Table 3.

Analysis

Figure 1 displays by SE the percentage of common results with the consensus SE for each position range. Again for all our searched keywords, we count the proportion of links in the 1 st position correspond to the link in 1 st position in the consensus SE, then do the same for the first 2 positions, then for the first 3, etc. We also draw in Figure 2 the distribution of the score of SEs relatively to the consensus where on the x-axis, we have the pages ordered (for each SE) by the relative score from the largest to the smallest.

It allows to see the variations of score per SE. Again the same SE groups appear, but the information is stronger than just the mean. For the first quarter of requests, scores are close for all SEs except Ask.com, the difference becomes significant later with some SEs which cannot keep up with he best ones.

To identify deviations from other search engines, we highlight respectively in Tables 4 and5 for each SE the (ordered) 10 queries with the highest and lowest relative score with respect to the consensus SE. Those queries correspond to the extreme left (for Table 4) and extreme right (for Table 5) of Fig. 2.

Search terms displayed in Table 4 appear to be quite complex-or specific-searches, for which there is not much room for disagreement among SEs.

On the other hand, Table 5 shows, for each SE, the terms for which they most disagree with the consensus, which may help highlight non-neutral behaviors. For example, it is interesting to note that Bing, the Microsoft-operated SE, differs most from the consensus (hence, from the other SEs) on some sensitive searches such as skype, gmail, youtube, and facebook. Similarly, AOL strongly disagrees with the consensus for yahoomail, mail, and messenger. While Qwant gets low scores for google maps, msn, outlook, news, google drive, skype, and gmail, all involving SE-controlled services. Finally, let us note that we may also have a look at searches like restaurant or cnn, for which Google is far from the consensus: is that to favor its own news and table-booking services? Our study is too preliminary to draw definite conclusions, but can help raise such questions.

Conclusions

In this paper, we have defined a measure of relevance of web pages for given queries based on the visibility/response from a whole set of search engines. This relevance takes into account the position of the web page thanks to a weight corresponding to the click-through-rate of the position. It then allowed to define a score of a search engine for a given query, and the average score for a whole set of queries.

We designed a tool in Python allowing to study the scores of nine known search engines and to build the consensus ranking maximizing the SE score, for a set of more that two hundred queries. A first analysis suggests that there are significant differences among search engines, that may help identify some sensitive terms subject to biases in the rankings.

We finally note that our method does not provide an absolute-value score for each SE allowing to decide which is the best one, but rather indicates whether an SE agrees with the others. The user may very well prefer an SE that is far from our consensus ranking, especially if that SE better takes her preferences into account when performing the ranking.

In a follow up of this preliminary work, we plan to design statistical tests of potentially intentional deviations by search engines from their regular behavior, to highlight if non-neutrality by search engines can be detected and harm some content providers. This would be a useful tool within the search neutrality debate.

Figure 1 :

 1 Figure 1: Similarities in position with the consensus

Figure 2 :

 2 Figure 2: Distribution of scores relative to the consensus, from largest to smallest.

Table 2 :

 2 SE scores, and 95% confidence intervals half-widths.

	SE	Score
	Google	0.0832 ± 0.0045
	Yahoo	0.1103 ± 0.0030
	Bing	0.0933 ± 0.0045
	AOL	0.1055 ± 0.0036
	Ask	0.0211 ± 0.0006
	DuckDuckGo 0.1106 ± 0.0029
	Ecosia	0.1071 ± 0.0033
	StartPage	0.0816 ± 0.0046
	Qwant	0.0906 ± 0.0048
	Consensus	0.1332 ± 0.0026

Table 3 :

 3 p-values for the tests comparing the average scores of search engines (T-test on related samples of scores).

		Yahoo	Bing	AOL	Ask	DuckDuckGo	Ecosia	StartPage	Qwant	Consensus
	Google	1.3e-38	5.5e-05	9.7e-24	7.7e-70	6.3e-42	5.4e-30	1.3e-01	5.4e-03	6.8e-82
	Yahoo		5.0e-23	3.5e-08	1.5e-131	5.4e-01	1.9e-04	1.0e-40	2.4e-25	2.4e-129
	Bing			5.8e-11	2.6e-81	3.1e-23	2.8e-15	6.6e-06	6.1e-02	4.0e-70
	AOL				6.1e-112	3.9e-07	1.3e-01	2.0e-26	1.9e-13	1.6e-78
	Ask					4.5e-135	5.1e-120	4.5e-67	8.3e-75	4.0e-163
	DuckDuckGo						4.5e-05	4.5e-42	4.4e-25	1.4e-130
	Ecosia							5.6e-32	1.8e-17	2.0e-91
	StartPage								9.4e-04	2.3e-82
	Qwant									1.6e-67

Table 4 :

 4 Per SE, ordered list of 10 queries with the largest relative score with respect to the consensus (and their relative scores)

	Google		Yahoo		Bing	AOL		Ask		DuckDuckGo Ecosia		StartPage	Qwant
	(0.2219)		(0.2686)		(0.1713)	(0.2576)		(0.115)		(0.4272)		(0.2803)		(0.1533)	(0.1469)
	convertidos	yahoomail	skype	when is fa-	how	to	traduttor		bbc news	beeg	google
						thers day		take	a					maps
								screenshot
								on a mac
	(0.2309)		(0.44)		(0.2025)	(0.2581)		(0.1153)		(0.5306)		(0.3822)		(0.1647)	(0.1533)
	how	to	mail		ikea	yahoomail	what is my	how many	where are	convertidos	minecraft
	draw	a						ip address	ounces in a	you now
	doghow to								quart
	get rid of
	blackheads
	(0.2322)		(0.5195)		(0.2287)	(0.2609)		(0.1179)		(0.5929)		(0.4572)		(0.2158)	(0.1564)
	restaurant	how	to	gmail	traductor		how	to	how	to	how	to	daily mail	msn
			make love		google		screenshot	start	a	make
								on mac		business		money
	(0.2564)		(0.5607)		(0.2301)	(0.2862)		(0.1183)		(0.6261)		(0.4779)		(0.2213)	(0.1712)
	how many	who sings	youtube	when	is	football as-	messenger	games		omegle	news
	ounces in a	this song			mothers		sociation
	quart					day
	(0.2686)		(0.6264)		(0.2318)	(0.2936)		(0.1188)		(0.6319)		(0.5005)		(0.2334)	(0.1801)
	cnn		messenger	youtube	where are	juegos		hotmail		how tall is	restaurant	google
					mp3	you now						kevin hart	drive
	(0.28)		(0.6351)		(0.2332)	(0.3147)		(0.119)		(0.6739)		(0.5194)		(0.2416)	(0.1844)
	ryanair		oranges		pokemon	mail		how many	who sings	tiempos		how	to	outlook
					go			centimeters	this song				make love
								in an inch
	(0.2957)		(0.6552)		(0.2452)	(0.3156)		(0.1192)		(0.6757)		(0.5219)		(0.2424)	(0.1957)
	putlocker		how do you	ryanair	messenger	irctc		euro 2016	myn		ryanair	skype
			spell
	(0.3033)		(0.6756)		(0.2928)	(0.3196)		(0.1193)		(0.7268)		(0.5238)		(0.2591)	(0.2063)
	what time	euro 2016	aleg	what	is	how much	zalando		how	to	mincraft	zara
	is it in aus-				your name	house can i			make
	tralia							afford				money fast
	(0.3038)		(0.6794)		(0.2981)	(0.427)		(0.1193)		(0.7293)		(0.528)		(0.2791)	(0.2318)
	instagram	what is the	facebook	euro 2016		weather		what is the	how old is	cnn	youtube
			tempera-							tempera-		hillary clin-	mp3
			ture							ture		ton
	(0.3059)		(0.7037)		(0.2981)	(0.4532)		(0.1196)		(0.7296)		(0.5438)		(0.2881)	(0.2641)
	traduttore	how many	pandora	who sings	how many	how	to	when	we	how	to	gmail
			weeks in a		this song		people		make		were young	draw	a
			year					are in the	pancakes				doghow to
								world						get rid of
														blackheads

Table 5 :

 5 Per SE, ordered list of 10 queries with the smallest relative score with respect to the consensus (and their relative score).

https://searchengineland.com/google-now-handles-2-999-trillion-searches-per-year-250247

See for example https://www.technologyreview.com/s/610275/meet-the-woman-who-searches-out-search-engines-bias-against-women-and-minorities/

http://gs.statcounter.com/search-engine-market-share