In this article, we tackle the problem of predicting the “next” geographical position of a tourist, given her history (i.e., the prediction is done accordingly to the tourist’s current trail) by means of supervised learning techniques, namely Gradient Boosted Regression Trees and Ranking SVM. The learning is done on the basis of an object space represented by a 68-dimension feature vector specifically designed for tourism-related data. Furthermore, we propose a thorough comparison of several methods that are considered state-of-the-art in recommender and trail prediction systems for tourism, as well as a popularity baseline. Experiments show that the methods we propose consistently outperform the baselines and provide strong evidence of the performance and robustness of our solutions.

In this paper, we tackle the problem of predicting the "next" geographical position of a tourist given her history (i.e., the prediction is done accordingly to the tourist's current trail) by means of supervised learning techniques, namely Gradient Boosted Regression Trees and Ranking SVM. The learning is done on the basis of an object space represented by a 68 dimension feature vector, specifically designed for tourism related data. Furthermore, we propose a thorough comparison of several methods that are considered state-of-the-art in touristic recommender and trail prediction systems as well as a strong popularity baseline. Experiments show that the methods we propose outperform important competitors and baselines thus providing strong evidence of the performance of our solutions.

Over recent years, we experienced a huge diffusion of internet connected computing devices. As a consequence, this leaded to research for efficient and scalable approaches for managing the burden caused by the highly increased volume of data to be exchanged and processed. Efficient communication protocols are fundamental building blocks for realizing such approaches [1], [2]. Thus, several peer-to-peer protocols have been proposed. Gossip protocols [3]-[7] are a family of peer-to-peer protocols that proved to be well-suited for supporting a scalable and decentralized strategy for peer and data aggregation and diffusion. However, one of the typical limitation of Gossip protocols consists in the selfish behavior adopted by peers in defining their neighborhood and, as a consequence, the topology of the overlay they build. GROUP [8] is a Gossip protocol we conceived to overcome this limitation. It builds explicit defined communities of peers that are identified by their leaders, each one elected in a distributed fashion. This protocol experimentally proved to be efficient and effective with respect to its aim. Anyhow, no analytical study has been realized so far. This work presents a currently ongoing work we are conducting for exploring the properties of GROUP in a more formal way. We conduct this preliminary investigation using a formalization based on Markov chains.

P2P overlays based on Delaunay triangulations have been recently exploited to implement systems providing efficient routing and data broadcast solutions. Several applications such as Distributed Virtual Environments and geographical nearest neighbours selection benefit from this approach. This paper presents a novel distributed algorithm for the incremental construction of a Delaunay overlay in a P2P network. The algorithm employs a distributed version of the classical Edge Flipping procedure. Each peer builds the Delaunay links incrementally by exploiting a random peer sample returned by the underlying gossip level. The algorithm is then optimized by considering the Euclidean distance between peers to speed up the overlay convergence. We present theoretical results that prove the correctness of our approach along with a set of experiments that assess the convergence rate of the distributed algorithm.

We introduce K-model, a computational model to evaluate the algorithms designed for graphic processors, and other architectures adhering to the stream programming model. We address the lack of a formal complexity model that properly accounts for memory contention, address coalescing in memory accesses, or the serial control of instruction flows. We study the impact of K-model rules on algorithm design. We devise a coalesced and low contention data access technique for Batcher's networks, and we evaluate the effectiveness of this technique within our K-model. To evaluate the benefits in using K-model in evaluating solutions for streaming architectures, we compare the complexity of a sorting network built using our technique, and quick sort. Although in theory quick sort is more efficient than bitonic sort, empirically, our bitonic sorting network has been shown to be faster than the state-of-the-art implementation of quick sort on graphics processing units (GPUs). We use our K-model to prove that this observation should generally hold. As a side result, our technique to perform a Batcher's network on GPUs improves the performance of one the fastest comparison-based solution for integers sorting.

Given a collection of objects, the Similarity Self-Join problem requires to discover all those pairs of objects whose similarity is above a user defined threshold. In this paper we focus on document collections, which are characterized by a sparseness that allows effective pruning strategies. Our contribution is a new parallel algorithm within the MapReduce framework. This work borrows from the state of the art in serial algorithms for similarity join and MapReduce-based techniques for set-similarity join. The proposed algorithm shows that it is possible to leverage a distributed file system to support communication patterns that do not naturally fit the MapReduce framework. Scalability is achieved by introducing a partitioning strategy able to overcome memory bottlenecks. Experimental evidence on real world data shows that our algorithm outperforms the state of the art by a factor 4.5.

The problem of defining a support for multidimensional range queries on P2P overlays is currently an active field of research. Several approaches based on the extension of the basic functionalities offered by Distributed Hash Tables have been recently proposed. The main drawback of these approaches is that the locality required for the resolution of a range query cannot be guaranteed by uniform hashing. On the other way, locality preserving hashing functions do not guarantee a good level of load balancing. This paper presents Hivory, a P2P overlay based on a Voronoi tessellation defined by the objects published by peers. Each object is mapped to a site of the Voronoi tessellation and the corresponding Delaunay Triangulation defines the P2P overlay. A hierarchy of Voronoi diagrams is defined by exploiting clusters of objects paired with the same site of the Voronoi diagram. A new Voronoi diagram including the peers of the cluster is created so that the query resolution may be refined by a top down visit of the Voronoi hierarchy. The paper presents the proposed solution, analysis its complexity, and provides a set of experimental results.

World Wide Web content continuously grows in size and importance. Furthermore, users ask Web search engines to satisfy increasingly disparate information needs. New techniques and tools are constantly developed aimed at assisting users in the interaction with the Web search engine. Query recommender systems suggesting interesting queries to users are an example of such tools. Most query recommendation techniques are based on the knowledge of the behaviors of past users of the search engine recorded in query logs.

The recommendation of queries, known as query suggestion, is a common practice on major Web Search Engines. It aims to help users to find the information they are looking for, and is usually based on the knowledge learned from past interactions with the search engine. In this paper we propose a new model for query suggestion, the Search Shortcut Problem, that consists in recommending "successful" queries that allowed other users to satisfy, in the past, similar information needs. This new model has several advantages with respect to traditional query suggestion approaches. First, it allows a straightforward evaluation of algorithms from available query log data. Moreover, it simplifies the application of several recommendation techniques from other domains. Particularly, in this work we applied Collaborative Filtering to this problem, and evaluated the interesting results achieved on large query logs from AOL and Microsoft. Different techniques for analyzing and extracting information from query logs, as well as new metrics and techniques for measuring the effectiveness of recommendations are proposed and evaluated. The results obtained clearly show the importance of several of our contributions, and open an interesting field for future research.

Giving suggestions to users of Web-based services is a common practice aimed at enhancing their navigation experience. Major Web Search Engines usually provide "Suggestions" under the form of queries that are, to some extent, related to the current query typed by the user, and the knowledge learned from the past usage of the system. In this work we introduce "Search Shortcuts" as "Successful" queries allowed, in the past, users to satisfy their information needs. Differently from conventional suggestion techniques, our search shortcuts allows to evaluate effectiveness by exploiting a simple train-and-test approach. We have applied several Collaborative Filtering algorithms to this problem, evaluating them on a real query log data. We generate the shortcuts from all user sessions belonging to the testing set, and measure the quality of the shortcuts suggested by considering the similarity between them and the navigational user behavior.

This paper describes the study conducted to design and evaluate a two-level on-line scheduler to dynamically schedule a stream of sequential and multi-threaded batch jobs on large scale grids, made up of interconnected clusters of heterogeneous machines. The scheduler aims to schedule arriving jobs respecting their computational and deadline requirements, and optimizing the utilization of hardware resources as well as software resources.

This paper presents VoRaQue, a software layer supporting range queries on Voronoi P2P overlays. VoRaQue maps data in a 2-dimensional space. The P2P overlay is defined by links connecting nodes that are close in the 2-dimensional space and by a set of long-range links which guarantee a poly-logarithmic routing. When a query is submitted, VoRaQue finds out a node belonging to the region defined by the query. A multicast spanning tree covering that region is then built by applying compass routing, a distributed protocol to embed a spanning tree into a Delaunay Triangulation. The paper presents the basic VoRaQue protocol, then introduces a set of optimizations and finally presents some experimental results.

This paper presents QLSE (QoS-constrained list scheduling heuristics), a quality of service-based launch time scheduling algorithm for wide area grids. QLSE considers applications described by a task interaction graph (TIG) whose nodes and edges are labeled according to the Quality of Service requirements of the application. The high values obtained in the performance evaluation for both the tasks communication and computation throughput demonstrates the applicability of the proposed approach.

In this paper, we propose a new method, called Convergent Scheduling, for scheduling a continuous stream of batch jobs on the machines of large-scale computing farms. This method exploits a set of heuristics that guide the scheduler in making decisions. Each heuristics manages a specific problem constraint, and contributes to carry out a value that measures the degree of matching between a job and a machine. Scheduling choices are taken to meet the QoS requested by the submitted jobs, and optimizing the usage of hardware and software resources. We compared it with some of the most common job scheduling algorithms, i.e. Backfilling, and Earliest Deadline First. Convergent Scheduling is able to compute good assignments, while being a simple and modular algorithm.

In order to minimize the execution time of a parallel application running on a heterogeneously distributed computing system, an appropriate mapping scheme is needed to allocate the application tasks to the processors. The general problem of mapping tasks to machines is a well-known NP-hard problem and several heuristics have been proposed to approximate its optimal solution. In this paper we propose a static graph-based mapping algorithm, called Heterogeneous Multi-phase Mapping (HMM), which permits suboptimal mapping of a parallel application onto a heterogeneous computing distributed system by using a local search technique together with a tabu search meta-heuristic. HMM allocates parallel tasks by exploiting the information embedded in the parallelism forms used to implement an application, and considering an affinity parameter, that identifies which machine in the heterogeneous computing system is most suitable to execute a task. We compare HMM with some leading techniques and with an exhaustive mapping algorithm. We also give an example of mapping of two real applications using HMM. Experimental results show that HMM performs well demonstrating the applicability of our approach. Copyright © 2005 John Wiley & Sons, Ltd.

In this demo we show a recommender system, called SUGGEST , that dynamically generates links to pages that have not yet been visited by a user and might be of his potential interest. Usually other recommender systems exploit a kind of two-phase architecture composed by an off-line component that analyzes Web server access logs and generates information used by a successive online component that generates recommendations. SUGGEST collapse the two-phase into a single online Apache module. The component is able to manage very large Web sites made up of dinamically generated pages by means of an efficient LRU-based database management strategy. The demo will show the way SUGGEST is able to anticipate users’ requests that will be made farther in the future, introducing a limited overhead on the Web server activity.

In this paper we propose a WUM recommender system, called SUGGEST 3.0, that dynamically generates links to pages that have not yet been visited by a user and might be of his potential interest. Differently from the recommender systems proposed so far, SUGGEST 3.0 does not make use of any off-line component, and is able to manage Web sites made up of pages dynamically generated. To this purpose SUGGEST 3.0 incrementally builds and maintains historical information by means of an incremental graph partitioning algorithm, requiring no off-line component. The main innovation proposed here is a novel strategy that can be used to manage large Web sites. Experiments, conducted in order to evaluate SUGGEST 3.0 performance, demonstrated that our system is able to anticipate users' requests that will be made farther in the future, introducing a limited overhead on the Web server activity.

The combination of genetic and local search heuristics has been shown to be an effective approach to solving the traveling salesman problem (TSP). This paper describes a new hybrid algorithm that exploits a compact genetic algorithm in order to generate high-quality tours, which are then refined by means of the Lin-Kernighan (LK) local search. The local optima found by the LK local search are in turn exploited by the evolutionary part of the algorithm in order to improve the quality of its simulated population. The results of several experiments conducted on different TSP instances with up to 13,509 cities show the efficacy of the symbiosis between the two heuristics.

The need to deal with highly complex scientific problems has led some researchers to use geographically distributed computing resources as a single powerful parallel machine. The word metacomputing has been coined to describe this new approach. This paper outlines some experiences in metacomputing carried out on a wide area network. A brief overview is given of the main issues concerning metacomputing, and some experiments in this field are reported. WAMM, the metacomputer visual interface we have developed, is described. Astrophysics is a particularly fruitful field for numerical-intensive computer simulation, because the systems under study, stars and galaxies, are not amenable to controlled laboratory experiments. An astrophysical application of the gravitational n-body problem, developed in conjunction with the Scuola Normale Superiore of Pisa, was used to test WAMM's utility in metacomputer management, and some performance figures related to the case study are given. Work related to WAMM and conclusions are also presented. © 1997 by John Wiley & Sons, Ltd.