Web search engines are complex systems deployed on large clusters of processors. With a constant growing number of users, Web search engines capacity must be frequently evaluated. Among other techniques, capacity planning methods are a good approach to estimate the amount of processors in cluster based systems, allowing data-center engineers to ensure enough computational resources are available to efficiently deal with the ever changing streams of user queries. In this paper, we present a novel capacity planning methodology that combines discrete-event simulation and classical operational analysis for open systems formulae. With this methodology, just a small fraction of deployments are evaluated to find an optimal assignment of resources given a target workload. We experimentally evaluate a simulation-based capacity planning module in combination with an OpenMP+MPI implementation of a Web search engine, that periodically evaluates its performance metrics in order to elastically adjust the amount of computational resources needed to support the current workload. Results show that the proposed methodology is able to quickly provide a new deployment configuration upon performance changes, ensuring that an strictly sufficient amount of computational resources are available to efficiently deal with users demands.

MOTIVATION: Genome repositories are growing faster than our storage capacities, challenging our ability to store, transmit, process and analyze them. While genomes are not very compressible individually, those repositories usually contain myriads of genomes or genome reads of the same species, thereby creating opportunities for orders-of-magnitude compression by exploiting inter-genome similarities. A useful compression system, however, cannot be only usable for archival, but it must allow direct access to the sequences, ideally in transparent form so that applications do not need to be rewritten. RESULTS: We present a highly compressed filesystem that specializes in storing large collections of genomes and reads. The system obtains orders-of-magnitude compression by using Relative Lempel-Ziv, which exploits the high similarities between genomes of the same species. The filesystem transparently stores the files in compressed form, intervening the system calls of the applications without the need to modify them. A client/server variant of the system stores the compressed files in a server, while the client's filesystem transparently retrieves and updates the data from the server. The data between client and server are also transferred in compressed form, which saves an order of magnitude network time. AVAILABILITY AND IMPLEMENTATION: The C++ source code of our implementation is available for download in https://github.com/vsepulve/relz_fs.

Computer models have been used as a bridge between parallel algorithms and hardware architectures. The Bulk-Synchronous Parallel (BSP) is a well-known computing model originally devised for distributed algorithms running on clusters of single-core processors. The Multi-BSP model, that extends the classic BSP model, was recently proposed for multi-core processors. However, this model -implemented through the MulticoreBSP-for-C library- presents some restrictions such as the explicit synchronizations between the cores, introducing some challenges on which the hardware characteristics should be taken into account to properly model the parallel algorithms. Therefore, we explore the suitability of these models for the Dell multi-core architecture. The objectives of this contribution are twofold. First, we model two different multi-core Dell architectures. Second, we show that a simple model with few parameters can be easily adapted to each Dell platform rather than complex models which tends to use tricky hardware parameters.

We studied routing protocols for Delay Tolerant Networks devised to improve the message delivery performance in natural disaster scenarios. In this paper we propose the MinVisited protocol which during the transitive path to the message destination, selects the next node based on two features: (1) the most distant neighbor, and (2) the largest number of encounters with the destination node of the message. We compare our protocol with well-known protocols of the technical literature. The results show that the proposed protocol presents a low workload overhead with a number of hops lower than 2, and in average 95% of the messages are successfully delivered.

Summary Discrete Event System Specification (DEVS) is a formalism for the modeling and analysis of discrete event systems. Parallel DEVS (PDEVS) is an extension of DEVS for supporting Parallel and Discrete Event Simulation, which is a powerful tool for evaluating the performance of large scale systems. In this work, we propose an optimistic approximate and semi‐asynchronous parallel strategy. The level of optimism is efficiently managed throughout the simulation execution, and it is automatically adjusted based on the simulation evolution. Load balance and model partitioning is automatically made by means of an algorithm that takes advantage of the communication pattern of the simulated model. Our proposal is designed for Web search engines, which are complex and highly optimized systems devised to operate on large clusters of processors and dealing with dynamic and unpredictable user query bursts. The results show that our proposal is able to reduce both execution times and memory usage of standard optimistic simulations of Web search engine models, at the expense of small errors.

Big Data is now a widely studied concept in the field of massive processing of information, but testing systems and applications in this field is a difficult task, because the real environments to be used are of a large scale and many times impossible to reproduce. Usually, for this task executions in virtual settings, called simulations, are used. The present article presents a simulator for applications developed to be executed on the Apache S4 distributed computing platform for multiple hardware and software scenarios. A version in which mobile devices as well as processing units are used is proposed. The results show that the simulator without mobile devices gets good prediction performance results considering the processing and communication times between the elements of the S4 applications, and the other version with mobile systems shows a decrease in performance in different simulation configurations. However, adding replication in the elements that are communicated with the cellphones has shown substantial improvements in the application's performance.

Summary Data abundance poses the need for powerful and easy‐to‐use tools that support processing large amounts of data. MapReduce has been increasingly adopted for over a decade by many companies, and more recently, it has attracted the attention of an increasing number of researchers in several areas. One main advantage is that the complex details of parallel processing, such as complex network programming, task scheduling, data placement, and fault tolerance, are hidden in a conceptually simple framework. MapReduce is supported by mature software technologies for deployment in data centers such as Hadoop. As MapReduce becomes popular for high‐performance applications, many questions arise concerning its performance and efficiency. In this paper, we demonstrated formally lower bounds on the isoefficiency function for MapReduce applications, when these applications can be modeled as BSP jobs. We also demonstrate how communication and synchronization costs can be dominant for MapReduce computations and discuss the conditions under which such scalability limits are valid. To our knowledge, this is the first study that demonstrates scalability bounds for MapReduce applications. We also discuss how some MapReduce implementations such as Hadoop can mitigate such costs to approach linear, or near‐to‐linear speedups. Copyright © 2015 John Wiley & Sons, Ltd.

DEVS is a formalism for modeling and analysis of discrete event systems. PDEVS is an extension of DEVS for supporting Parallel and Discrete Event Simulation (PDES). PCD++ is a simulation platform that supports parallel simulations of DEVS models, where the model component allocation in processors is not an automatic process. This can be a time consuming task requiring knowledge of communication patterns among model components. In this paper, we propose and evaluate different allocation strategies devised to improve load balance of parallel DEVS simulations. The experimentation is made on a Web search engine application whose workload is featured by dynamic and unpredictable user query bursts, and high message traffic among processors.

This paper proposes using Coloured Petri Nets to model performance of vertical search engines for Web search. In such systems, queries submitted by users or client systems are handled by different components implemented as services deployed on large clusters of dedicated processors. We propose models that represent key features of components running time cost at a suitable level of detail. A comprehensive evaluation study is presented to reveal good precision of models when compared against actual implementations and complex process-oriented simulators of the same search engine instances. A C++ class library is proposed to enable rapid model construction by using a hierarchical and scalable approach, and to enable transparent generation and efficient execution of respective simulation programs either sequentially or in parallel.

Large scale Web search engines are complex and highly optimized systems devised to operate on dedicated clusters of processors. Any, even a small, gain in performance is beneficial to economical operation given the large amount of hardware resources deployed in the respective data centers. Performance is fully dependent on users behavior which is featured by unpredictable and drastic variations in trending topics and arrival rate intensity. In this context, discrete-event simulation is a powerful tool either to predict performance of new optimizations introduced in search engine components or to evaluate different scenarios under which alternative component configurations are able to process demanding workloads. These simulators must be fast, memory efficient and parallel to cope with the execution of millions of events in small running time on few processors. In this paper we propose achieving this objective at the expense of performing approximate parallel simulation.

Focused crawlers are programs designed to download web pages which are relevant to specific topics. Using information gathered at running time, focused crawlers explore the web following promissory hyperlinks and fetching only pages which appear to be relevant. These crawlers are receiving increasing attention because they favor the construction of vertical search engines, allowing users to focus on specific topics of information, providing higher accuracy and reducing computational costs involved in query processing. In this article, we introduce an efficient focused crawling strategy which considers a number of distributed focused crawlers which recover relevant pages to a given knowledge domain. We propose an ontology-based knowledge representation approach to drive the crawler to specific segments of the web. Experimental results with actual samples of the Web show the feasibility and efficiency of our strategy.

Web search engines are systems devised to cope with highly dynamic and demanding query rates. These systems are composed by several services, each one dedicated to execute a single operation required to solve a query. Services are allocated into thousand of multi-core processors organized in racks. Some services communicate more than others, so it is desirable to put them in the same rack. In this work, we present and evaluate deployment algorithms for a web search engine. In particular, we focus on vertical search engines with specific on-line content which may include shopping, advertisement, etc.. Our goal is to improve the performance of a search engine by reducing communication time. Communication among services is performed by means of a fast and complex network supporting parallel sending and receiving of messages. We propose a communication-graph-based method, in which processors are the nodes of the graph and communication between them is represented as weighted arcs. Results show that our proposal method is able to reduce maximum query response time.

Metric-space similarity search has been proven suitable for searching large collections of complex objects such as images. A number of distributed index data structures and respective parallel query processing algorithms have been proposed for clusters of distributed memory processors. Previous work has shown that best performance is achieved when using global indexing as opposed to local indexing. However global indexing is prone to performance degradation when query load becomes unbalanced across processors. This paper proposes a query scheduling algorithm that solves this problem. It adaptively load balances processing of user queries that are dynamically skewed towards particular sections of the distributed index. Sections highly hit by queries can be kept replicated. Experimental results show that with 1%-10% replication performance improves significantly (e.g., 35%) under skewed work-loads.

This paper proposes a two-level caching strategy for Web search queries which is devised to operate on P2P networks. The aim is to significantly reduce query traffic going from a large community of users to commercial search engines by placing between them a P2P caching service capable of storing and efficiently distributing frequent queries among users. The proposed design takes into consideration the highly dynamic nature of user queries both in traffic intensity and drastic shifts in user interest which are both usually driven by unpredictable world-wide events. Each peer maintains a LRU result cache (RCache) used to keep the answers for queries originated in the peer itself and queries for which the peer is responsible for by contacting on-demand a Web search engine to get the query answers. When query traffic is predominantly routed to a few responsible peers our strategy replicates the role of ``being responsible for" to neighboring peers so that they can absorb part of the traffic to restore load balance. This is a fairly slow and adaptive process that we call mid-term load balancing. To achieve a short-term fair distribution of queries we introduce in each peer a location cache (LCache) which keeps pointers to peers that have already requested the same queries in the very recent past. This lets these peers share their query answers with newly requesting peers. This process is fast as these popular queries are usually cached in the first DHT hop of a requesting peer which quickly tends to redistribute load among more and more peers. A comparative study shows that the proposed strategy achieves better load balance, significantly smaller communication volume among peers, and larger cache hit ratios than previous strategies.

Similarity search has been widely studied in the last years, as it can be applied to several fields such as searching by content in multimedia objects, text retrieval or computational biology. These applications usually work on very large databases that are often indexed off-line to enable the acceleration of on-line searches. However, to maintain an acceptable throughput, it is essential to exploit the intrinsic parallelism of the algorithms used for the on-line query solving process, even with indexed databases. Therefore, many strategies have been proposed in the literature to parallelize these algorithms, both on shared and distributed memory multiprocessor systems. Lately, GPUs have also been used to implement brute-force approaches instead of using indexing structures, due to the difficulties introduced by the index in the efficient exploitation of the GPU resources. In this work we propose a Multi-GPU metric-space technique that efficiently exploits index data structures for similarity search in large databases, and show how it outperforms previous OpenMP and GPU brute-force strategies. Furthermore, our analysis covers the effects of the database size and its nature.

Large Web search engines are constructed as a collection of services that are deployed on dedicated clusters of distributed-memory processors. In particular, efficient user query throughput heavily relies on using result cache services devoted to maintaining the answers to most frequent queries. Load balancing and fault tolerance are critical to this service. This paper proposes the design of a result cache service based on consistent hashing and a strategy for enabling fault tolerance. Performance evaluation is performed by using actual queries from a commercial search engine. The results show that the proposed cache service outperforms baseline approaches, decreases the average query response time, increases query throughput and efficiently recovers performance after processor failures.

Positional ranking functions, widely used in Web search engines, improve result quality by exploiting the positions of the query terms within documents. However, it is well known that positional indexes demand large amounts of extra space, typically about three times the space of a basic nonpositional index. Textual data, on the other hand, is needed to produce text snippets. In this paper, we study time-space trade-offs for search engines with positional ranking functions and text snippet generation. We consider both index-based and non-index based alternatives for positional data. We aim to answer the question of whether one should index positional data or not. We show that there is a wide range of practical time-space trade-offs. Moreover, we show that both position and textual data can be stored using about 71% of the space used by traditional positional indexes, with a minor increase in query time. This yields considerable space savings and outperforms, both in space and time, recent alternatives from the literature. We also propose several efficient compressed text representations for snippet generation, which are able to use about half of the space of current state-of-the-art alternatives with little impact in query processing time.

Search nodes are single-purpose components of large Web search engines and their efficient implementation is critical to sustain thousands of queries per second and guarantee individual query response times within a fraction of a second. Current technology trends indicate that search nodes ought to be implemented as multi-threaded multi-core systems. The straightforward solution that system designers can apply in this case is simply to follow standard practice by deploying one asynchronous thread per active query in the node and attaching each thread to a different core. Each concurrent thread is responsible for sequentially processing a single query at a time. The only potential source of read/write conflicts among threads are the accesses to the different application caches present in the search node. However, new Web applications pose much more demanding requirements in terms of read/write conflicts than recent past applications since now data updates must take place concurrently with query processing. Insisting on the same paradigm of concurrent threads now augmented with a transaction concurrency control protocol is a feasible solution. In this paper we propose a more efficient and much simpler solution which has the additional advantage of enabling a very efficient administration of application caches. We propose performing relaxed bulk-synchronous parallelism at multi-core level.

This paper proposes a cache hierarchy that enables Web search engines to efficiently process user queries. The different caches in the hierarchy are used to store pieces of data which are useful to solve frequent queries. Cached items range from specific data such as query answers to generic data such as segments of index retrieved from secondary memory. The paper also presents a comparative study based on discrete-event simulation and bulk-synchronous parallelism. The studied performance metrics include overall query throughput, single-user query latency and power consumption. In all cases, the results show that the proposed cache hierarchy leads to better performance than a baseline approach built on state of the art caching techniques.

This paper studies the problem of distributing a metric-space search index based on compact clustering onto a set of distributed memory processors. The aim is enabling efficient similarity search in large-scale Web search engines. The index data structure is composed of a set of clusters enclosing the database objects and we propose distribution methods based on two different solution approaches. The first one makes use of specific knowledge about the work-load generated by user queries. Here the challenge is how to represent and use such a knowledge into a method capable of producing a cluster distribution leading to high performance. The second one follows a novel direction by completely disregarding user behavior to look instead at the relationships among the index clusters themselves to decide their placement onto processors. Both methods perform efficiently depending on the context and they are generic enough to be applied to different distributed index data structures for metric-space databases.

This paper proposes a strategy to organize metric-space query processing in multi-core search nodes as understood in the context of search engines running on clusters of computers. The strategy is applied in each search node to process all active queries visiting the node as part of their solution which, in general, for each query is computed from the contribution of each search node. When query traffic is high enough, the proposed strategy assigns one thread to each query and lets them work in a fully asynchronous manner. When query traffic is moderate or low, some threads start to idle so they are put to work on queries being processed by other threads. The strategy solves the associated synchronization problem among threads by switching query processing into a bulk-synchronous mode of operation. This simplifies the dynamic re-organization of threads and overheads are very small with the advantage that the overall work-load is evenly distributed across all threads.

This paper proposes a strategy to reduce the amount of hardware involved in the solution of search engine queries. It proposes using a secondary compact cache that keeps minimal information stored in the query receptionist machine to register the processors that must get involved in the solution of queries which are evicted from the standard result cache or are not admitted in it. This cache strategy produces exact answers by using very few processors.

Searching for similar objects in metric-space databases can be efficiently solved by using index data structures. A number of alternative sequential indexes have been proposed in the literature. This paper proposes the parallelization of a recent pivot-based index data structure which can efficiently accommodate on-line updates and reduces the number of object-to-object comparisons during searches. We present algorithms for index construction and query processing.

Search engines use inverted files as index data structures to speed up the solution of user queries. The index is distributed on a set of processors forming a cluster of computers and queries are received by a broker machine and scheduled for solution in the cluster. The broker must use a scheduling algorithm to assign queries to processors since the computations associated with the ranking of documents that form part of the solutions to queries can take a significant fraction of the total running time. The cost of this task can be highly variable and depends on the particular user preferences for words when formulating queries in a given period of time. Thus the scheduling algorithm must be able to cope efficiently with a highly dynamic and very large amount of jobs being assigned in an on-line manner to the processors. In this paper we evaluate a number of scheduling algorithms proposed in the literature in the context of scheduling queries on a search engine.

This paper describes the design of a crawler devised to perform the periodic retrieval of Web documents for a search engine able to accept on-line updates in a concurrent manner. On-line updates comes in the form of insertions of new documents or update of existing ones, all of them mixed with the usual user queries. The search engine is bulk-synchronous which allows it to deal efficiently with the concurrency control problem. The crawler is also bulk- synchronous so that it can be integrated into the same P- processors cluster executing the search engine. This paper describes and evaluates the practical feasibility of such a crawler.

We present a general method of parallel query processing that allows scalable performance on distributed inverted files. The method allows the realization of a hybrid that combines the advantages of the document and term partitioned inverted files.