Traffic congestion is a phenomenon with which most drivers are familiar. It negatively affects drivers, city's residents and also the economic efficiency. Road pavement condition is one of the main causes of traffic congestion. Warning drivers of road pavement conditions is an effective and highly recommended solution to prevent a traffic jam before it actually occurs. Through this paper, we present a new strategy to reduce traffic congestion. We propose an unsupervised anomaly detection framework that predicts road obstacles. We suggest a well-motivated combination between the Long Short Term Memory (LSTM) and Local outlier value factor (LOF) techniques for predicting obstacles in time series. This combination can potentially offer very promising results in terms of prediction accuracy. We illustrate significant performance gains achieved by our technique with respect to the conventional methods.

Meeting user demand is one of the most challenging problems arising in public bicycle sharing systems. Various factors, such as daily commuting patterns or topographical conditions, can lead to an unbalanced state where the numbers of rented and returned bicycles differ significantly among the stations. This can cause spatial imbalance of the bicycle inventory which becomes critical when stations run completely empty or full, and thus prevent users from renting or returning bicycles. To prevent such service disruptions, we propose to forecast user demand in terms of expected number of bicycle rentals and returns and accordingly to estimate number of bicycles that need to be manually redistributed among the stations by maintenance vehicles. As opposed to traditional solutions to this problem, which rely on short-term demand forecasts, we aim to maximise the time within which the stations remain balanced by forecasting user demand multiple steps ahead of time. We propose a multi-input multi-output deep learning model based on Long Short-Term Memory networks to forecast user demand over long future horizons. Conducted experimental study over real-world dataset confirms the efficiency and accuracy of our approach.

Selecting the most interesting tourist attractions and planning optimal sightseeing tours can be a difficult task for individuals visiting unfamiliar tourist destinations. On the other hand, the massive amounts of tourists in big cities can collapse certain areas causing transport inefficiency, unbalanced economic growth and nuisance among tourists and citizens. Therefore, the tourist trip planning problem should take into account the possibility for the city government to manage the urban environment and achieve a balanced and sustainable growth. In this paper we introduce the tourist trip planning problem which covers both individual (tourist) and global (city) needs. The planning problem is modelled as an extension of the mixed orienteering problem and can be controlled by deployment of mobility policies which put restrictions on points of interest and routes between them. We propose an algorithmic approach and a software tool to solve this hard combinatorial optimisation problem using variable neighbourhood search. The performance of the proposed algorithm and the tool is assessed over a real-life dataset related to the city of Barcelona. Computational results confirm the efficiency of the algorithm and ability to help both individuals in planning their trips and city governments in achieving sustainable mobility objectives.

Among different components of urban mobility, urban freight transport is usually considered as the least sustainable. Limited traffic infrastructures and increasing demands in dense urban regions lead to frequent delivery runs with smaller freight vehicles. This increases the traffic in urban areas and has negative impacts upon the quality of life in urban populations. Data driven optimizations are essential to better utilize existing urban transport infrastructures and to reduce the negative effects of freight deliveries for the cities. However, there is limited work and data driven research on urban delivery areas and freight transportation networks. In this paper, we collect and analyse data on urban freight deliveries and parking areas towards an optimized urban freight transportation system. Using a new check-in based mobile parking system for freight vehicles, we aim to understand and optimize freight distribution processes. We explore the relationship between areas' availability patterns and underlying traffic behaviour in order to understand the trends in urban freight transport. By applying the detected patterns we predict the availabilities of loading/unloading areas, and thus open up new possibilities for delivery route planning and better managing of freight transport infrastructures.

Community detection has arisen as one of the most relevant topics in the field of graph data mining due to its applications in many fields such as biology, social networks, or network traffic analysis. Although the existing metrics used to quantify the quality of a community work well in general, under some circumstances, they fail at correctly capturing such notion. The main reason is that these metrics consider the internal community edges as a set, but ignore how these actually connect the vertices of the community. We propose the Weighted Community Clustering ( WCC ), which is a new community metric that takes the triangle instead of the edge as the minimal structural motif indicating the presence of a strong relation in a graph. We theoretically analyse WCC in depth and formally prove, by means of a set of properties, that the maximization of WCC guarantees communities with cohesion and structure. In addition, we propose Scalable Community Detection (SCD) , a community detection algorithm based on WCC , which is designed to be fast and scalable on SMP machines, showing experimentally that WCC correctly captures the concept of community in social networks using real datasets. Finally, using ground-truth data, we show that SCD provides better quality than the best disjoint community detection algorithms of the state of the art while performing faster.

The Linked Data Benchmark Council (LDBC) is now two years underway and has gathered strong industrial participation for its mission to establish benchmarks, and benchmarking practices for evaluating graph data management systems. The LDBC introduced a new choke-point driven methodology for developing benchmark workloads, which combines user input with input from expert systems architects, which we outline. This paper describes the LDBC Social Network Benchmark (SNB), and presents database benchmarking innovation in terms of graph query functionality tested, correlated graph generation techniques, as well as a scalable benchmark driver on a workload with complex graph dependencies. SNB has three query workloads under development: Interactive, Business Intelligence, and Graph Algorithms. We describe the SNB Interactive Workload in detail and illustrate the workload with some early results, as well as the goals for the two other workloads.

Annotation-based techniques for image retrieval suffer from sparse and short image textual descriptions. Moreover, users are often not able to describe their needs with the most appropriate keywords. This situation is a breeding ground for a vocabulary mismatch problem resulting in poor results in terms of retrieval precision. In this paper, we propose a query expansion technique for queries expressed as keywords and short natural language descriptions. We present a new massive query expansion strategy that enriches queries using a graph knowledge base by identifying the query concepts, and adding relevant synonyms and semantically related terms. We propose a topological graph enrichment technique that analyzes the network of relations among the concepts, and suggests semantically related terms by path and community detection analysis of the knowledge graph. We perform our expansions by using two versions of Wikipedia as knowledge base achieving improvements of the system's precision up to more than 27%.

Community detection has arisen as one of the most relevant topics in the field of graph mining, principally for its applications in domains such as social or biological networks analysis. Different community detection algorithms have been proposed during the last decade, approaching the problem from different perspectives. However, existing algorithms are, in general, based on complex and expensive computations, making them unsuitable for large graphs with millions of vertices and edges such as those usually found in the real world.

Community detection has arisen as one of the most relevant topics in the field of graph data mining due to its importance in many fields such as biology, social networks or network traffic analysis. The metrics proposed to shape communities are too lax and do not consider the internal layout of the edges in the community, which lead to undesirable results. We define a new community metric called WCC. The proposed metric meets a minimum set of basic properties that guarantees communities with structure and cohesion. We experimentally show that WCC correctly quantifies the quality of communities and community partitions using real and synthetic datasets, and compare some of the most used community detection algorithms in the state of the art.

The increasing amount of graph like data from social networks, science and the web has grown an interest in analyzing the relationships between different entities. New specialized solutions in the form of graph databases, which are generic and able to adapt to any schema as an alternative to RDBMS, have appeared to manage attributed multigraphs efficiently. In this paper, we describe the internals of DEX graph database, which is based on a representation of the graph and its attributes as maps and bitmap structures that can be loaded and unloaded efficiently from memory. We also present the internal operations used in DEX to manipulate these structures. We show that by using these structures, DEX scales to graphs with billions of vertices and edges with very limited memory requirements. Finally, we compare our graph-oriented approach to other approaches showing that our system is better suited for out-of-core typical graph-like operations.

We propose and analyze a distributed cooperative caching strategy based on the Evolutive Summary Counters (ESC), a new data structure that stores an approximated record of the data accesses in each computing node of a search engine. The ESC capture the frequency of accesses to the elements of a data collection, and the evolution of the access patterns for each node in a network of computers. The ESC can be efficiently summarized into what we call ESC-summaries to obtain approximate statistics of the document entries accessed by each computing node. We use the ESC-summaries to introduce two algorithms that manage our distributed caching strategy, one for the distribution of the cache contents, ESC-placement, and another one for the search of documents in the distributed cache, ESC-search. While the former improves the hit rate of the system and keeps a large ratio of data accesses local, the latter reduces the network traffic by restricting the number of nodes queried to find a document. We show that our cooperative caching approach outperforms state-of-the-art models in both hit rate, throughput, and location recall for multiple scenarios, i.e., different query distributions and systems with varying degrees of complexity.

The performance of external sorting using merge sort is highly dependent on the length of the runs generated. One of the most commonly used run generation strategies is Replacement Selection (RS) because, on average, it generates runs that are twice the size of the memory available. However, the length of the runs generated by RS is downsized for data with certain characteristics, like inputs sorted inversely with respect to the desired output order. The goal of this paper is to propose and analyze two-way replacement selection (2WRS), which is a generalization of RS obtained by implementing two heaps instead of the single heap implemented by RS. The appropriate management of these two heaps allows generating runs larger than the memory available in a stable way, i.e. independent from the characteristics of the datasets. Depending on the changing characteristics of the input dataset, 2WRS assigns a new data record to one or the other heap, and grows or shrinks each heap, accommodating to the growing or decreasing tendency of the dataset. On average, 2WRS creates runs of at least the length generated by RS, and longer for datasets that combine increasing and decreasing data subsets. We tested both algorithms on large datasets with different characteristics and 2WRS achieves speedups at least similar to RS, and over 2.5 when RS fails to generate large runs.

In this paper we study the performance of a distributed search engine from a data caching point of view. We compare and combine two different approaches to achieve better hit rates: (a) send the queries to the node which currently has the related data in its local memory (cache-aware load balancing), and (b) send the cached contents to the node where a query is being currently processed (cooperative caching). Furthermore, we study the best scheduling points in the query computation in which they can be reassigned to another node, and how this reassignation should be performed. Our analysis is guided by statistical tools on a real question answering system for several query distributions, which are typically found in query logs.

The need for high performance and throughput Question Answering (QA) systems demands for their migration to distributed environments. However, even in such cases it is necessary to provide the distributed system with cooperative caches and load balancing facilities in order to achieve the desired goals. Until now, the literature on QA has not considered such a complex system as a whole. Currently, the load balancer regulates the assignment of tasks based only on the CPU and I/O loads without considering the status of the system cache.

In this demonstration we show the Bibliographic Exploration tool BIBEX. BIBEX is based on the graph database query engine DEX and integrates both the Citeseer and DBLP databases. BIBEX can be found in our web site at www.dama.upc.edu/bibex.

Link and graph analysis tools are important devices to boost the richness of information retrieval systems. Internet and the existing social networking portals are just a couple of situations where the use of these tools would be beneficial and enriching for the users and the analysts. However, the need for integrating different data sources and, even more important, the need for high performance generic tools, is at odds with the continuously growing size and number of data repositories.

Record Linkage (RL) is an important component of data cleansing and integration. For years, many efforts have focused on improving the performance of the RL process, either by reducing the number of record comparisons or by reducing the number of attribute comparisons, which reduces the computational time, but very often decreases the quality of the results. However, the real bottleneck of RL is the post-process, where the results have to be reviewed by experts that decide which pairs or groups of records are real links and which are false hits. In this paper, we show that exploiting the relationships (e.g. foreign key) established between one or more data sources, makes it possible to find a new sort of semantic blocking method that improves the number of hits and reduces the amount of review effort.

The use of evolutionary algorithms has been proposed as a powerful random search strategy to solve the join order problem. Specifically, genetic programming used in query optimization has been proposed as an alternative to the limitations of dynamic programming with large join queries. However, very little is known about the impact and behavior of the genetic operations used in this type of algorithms. In this paper, we present an analysis that helps us to understand the effect of these operations during the optimization execution. Specifically, we study five different aspects: the age of the members in the population in terms of generations, the number of query execution plans (QEP) discarded without producing new offsprings, the average QEP life time in generations, the efficiency of the genetic operations and the evolution of the best cost. All in all, our analysis allows us to understand the impact of crossovers compared to mutation operations and the dynamically changing effects of these operations.

The use of clusters of symmetric multiprocessor (SMP) configurations in database processing has become a key factor in allowing greater scalability. It has also posed many challenges in the implementation of one of the most costly operations within relational algebra: the join operation. When massive data is involved, usually the join cannot be performed in-memory and is processed out of core. In this case, performance depends on an effective use of the memory hierarchy, such that I/O and memory contention are minimized. In this paper, we propose a parallel algorithm for out of core join processing that dynamically adapts its behavior to the resources available in the system. We evaluate and compare our proposal against other parallel approaches in a real SMP cluster in a major commercial database, the IBM/spl reg/ DB2P Universal Database7 product (DB2 UDB). Results show that our proposal outperforms previous work significantly.

We explore the use of compiler optimizations, which optimize the layout of instructions in memory. The target is to enable the code to make better use of the underlying hardware resources regardless of the specific details of the processor/architecture in order to increase fetch performance. The Software Trace Cache (STC) is a code layout algorithm with a broader target than previous layout optimizations. We target not only an improvement in the instruction cache hit rate, but also an increase in the effective fetch width of the fetch engine. The STC algorithm organizes basic blocks into chains trying to make sequentially executed basic blocks reside in consecutive memory positions, then maps the basic block chains in memory to minimize conflict misses in the important sections of the program. We evaluate and analyze in detail the impact of the STC, and code layout optimizations in general, on the three main aspects of fetch performance; the instruction cache hit rate, the effective fetch width, and the branch prediction accuracy. Our results show that layout optimized, codes have some special characteristics that make them more amenable for high-performance instruction fetch. They have a very high rate of not-taken branches and execute long chains of sequential instructions; also, they make very effective use of instruction cache lines, mapping only useful instructions which will execute close in time, increasing both spatial and temporal locality.

In this paper, we look into the characteristics of the reference stream of TPC-C workloads from the buffer pool point of view. We analyze a trace coming from DB2 UDB version 8.1 fix pack 4 and compare it to a trace from DB2 UDB version 8.1 GA. We perform three types of analysis. A static analysis of the number of reads and writes for index and data pages. We conclude that index pages receive less references than data pages by are more frequently accessed individually. Then, we analyze how DB2 processes access those pages. Index pages have more references than data pages when accessed by more than one process. Finally, we understand the accesses along the life of a page. We conclude that there is a significant burstiness in the reference stream, where, each burst is caused by one process.

Fetch engine performance is a key topic in superscalar processors, since it limits the instruction-level parallelism that can be exploited by the execution core. In the search of high performance, the fetch engine has evolved toward more efficient designs, but its complexity has also increased.In this paper, we present the stream fetch engine, a novel architecture based on the execution of long streams of sequential instructions, taking maximum advantage of code layout optimizations. We describe our design in detail, showing that it achieves high fetch performance, while requiring less complexity than other state-of-the-art fetch architectures.

Fetch performance is a very important factor because it effectively limits the overall processor performance. However there is little performance advantage in increasing front-end performance beyond what the back-end can consume. For each processor design, the target is to build the best possible fetch engine for the required performance level. A fetch engine will be better if it provides better performance, but also if it takes fewer resources, requires less chip area, or consumes less power. In this paper we propose a novel fetch architecture based on the execution of long streams of sequential instructions, taking maximum advantage of code layout optimizations. We describe our architecture in detail, and show that it requires less complexity and resources than other high performance fetch architectures like the trace cache, while providing a high fetch performance suitable for wide-issue superscalar processors. Our results show that using our fetch architecture and code layout optimizations obtains 10% higher performance than the EV8 fetch architecture, and 4% higher than the FTB architecture using state-of-the-art branch predictors, while being only 1.5% slower than the trace cache. Even in the absence of code layout optimizations, fetching instruction streams is still 10% faster than the EV8, and only 4% slower than the trace cache. Fetching instruction streams effectively exploits the special characteristics of layout optimized codes to provide a high fetch performance, close to that of a trace cache, but has a much lower cost and complexity, similar to that of a basic block architecture.

Parallel in-memory 64-bit sorting is an important problem in Database Management Systems and other applications such as Internet Search Engines and Data Mining Tools.

Commercial applications such as databases and Web servers constitute the most important market segment for high-performance servers. Among these applications, on-line transaction processing (OLTP) workloads provide a challenging set of requirements for system designs since they often exhibit inefficient executions dominated by a large memory stall component. This behavior arises from large instruction and data footprints and high communication miss rates. A number of recent studies have characterized the behavior of commercial workloads and proposed architectural features to improve their performance. However, there has been little research on the impact of software and compiler-level optimizations for improving the behavior of such workloads.

The design of higher performance processors has been following two major trends: increasing the pipeline depth to allow faster clock rates, and widening the pipeline to allow parallel execution of more instructions. Designing a higher performance processor implies balancing all the pipeline stages to ensure that overall performance is not dominated by any of them. This means that a faster execution engine also requires a faster fetch engine, to ensure that it is possible to read and decode enough instructions to keep the pipeline full and the functional units busy. This paper explores the challenges faced by the instruction fetch stage for a variety of processor designs, from early pipelined processors, to the more aggressive wide issue superscalars. We describe the different fetch engines proposed in the literature, the performance issues involved, and some of the proposed improvements. We also show how compiler techniques that optimize the layout of the code in memory can be used to improve the fetch performance of the different engines described Overall, we show how instruction fetch has evolved from fetching one instruction every few cycles, to fetching one instruction per cycle, to fetching a full basic block per cycle, to several basic blocks per cycle: the evolution of the mechanism surrounding the instruction cache, and the different compiler optimizations used to better employ these mechanisms.

The objective of this paper is to improve the use of the hardware resources of the trace cache mechanism, reducing the implementation cost with no performance degradation. We achieve that by eliminating the replication of traces between the instruction cache and the trace cache. As we show, the trace cache mechanism is generating a high degree of redundancy between the traces stored in the trace cache and those built by the compiler, already present in the instruction cache. Furthermore, code reordering techniques like the software trace cache arrange the basic blocks in a program so that the fall-through path is the most common, effectively increasing this trace redundancy. We propose selective trace storage to avoid trace redundancy between the trace cache and the instruction cache. A simple modification of the fill unit allows the trace cache to store only those traces containing taken branches, which can nor be obtained in a single cycle from the instruction cache. Our results show that selective trace storage and the software trace cache used on a 32 entry trace cache (2 KB) perform as well as a 2048 entry trace cache (128 KB) without the enhancements. This shows that the cooperation between hardware and software is crucial to improve the performance and reduce the requirements of hardware mechanisms in the fetch engine.

While database workloads consume a major fraction of the cycles in today's machines, there are only a few public-domain performance studies that characterize in detail how these workloads exercise the machines. This fact is due to the complexity of setting up and tuning database workloads, the high cost of the equipment required to evaluate them, and the frequent use of proprietary systems. In this paper, we help redress this problem by presenting a detailed performance characterization of the TPC-D benchmark running on a 4-processor Pentium Pro SMP multiprocessor with Windows NT and Microsoft's SQL Server. We use the Pentium Pro built-in hardware event counters and software tools that monitor system activity. Our results show that TPC-D queries have a relatively low CPI. The CPIs, which are 1.27 on average for the 17 read-only queries, are comparable to values observed for technical workloads. The major sources of processor stall cycles are the instruction fetch bottleneck and data misses in the secondary cache. Kernel time is negligible, as queries spend less than 6% of their time on average in the kernel. Other results show that branch prediction is effective in TPC-D and that the exclusive state in the cache tags is largely unnecessary. Finally, we compare our results to the ones published for TPC-C.

Instruction fetch bandwidth is feared to be a major limiting factor to the performance of future wide-issue aggressive superscalars. In this paper, we focus on database applications running decision support workloads. We characterize the locality patterns of ia database kernel and find frequently executed paths. Using this information, we propose an algorithm to lay out the basic blocks for improved I-fetch. Our results show a miss reduction of 60-98% for realistic I-cache sizes and a doubling of the number of instructions executed between taken branches. As a consequence, we increase the fetch bandwith provided by an aggressive sequential fetch unit from 5.8 for the original code to 10.6 using our proposed layout. Our software scheme combines well with hardware schemes like a trace cache providing up to 12.1 instruction per cycle, suggesting that commercial workloads may be amenable to the aggressive I-fetch of future superscalars.

The exploitation of data locality in parallel computers is paramount to reduce the memory traffic and communication among processing nodes. We focus on the exploitation of locality by Parallel Radix sort. The original Parallel Radix sort has several communication steps in which one sorting key may have to visit several processing nodes. In response to this, we propose a reorganization of Radix sort that leads to a highly local version of the algorithm at a very low cost. As a key feature, our algorithm performs one only communication step, forcing keys to move at most once between processing nodes. Also, our algorithm reduces the amount of data communicated. Finally, the new algorithm achieves a good load balance which makes it insensitive to skewed data distributions. We call the new version of Parallel Radix sort that combines locality and load balance, Communication and Cache Conscious Radix sort (C 3 -Radix sort). Our results on 16 processors of the SGI O2000 show that C 3 -R...

In this paper we address the important problem of instruction fetch for future wide issue superscalar processors.Our approach focuses on understanding the interaction between software and hardware techniques targeting an increase in the instruction fetch bandwidth.That is the objective, for instance, of the Hardware Trace Cache (HTC).We design a profile based code reordering technique which targets a maximization of the sequentiality of instructions, while still trying to minimize instruction cache misses.We call our software approach, Software Xrace Cache {STC).We evaluate our software approach, and then compare it with the HTC and the combination of both techniques.Our results show that for large codes with few loops and deterministic execution sequences like databases and some SPEC-INT codes, the STC offers similar, or better, results than a HTC.Moreover, when combining the software and hardware approaches, we obtain encouraging results: the STC and a small HTC offer similar performance to a much larger HTC alone.1 Introduction Instruction fetch bandwidth may become a major limiting factor for future aggressive wide-issue superscalars.Consequently, it is crucial to develop software and hardware techniques that interact to deliver multiple basic blocks to the processor every cycle.Unfortunately, for many important codes, this is hard to do.For instance, database codes and several integer SPEC *This research has been SuDDOrted bv CICYT erant TIC-0511-98 (UPC authors), the Generaiitat de Catalunyagrants ACI 97-26 (Josep L. Larriba-Pey and Josep Torrellas) and 1998FI-00306-APTIND (Alex Ramiree), the Commission for Cultural, Educational and Scientific Exchange'between the United States of .America and Spain

Although cache-coherent shared-memory multiprocessors are often used to run commercial workloads, little work has been done to characterize how well these machines support such workloads. In particular, we do not have much insight into the demands of commercial workloads on the memory subsystem of these machines. In this paper, we analyze in detail the memory access patterns of several queries that are representative of Decision Support System (DSS) databases. Our analysis shows that the memory use of queries differs largely depending on how the queries access the database data, namely via indices or by sequentially scanning the records. The former queries, which we call Index queries, suffer most of their shared-data misses on indices and on lock-related metadata structures. The latter queries, which we call Sequential queries, suffer most of their shared-data misses on the database records as they are scanned. An analysis of the data locality in the queries shows that both Index and Sequential queries exhibit spatial locality and, therefore, can benefit from relatively long cache lines. Interestingly, shared data is reused very little inside queries. However, there is data reuse across Sequential queries. Finally, we show that the performance of Sequential queries can be improved moderately with data prefetching.

In this paper we analyze the use of Blocklng (tiling), Data Precopying and Software Pipelining to improve the performance of sparse matrix computations on superscalar workstations.In particular, we analyze the case of the Sparse Matrix by dense Matrix operation.The analysis focusses on the practical aspects that can be observed when programming such problem on present workstations with several memory levels.The problem is studied on the Alpha 21064 based workstation DEC 3000/800.Simulations of the memory hierarchyare also used to understand the behaviour of the algorithms.The results obtained show that there is a clear difference between the dense case and the sparse case in terms of the compromises to be adopted to optimize the algorithms.The analysis can be of interest to numerical library and compiler designers.1

In this paper, a review of methods for the solution of general bidiagonal systems of equations is done. Gaussian Elimination, the r-Cyclic Reduction family of algorithms and the Divide and Conquer algorithm are analyzed. A unified view of the three types of methods is proposed. The work is focussed on two basic aspects of the methods: parallelism and grain. The influence of the architecture of the target computer on the parallelism and grain of the methods is evaluated. In particular, vector processors are analyzed as target architecture and one vector processor of the Convex C-3480 is taken as a case study. For the special case of Divide and Conquer, a model is made in order to tune parallelism and grain for its optimal execution. Two conclusions can be outlined from the analysis of the methods. First, the execution time of the r-Cyclic Reduction family of algorithms is lower as r grows reaching a lower significative bound in r=9. This means that the classic use of Cyclic Reduction on vector computers is outdated from now on. Second, the higher rank versions of the r-Cyclic Reduction family of algorithms and the optimized version of Divide and Conquer behave similarly on vector computers.