Search

Summary: The WAND processing strategy is a dynamic pruning algorithm designed for large scale Web search engines where fast response to queries is a critical service. The WAND is used to reduce the amount of computation by scoring only documents that may become part of the top‐k document results. In this paper, we present two parallel strategies for the WAND algorithm and compare their performance on GPUs. In our first strategy (named size‐based), the posting lists are evenly partitioned among thread blocks. Our second strategy (named range‐based) partitions the posting lists according to document identifier intervals; thus, partitions may have different sizes. We also propose three threshold sharing policies, named Local, Safe‐R, and Safe‐WR, which emulate the WAND algorithm global pruning technique. We evaluated our proposals with different amounts of work, from short to extra‐large queries, using single query processing and batch of queries. Results show that the size‐based strategy reports the highest speedups but at the cost of low quality of results. The range‐based algorithm retrievals the exact top‐k documents and maintains a good speedup. Moreover, both strategies are capable of scaling as the amount of work is increased. In addition, there is no significant difference in the performance of the three threshold sharing policies. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]