Search

Rapid response, namely, low latency, is fundamental in search applications; it is particularly so in interactive search sessions, such as those encountered in conversational settings. An observation with a potential to reduce latency asserts that conversational queries exhibit a temporal locality in the lists of documents retrieved. Motivated by this observation, we propose and evaluate a client-side document embedding cache, improving the responsiveness of conversational search systems. By leveraging state-of-the-art dense retrieval models to abstract document and query semantics, we cache the embeddings of documents retrieved for a topic introduced in the conversation, as they are likely relevant to successive queries. Our document embedding cache implements an efficient metric index, answering nearest-neighbor similarity queries by estimating the approximate result sets returned. We demonstrate the efficiency achieved using our cache via reproducible experiments based on Text Retrieval Conference Conversational Assistant Track datasets, achieving a hit rate of up to 75% without degrading answer quality. Our achieved high cache hit rates significantly improve the responsiveness of conversational systems while likewise reducing the number of queries managed on the search back-end. [ABSTRACT FROM AUTHOR]

With the advent of 5G+ services, it has become increasingly convenient for mobile users to enjoy high-quality multimedia content from CDN driven streaming and catch-up TV services (Netflix, iPlayer) in the (post-) COVID over-the-top (OTT) content rush. To relieve ISP owned fixed-line networks from CDN streamed multimedia traffic, system ideas (e.g., Wi-Stitch in [45]) have been proposed to (a) leverage 5G services and enable consumers to share cached multimedia content at the edge, and (b) consequently, and more importantly, reduce IP traffic at the core network. Unfortunately, given that contemporary multimedia content might be a monetized asset, these ideas do not take this important fact into account for shared content. We present EdgeMart--a content provider (CP) federated, and computationally sustainable networked (graphical) market economy for paid-sharing of cached licensed (OTT) content with autonomous users of a wireless edge network (WEN). EdgeMart is a unique oligopoly multimedia market (economy) that comprises competing networked sub-markets of non-cooperative content sellers/buyers--each sub-market consisting of a single buyer connected (networked) to only a subset of sellers. We prove that for any WEN-supported supply-demand topology, a pure strategy EdgeMart equilibrium exists that is (a) nearly efficient (in a microeconomic sense) indicating economy sustainability, (b) robust to edge user entry/exit, and (c) can be reached in poly-time (indicating computational sustainability). In addition, we experimentally show that for physical WENs of varying densities, a rationally selfish EdgeMart economy induces similar orders of multimedia IP traffic savings when compared to the ideal (relatively less practical), altruistic, and non-monetized "economy" implemented atop the recently introduced Wi-Stitch WEN-based content trading architecture. Moreover, the EdgeMart concept helps envision a regulated edge economy of opportunistic (pay per licensed file) client services for commercial OTT platforms. [ABSTRACT FROM AUTHOR]

With the easy access to mobile networks and the proliferation of video applications, video traffic is occupying a great portion of the network traffic, which poses a new challenge of how to alleviate the heavy backhaul traffic and ensure the high quality of experience for video services. As a promising solution towards addressing this challenge, video caching in edge networks has recently received significant attention, which mostly considers the video popularity and the user preference for the video. However, few studies consider the user behavior and the user preference for different parts of the video that indeed have an essential impact on caching efficiency. Hence, this article proposes a new caching and resource scheduling scheme for adaptive bitrate videos by incorporating these fine-grained factors. We first model the video service problem as a nonlinear integer programming problem, which can be divided into a cache placement problem and an online resource scheduling problem. Then, we design efficient algorithms based on several techniques, including greedy strategy, relaxation, and rounding, to solve the two problems. Extensive experimental results based on two real-world datasets show that the proposed solution achieves superior performance compared with several state-of-the-art caching approaches. [ABSTRACT FROM AUTHOR]

The demand and usage of 360° video services are expected to increase. However, despite these services being highly bandwidth intensive, not much is known about the potential value that basic bandwidth saving techniques such as server or edge-network on-demand caching (e.g., in a CDN) could have when used for delivery of such services. This problem is both important and complicated as client-side solutions have been developed that split the full 360° view into multiple tiles, and adapt the quality of the downloaded tiles based on the user's expected viewing direction and bandwidth conditions. This article presents new trace-based analysis methods that incorporate users' viewports (the area of the full 360° view the user actually sees), a first characterization of the cross-user similarities of the users' viewports, and a trace-based analysis of the potential bandwidth savings that caching-based techniques may offer under different conditions. Our analysis takes into account differences in the time granularity over which viewport overlaps can be beneficial for resource saving techniques, compares and contrasts differences between video categories, and accounts for uncertainties in the network conditions and the prediction of the future viewing direction when prefetching. The results provide substantial insight into the conditions under which overlap can be considerable and caching effective, and inform the design of new caching system policies tailored for 360° video. [ABSTRACT FROM AUTHOR]

Machine-learned predictors, although achieving very good results for inputs resembling training data, cannot possibly provide perfect predictions in all situations. Still, decision-making systems that are based on such predictors need not only benefit from good predictions, but should also achieve a decent performance when the predictions are inadequate. In this article, we propose a prediction setup for arbitrary metrical task systems (MTS) (e.g., caching, k-server, and convex body chasing) and online matching on the line. We utilize results from the theory of online algorithms to show how to make the setup robust. Specifically, for caching, we present an algorithm whose performance, as a function of the prediction error, is exponentially better than what is achievable for generalMTS. Finally, we present an empirical evaluation of our methods on real-world datasets, which suggests practicality. [ABSTRACT FROM AUTHOR]

Embedded systems are becoming increasingly complex and heterogeneous, featuring multiple processor cores (which might themselves be heterogeneous) as well as specialized hardware accelerators, all accessing shared memory. Many accelerators are non-coherent (i.e., do not support hardware cache coherence) because it reduces hardware complexity, cost, and power consumption, while potentially offering superior performance. However, the disadvantage of non-coherence is that the software must explicitly synchronize between accelerators and processors, and this synchronization is notoriously error-prone. We propose an analysis technique to find data races in software for heterogeneous systems that include non-coherent accelerators. Our approach builds on classical results for data race detection, but the challenge turns out to be analyzing cache behavior rather than the behavior of the non-coherent accelerators. Accordingly, our central contribution is a novel, sound (data-race-preserving) abstraction of cache behavior. We prove our abstraction sound, and then to demonstrate the precision of our abstraction, we implement it in a simple dynamic race detector for a system with a processor and a massively parallel accelerator provided by a commercial FPGA-based accelerator vendor. On eleven software examples provided by the vendor, the tool had zero false positives and was able to detect previously unknown data races in two of the 11 examples. [ABSTRACT FROM AUTHOR]

Many social-media and IoT services have very large working sets consisting of billions of tiny (≈100 B) objects. Large, flash-based caches are important to serving these working sets at acceptable monetary cost. However, caching tiny objects on flash is challenging for two reasons: (i) SSDs can read/write data only in multi-KB "pages" that are much larger than a single object, stressing the limited number of times flash can be written; and (ii) very few bits per cached object can be kept in DRAM without losing flash's cost advantage. Unfortunately, existing flash-cache designs fall short of addressing these challenges: write-optimized designs require too much DRAM, and DRAM-optimized designs require too many flash writes. We present Kangaroo, a new flash-cache design that optimizes both DRAM usage and flash writes to maximize cache performance while minimizing cost. Kangaroo combines a large, set-associative cache with a small, log-structured cache. The set-associative cache requires minimal DRAM, while the log-structured cache minimizes Kangaroo's flash writes. Experiments using traces from Meta and Twitter show that Kangaroo achieves DRAM usage close to the best prior DRAM-optimized design, flash writes close to the best prior write-optimized design, and miss ratios better than both. Kangaroo's design is Pareto-optimal across a range of allowed write rates, DRAM sizes, and flash sizes, reducing misses by 29% over the state of the art. These results are corroborated by analytical models presented herein and with a test deployment of Kangaroo in a production flash cache at Meta. [ABSTRACT FROM AUTHOR]

Active storage devices and in-storage computing are proposed and developed in recent years to effectively reduce the amount of required data traffic and to improve the overall application performance. They are especially preferred in the compute-storage disaggregated infrastructure. In both techniques, a simple computing module is added to storage devices/servers such that some stored data can be processed in the storage devices/servers before being transmitted to application servers. This can reduce the required network bandwidth and offload certain computing requirements from application servers to storage devices/servers. However, several challenges exist when designing an in-storage computing-based architecture for applications. These include what computing functions need to be offloaded, how to design the protocol between in-storage modules and application servers, and how to deal with the caching issue in application servers. HBase is an important and widely used distributed Key-Value Store. It stores and indexes key-value pairs in large files in a storage system like HDFS. However, its performance especially read performance, is impacted by the heavy traffics between HBase RegionServers and storage servers in the compute-storage disaggregated infrastructure when the available network bandwidth is limited. We propose an In-Storage-based HBase architecture, called IS-HBase, to improve the overall performance and to address the aforementioned challenges. First, IS-HBase executes a data pre-processing module (In-Storage ScanNer, called ISSN) for some read queries and returns the requested key-value pairs to RegionServers instead of returning data blocks in HFile. IS-HBase carries out compactions in storage servers to reduce the large amount of data being transmitted through the network and thus the compaction execution time is effectively reduced. Second, a set of new protocols is proposed to address the communication and coordination between HBase RegionServers at computing nodes and ISSNs at storage nodes. Third, a new self-adaptive caching scheme is proposed to better serve the read queries with fewer I/O operations and less network traffic. According to our experiments, the IS-HBase can reduce up to 97% network traffic for read queries and the throughput (queries per second) is significantly less affected by the fluctuation of available network bandwidth. The execution time of compaction in IS-HBase is only about 6.31% - 41.84% of the execution time of legacy HBase. In general, IS-HBase demonstrates the potential of adopting in-storage computing for other data-intensive distributed applications to significantly improve performance in compute-storage disaggregated infrastructure. [ABSTRACT FROM AUTHOR]

In order for a software system to self-adapt, it often needs to be aware of its behavior. A typical way of achieving this is by means of the runtime collection of execution traces, which requires the interception of the execution of, e.g. methods, and record information about them. Although this is simple in theory, in practice, it can be very costly because it might have a significant impact on the application performance or require huge amounts of memory or storage. This becomes a significant issue mainly in real-time applications, which are time-sensitive and must often meet deadlines in resource-constrained environments. We thus in this paper propose a two-phase tracing framework to cope with the monitoring overhead. In its first phase, the application is monitored in a lightweight fashion providing information for the second phase, which identifies an adaptive configuration and samples traces according to the current configuration. The adaptive configuration is determined by a set of criteria, specified through a proposed domain-specific language. We empirically evaluate our framework by instantiating it as a reduced-overhead monitoring solution, integrated into an existing automated application-level caching approach. We demonstrate that our solution reduces the overhead caused by monitoring, without compromising the performance improvements provided by the caching approach. [ABSTRACT FROM AUTHOR]

Caching and prefetching are important mechanisms for speeding up access time to data on secondary storage. Recent work in competitive online algorithms has uncovered several promising new algorithms for caching. In this paper, we apply a form of the competitive philosophy for the first time to the problem of prefetching to develop an optimal universal prefetcher in terms of fault rate, with particular applications to large-scale databases and hypertext systems. Our prediction algorithms with particular applications to large-scale databases and hypertext systems. Our prediction algorithms for prefetching are novel in that they are based on data compression techniques that are both theoretically optimal and good in practice. Intuitively, in order to compress data effectively, you have to be able to predict future data well, and thus good data compressors should be able to predict well for purposes of prefetching. We show for powerful models such as Markov sources and mthe order Markov sources that the page fault rate incurred by our prefetching algorithms are optimal in the limit for almost all sequences of page requests. [ABSTRACT FROM AUTHOR]

State-of-the-art software-defined wide area networks (SD-WANs) provide the foundation for flexible and highly resilient networking. In this work, we design, implement, and evaluate a novel architecture (denoted as SABR) that leverages the benefits of software-defined networking (SDN) to provide network-assisted adaptive bitrate streaming. With clients retaining full control of their streaming algorithms, we clearly show that by this network assistance, both the clients and the content providers benefit significantly in terms of quality of experience (QoE) and content origin offloading. SABR utilizes information on available bandwidths per link and network cache contents to guide video streaming clients with the goal of improving the viewer's QoE. In addition, SABR uses SDN capabilities to dynamically program flows to optimize the utilization of content delivery network caches. Backed by our study of SDN-assisted streaming, we discuss the change in the requirements for network-to-player APIs that enables flexible video streaming. We illustrate the difficulty of the problem and the impact of SDN-assisted streaming on QoE metrics using various well-established player algorithms. We evaluate SABR together with state-of-the-art dynamic adaptive streaming over HTTP (DASH) quality adaptation algorithms through a series of experiments performed on a real-world, SDN-enabled testbed network with minimal modifications to an existing DASH client. In addition, we compare the performance of different caching strategies in combination with SABR. Our trace-based measurements show the substantial improvement in cache hit rates and QoE metrics in conjunction with SABR indicating a rich design space for jointly optimized SDN-assisted caching architectures for adaptive bitrate video streaming applications. [ABSTRACT FROM AUTHOR]

Knowledge Bases (KBs) are widely used as one of the fundamental components in SemanticWeb applications as they provide facts and relationships that can be automatically understood by machines. Curated knowledge bases usually use Resource Description Framework (RDF) as the data representation model. To query the RDF-presented knowledge in curated KBs, Web interfaces are built via SPARQL Endpoints. Currently, querying SPARQL Endpoints has problems like network instability and latency, which affect the query efficiency. To address these issues, we propose a client-side caching framework, SPARQL Endpoint Caching Framework (SECF), aiming at accelerating the overall querying speed over SPARQL Endpoints. SECF identifies the potential issued queries by leveraging the querying patterns learned from clients' historical queries and prefecthes/caches these queries. In particular,we develop a distance function based on graph edit distance to measure the similarity of SPARQL queries. We propose a feature modelling method to transform SPARQL queries to vector representation that are fed into machine-learning algorithms. A time-aware smoothingbased method, Modified Simple Exponential Smoothing (MSES), is developed for cache replacement. Extensive experiments performed on real-world queries showcase the effectiveness of our approach, which outperforms the state-of-the-art work in terms of the overall querying speed. [ABSTRACT FROM AUTHOR]

This article proposes to use a frequency-based cache admission policy in order to boost the effectiveness of caches subject to skewed access distributions. Given a newly accessed item and an eviction candidate from the cache, our scheme decides, based on the recent access history, whether it is worth admitting the new item into the cache at the expense of the eviction candidate. This concept is enabled through a novel approximate LFU structure called TinyLFU, which maintains an approximate representation of the access frequency of a large sample of recently accessed items. TinyLFU is very compact and lightweight as it builds upon Bloom filter theory. We study the properties of TinyLFU through simulations of both synthetic workloads and multiple real traces from several sources. These simulations demonstrate the performance boost obtained by enhancing various replacement policies with the TinyLFU admission policy. Also, a new combined replacement and eviction policy scheme nicknamed W-TinyLFU is presented. W-TinyLFU is demonstrated to obtain equal or better hit ratios than other state-of-the-art replacement policies on these traces. It is the only scheme to obtain such good results on all traces. [ABSTRACT FROM AUTHOR]

Many content distribution architectures offer desirable elements that lead to less bandwidth usage, reduced network congestion, higher content availability, and reduced costs. However, their level of adoption and utilization in commercial environments depends on the level of content accounting and accountability they offer. Content accounting refers to any information that a content distributor needs to track relating to the delivery of content to its intended consumers. In contrast, content accountability refers to the willingness of the communicating infrastructure to produce accurate and verifiable information about the content distribution process. This article surveys existing and proposed future content delivery architectures detailing their methodologies for providing efficient low-cost content distribution, content accounting, and accountability across trustworthy and untrustworthy infrastructures. We use two methods to help identify the drawbacks and merits of these architectures. The first is a taxonomy for accounting information based on our analysis of logging information gathered from the surveyed systems. The second is a generic model for content distribution based on a synthesis of desirable elements from the surveyed architectures. These methods help highlight key architectural elements required for efficient low-cost content distribution. Finally, we identify outstanding challenges related to establishing accountability in accounting information produced for content distributed across trusted and untrusted infrastructures. [ABSTRACT FROM AUTHOR]

In this article, we take advantage of the user behavior of requesting videos from the top of the related list provided by YouTube to improve the performance of YouTube caches. We recommend that local caches reorder the related lists associated with YouTube videos, presenting the cached content above noncached content. We argue that the likelihood that viewers select content from the top of the related list is higher than selection from the bottom, and pushing contents already in the cache to the top of the related list would increase the likelihood of choosing cached content. To verify that the position on the list really is the selection criterion more dominant than the content itself, we conduct a user study with 40 YouTube-using volunteers who were presented with random related lists in their everyday YouTube use. After confirming our assumption, we analyze the benefits of our approach by an investigation that is based on two traces collected from a university campus. Our analysis shows that the proposed reordering approach for related lists would lead to a 2 to 5 times increase in cache hit rate compared to an approach without reordering the related list. This increase in hit rate would lead to reduction in server load and backend bandwidth usage, which in turn reduces the latency in streaming the video requested by the viewer and has the potential to improve the overall performance of YouTube's content distribution system. An analysis of YouTube's recommendation system reveals that related lists are created from a small pool of videos, which increases the potential for caching content from related lists and reordering based on the content in the cache. [ABSTRACT FROM AUTHOR]

We design algorithms that, given a collection of documents and a distribution over user queries, return a small subset of the document collection in such a way that we can efficiently provide high-quality answers to user queries using only the selected subset. This approach has applications when space is a constraint or when the query-processing time increases significantly with the size of the collection. We study our algorithms through the lens of stochastic analysis and prove that even though they use only a small fraction of the entire collection, they can provide answers to most user queries, achieving a performance close to the optimal. To complement our theoretical findings, we experimentally show the versatility of our approach by considering two important cases in the context of Web search. In the first case, we favor the retrieval of documents that are relevant to the query, whereas in the second case we aim for document diversification. Both the theoretical and the experimental analysis provide strong evidence of the potential value of query covering in diverse application scenarios. [ABSTRACT FROM AUTHOR]

Due to the large access latency of hard disks during data retrieval in computer systems, buffer caching mechanisms have been studied extensively in database and operating systems. By storing requested data into the buffer cache, subsequent requests can be directly serviced without accessing slow disk storage. Meanwhile, high-speed storage media like PCM (phase-change memory) have emerged recently, and one may wonder if the traditional buffer cache will be still effective for these high-speed storage media. This article answers the question by showing that the buffer cache is still effective in such environments due to the software overhead and the bimodal data access characteristics. Based on this observation, we present a new buffer cache management scheme appropriately designed for the system where the speed gap between cache and storage is narrow. To this end, we analyze the condition that caching will be effective and find the characteristics of access patterns that can be exploited in managing buffer cache for high performance storage like PCM. [ABSTRACT FROM AUTHOR]

Ranked result lists with query-dependent snippets have become state of the art in text search. They are typically implemented by searching, at query time, for occurrences of the query words in the top-ranked documents. This document-based approach has three inherent problems: (I) when a document is indexed by terms which it does not contain literally (e.g., related words or spelling variants), localization of the corresponding snippets becomes problematic; (ii) each query operator (e.g., phrase or proximity search) has to be implemented twice, on the index side in order to compute the correct result set, and on the snippetgeneration side to generate the appropriate snippets; and (iii) in a worst case, the whole document needs to be scanned for occurrences of the query words, which could be problematic for very long documents. We present a new index-based method that localizes snippets by information solely computed from the index and that overcomes all three problems. Unlike previous index-based methods, we show how to achieve this at essentially no extra cost in query processing time, by a technique we call operator inversion. We also show how our index-based method allows the caching of individual segments instead of complete documents, which enables a significantly larger cache hit-ratio as compared to the document-based approach. We have fully integrated our implementation with the CompleteSearch engine. [ABSTRACT FROM AUTHOR]

Video streaming is the core technology for online video delivery systems. Initial research on this technology faced many challenges. In this article, lessons learned from beginning trials are discussed; some pioneering works that provided early solutions and inspired subsequent research are presented; and new techniques required for emerging applications are examined. [ABSTRACT FROM AUTHOR]

Video on Demand (VoD) services allow users to select and locally consume remotely stored content. We investigate the use of caching to solve the scalability issues of several existing VoD providers. We propose metrics and goals that define the requirements of a caching framework for CDNs of VoD systems. Using data logs collected from Motorola equipment from Comcast VoD deployments we show that several classic caching solutions do not satisfy the proposed goals. We address this issue by developing novel techniques for predicting future values of several metrics of interest. We rely on computed predictions to define the penalty imposed on the system, both network and caching sites, when not storing individual items. We use item penalties to devise novel caching and static content placement strategies. We use the previously mentioned data logs to validate our solutions and show that they satisfy all the defined goals. [ABSTRACT FROM AUTHOR]

Content discovery is a major source of latency in peer-to-peer (P2P) media streaming systems, especially in the presence of noncontinuous user access, such as random seek in Video-on-Demand (VoD) streaming and teleportation in a Networked Virtual Environment (NVE). After the aforementioned user interactions, streaming systems often need to initiate the content discovery process to identify where to retrieve the requested media objects. Short content lookup latency is demanded to ensure smooth user experience. Existing content discovery systems based on either a Distributed Hash Table (DHT) or gossip mechanism cannot cope with noncontinuous access efficiently due to their long lookup latency. In this work, we propose an access-pattern-driven distributed caching middleware named APRICOD, which caters for fast and scalable content discovery in peer-to-peer media streaming systems, especially when user interactions are present. APRICOD exploits correlations among media objects accessed by users, and adapts to shift in the user access pattern automatically. We first present a general APRICOD design that can be used with any existing content discovery system. We then present an implementation of APRICOD on top of Pastry, which we use to evaluate APRICOD. Our evaluation in a 1024-node system, using a Second Life trace with 5, 735 users and a VoD trace with 54 users, shows that APRICOD can effectively resolve all continuous access queries with a single hop deterministically with node failure as an exception, and resolve noncontinuous access queries with a single hop with high probability. [ABSTRACT FROM AUTHOR]

This article presents asymptotically optimal algorithms for rectangular matrix transpose, fast Fourier transform (FFT), and sorting on computers with multiple levels of caching. Unlike previous optimal algorithms, these algorithms are cache oblivious: no variables dependent on hardware parameters, such as cache size and cache-line length, need to be tuned to achieve optimality Nevertheless, these algorithms use an optimal amount of work and move data optimally among multiple levels of cache. For a cache with size M and cache-line length B where M = Θ(B2), the number of cache misses for an m x n matrix transpose is Θ(1 + mn/B). The number of cache misses for either an n-point FFT or the sorting of n numbers is Θ (1 + (n/B)(1 + logM n)). We also give a Θ(mnp)-work algorithm to multiply an m x n matrix by an n x p matrix that incurs Θ (1 + (mn + np + mp)/B + mnp/B√M) cache faults. We introduce an "ideal-cache" model to analyze our algorithms. We prove that an optimal cache-oblivious algorithm designed for two levels of memory is also optimal for multiple levels and that the assumption of optimal replacement in the ideal-cache model can be simulated efficiently by LRU replacement. We offer empirical evidence that cache-oblivious algorithms perform well in practice. [ABSTRACT FROM AUTHOR]

Automatic recycling of intermediate results to improve both query response time and throughput is a grand challenge for state-of-the-art databases. Tuples are loaded and streamed through a tuple-at-a-time processing pipeline, avoiding materialization of intermediates as much as possible. This limits the opportunities for reuse of overlapping computations to DBA-defined materialized views and function/result cache tuning. In contrast, the operator-at-a-time execution paradigm produces fully materialized results in each step of the query plan. To avoid resource contention, these intermediates are evicted as soon as possible. In this article we study an architecture that harvests the byproducts of the operator-at-a-time paradigm in a column-store system using a lightweight mechanism, the recycler. The key challenge then becomes the selection of the policies to admit intermediates to the resource pool, to determine their retention period, and devise the eviction strategy when facing resource limitations. The proposed recycling architecture has been implemented in an open-source system. An experimental analysis against the TPC-H ad-hoc decision support benchmark and a complex, real-world application (SkyServer) demonstrates its effectiveness in terms of self-organizing behavior and its significant performance gains. The results indicate the potentials of recycling intermediates and charts a route for further development of database kernels. [ABSTRACT FROM AUTHOR]

We describe the architecture of a novel system for precomputing sparse directional occlusion caches. These caches are used for accelerating a fast cinematic lighting pipeline that works in the spherical harmonics domain. The system was used as a primary lighting technology in the movie Avatar, and is able to efficiently handle massive scenes of unprecedented complexity through the use of a flexible, stream-based geometry processing architecture, a novel out-of-core algorithm for creating efficient ray tracing acceleration structures, and a novel out-of-core GPU ray tracing algorithm for the computation of directional occlusion and spherical integrals at arbitrary points. [ABSTRACT FROM AUTHOR]

Content distribution networks (CDNs) have gained considerable attention in the past few years. Hence there is need for developing frameworks for carrying out CDN simulations. In this article we present a modeling and simulation framework for CDNs, called CDNsim. CDNsim has been designated to provide a realistic simulation for CDNs, simulating the surrogate servers, the TCP/IP protocol, and the main CDN functions. The main advantages of this tool are its high performance, its extensibility, and its user interface, which is used to configure its parameters. CDNsim provides an automated environment for conducting experiments and extracting client, server, and network statistics. The purpose of CDNsim is to be used as a testbed for CDN evaluation and experimentation. This is quite useful to both the research community (to experiment with new CDN data management techniques), and for CDN developers (to evaluate profits on prior certain CDN installations). [ABSTRACT FROM AUTHOR]

In this article we study the trade-offs in designing efficient caching systems for Web search engines. We explore the impact of different approaches, such as static vs. dynamic caching, and caching query results vs. caching posting lists. Using a query log spanning a whole year, we explore the limitations of caching and we demonstrate that caching posting lists can achieve higher hit rates than caching query answers. We propose a new algorithm for static caching of posting lists, which outperforms previous methods. We also study the problem of finding the optimal way to split the static cache between answers and posting lists. Finally, we measure how the changes in the query log influence the effectiveness of static caching, given our observation that the distribution of the queries changes slowly over time. Our results and observations are applicable to different levels of the data-access hierarchy, for instance, for a memory/disk layer or a broker/remote server layer. [ABSTRACT FROM AUTHOR]

Video-on-Demand (VoD) is a compelling application, but costly. VoD is costly due to the load it places on video source servers. Many have proposed using peer-to-peer (P2P) techniques to shift load from servers to peers. Yet, nobody has implemented and deployed a system to openly and systematically evaluate how these techniques work. This article describes the design, implementation and evaluation of GridCast, a real deployed P2P VoD system. GridCast has been live on CERNET since May of 2006. It provides seek, pause, and play operations, and employs peer sharing to improve system scalability. In peak months, GridCast has served videos to 23,000 unique users. From the first deployment, we have gathered information to understand the system and evaluate how to further improve peer sharing through caching and replication. We first show that GridCast with single video caching (SVC) can decrease load on source servers by an average of 22% from a client-server architecture. We analyze the net effect on system resources and determine that peer upload is largely idle. This leads us to changing the caching algorithm to cache multiple videos (MVC). MVC decreases source load by an average of 51% over the client-server. The improvement is greater as user load increases. This bodes well for peer-assistance at larger scales. A detailed analysis of MVC shows that departure misses become a major issue in a P2P VoD system with caching optimization. Motivated by this observation, we examine how to use replication to eliminate departure misses and further reduce server load. A framework for lazy replication is presented and evaluated in this article. In this framework, two predictors are plugged in to create the working replication algorithm. With these two simple predictors, lazy replication can decrease server load by 15% from MVC with only a minor increase in network traffic. [ABSTRACT FROM AUTHOR]

Sorting is one of the most important and well-studied problems in computer science. Many good algorithms are known which offer various trade-offs in efficiency, simplicity, memory use, and other factors. However, these algorithms do not take into account features of modern computer architectures that significantly influence performance. Caches and branch predictors are two such features and, while there has been a significant amount of research into the cache performance of general purpose sorting algorithms, there has been little research on their branch prediction properties. In this paper, we empirically examine the behavior of the branches in all the most common sorting algorithms. We also consider the interaction of cache optimization on the predictability of the branches in these algorithms. We find insertion sort to have the fewest branch mispredictions of any comparison-based sorting algorithm, that bubble and shaker sort operate in a fashion that makes their branches highly unpredictable, that the unpredictability of shellsort's branches improves its caching behavior, and that several cache optimizations have little effect on mergesort's branch mispredictions. We find also that optimizations to quicksort, for example the choice of pivot, have a strong influence on the predictability of its branches. We point out a simple way of removing branch instructions from a classic heapsort implementation and also show that unrolling a loop in a cache-optimized heapsort implementation improves the predicitability of its branches. Finally, we note that when sorting random data two-level adaptive branch predictors are usually no better than simpler bimodal predictors. This is despite the fact that two-level adaptive predictors are almost always superior to bimodal predictors, in general. [ABSTRACT FROM AUTHOR]

On-disk sequentiality of requested blocks, or their spatial locality, is critical to real disk performance where the throughput of access to sequentially-placed disk blocks can be an order of magnitude higher than that of access to randomly-placed blocks. Unfortunately, spatial locality of cached blocks is largely ignored, and only temporal locality is considered in current system buffer cache managements. Thus, disk performance for workloads without dominant sequential accesses can be seriously degraded. To address this problem, we propose a scheme called DULO (DUal LOcality) which exploits both temporal and spatial localities in the buffer cache management. Leveraging the filtering effect of the buffer cache, DULO can influence the I/O request stream by making the requests passed to the disk more sequential, thus significantly increasing the effectiveness of I/O scheduling and prefetching for disk performance improvements. We have implemented a prototype of DULO in Linux 2.6.11. The implementation shows that DULO can significantly increases disk I/O throughput for real-world applications such as a Web server, TPC benchmark, file system benchmark, and scientific programs. It reduces their execution times by as much as 53%. [ABSTRACT FROM AUTHOR]

We focus in this work on an aspect of online computation that is not addressed by standard competitive analysis, namely, identifying request sequences for which nontrivial online algorithms are useful versus request sequences for which all algorithms perform equally poorly. The motivations for this work are advanced system and architecture designs which allow the operating system to dynamically allocate resources to online protocols such as prefetching and caching. To utilize these features, the operating system needs to identify data streams that can benefit from more resources. Our approach in this work is based on the relation between entropy, compression, and gambling, extensively studied in information theory. It has been shown that in some settings, entropy can either fully or at least partially characterize the expected outcome of an iterative gambling game. Our goal is to study the extent to which the entropy of the input characterizes the expected performance of online algorithms for problems that arise in computer applications. We study bounds based on entropy for three classical online problems—list accessing, prefetching, and caching. Our bounds relate the performance of the best online algorithm to the entropy, a parameter intrinsic to characteristics of the request sequence. This is in contrast to the competitive ratio parameter of competitive analysis, which quantifies the performance of the online algorithm with respect to an optimal offline algorithm. For the prefetching problem, we give explicit upper and lower bounds for the performance of the best prefetching algorithm in terms of the entropy of the request sequence. In contrast, we show that the entropy of the request sequence alone does not fully capture the performance of online list accessing and caching algorithms. [ABSTRACT FROM AUTHOR]

We introduce a new paradigm for querying strings in external memory, suited to the execution of sequences of operations. Formally, given a dictionary of n strings S1, … , Sn , we aim at supporting a search sequence for m not necessarily distinct strings T1, T2, … , Tm, as well as inserting and deleting individual strings. The dictionary is stored on disk, where each access to a disk page fetches B items, the cost of an operation is the number of pages accessed (I/Os), and efficiency must be attained on entire sequences of string operations rather than on individual ones. Our approach relies on a novel and conceptually simple self-adjusting data structure (SASL) based on skip lists, that is also interesting per se. The search for the whole sequence T1, T1, … , Tm can be done in an expected number of I/Os: ["Multiple line equation(s) cannot be represented in ASCII text"]. where each Tj may or may not be present in the dictionary, and ni is the number of times Si is queried (i.e., the number of Tjs equal to Si ). Moreover, inserting or deleting a string Si takes an expected amortized number ["Multiple line equation(s) cannot be represented in ASCII text"]. The term ["Multiple line equation(s) cannot be represented in ASCII text"] in the search formula is a lower bound for reading the input, and the term ["Multiple line equation(s) cannot be represented in ASCII text"]. (entropy of the query sequence) is a standard information-theoretic lower bound.We regard this result as the static optimality theorem for external-memory string access, as compared to Sleator and Tarjan's classical theorem for numerical dictionaries [Sleator and Tarjan 1985]. Finally,we reformulate the search bound if a cache is available, taking advantage of common prefixes among the strings examined in the search. [ABSTRACT FROM AUTHOR]

Wide area data delivery requires timely propagation of up-to-date information to thousands of clients over a wide area network. Applications include web caching, RSS source monitoring, and email access via a mobile network. Data sources vary widely in their update patterns and may experience different update rates at different times or unexpected changes to update patterns. Traditional data delivery solutions are either push-based, which requires servers to push updates to clients, or pull-based, which require clients to check for updates at servers. While push-based solutions ensure timely data delivery, they are not always feasible to implement and may not scale to a large number of clients. In this article, we present adaptive pull-based policies that explicitly aim to reduce the overhead of contacting remote servers, compared to existing pull-based policies, while meeting freshness requirements. We model updates to data sources using update histories, and present two novel history-based policies to estimate when updates occur; they are based on individual history and aggregate history. These policies are presented within an architectural framework that supports their deployment either client-side or server-side. We further develop two adaptive policies to handle objects that initially may have insufficient history or objects that experience changes in update patterns. Extensive experimental evaluation using three data traces from diverse applications shows that history-based policies can reduce contact between clients and servers by up to 60% compared to existing pull-based policies while providing a comparable level of data freshness. Our experiments further demonstrate that our adaptive policies can select the best policy to match the behavior of an object and perform better than any individual policy, thus they dominate standalone policies. [ABSTRACT FROM AUTHOR]

This article discusses efficiency and effectiveness issues in caching the results of queries submitted to a Web search engine (WSE). We propose SDC (Static Dynamic Cache), a new caching strategy aimed to efficiently exploit the temporal and spatial locality present in the stream of processed queries. SDC extracts from historical usage data the results of the most frequently submitted queries and stores them in a static, read-only portion of the cache. The remaining entries of the cache are dynamically managed according to a given replacement policy and are used for those queries that cannot be satisfied by the static portion. Moreover, we improve the hit ratio of SDC by using an adaptive prefetching strategy, which anticipates future requests by introducing a limited overhead over the back-end WSE. We experimentally demonstrate the superiority of SDC over purely static and dynamic policies by measuring the hit ratio achieved on three large query logs by varying the cache parameters and the replacement policy used for managing the dynamic part of the cache. Finally, we deploy and measure the throughput achieved by a concurrent version of our caching system. Our tests show how the SDC cache can be efficiently exploited by many threads that concurrently serve the queries of different users. [ABSTRACT FROM AUTHOR]

As improvements in processor performance continue to far outpace improvements in storage performance, I/O is increasingly the bottleneck in computer systems, especially in large database systems that manage huge amounts of data. The key to achieving good I/O performance is to thoroughly understand its characteristics. In this article we present a comprehensive analysis of the logical I/O reference behavior of the peak production database workloads from ten of the world's largest corporations. In particular, we focus on how these workloads respond to different techniques for caching, prefetehing, and write buffering. Our findings include several broadly applicable rules of thumb that describe how effective the various I/O optimization techniques are for the production workloads. For instance, our results indicate that the buffer pool miss ratio tends to be related to the ratio of buffer pool size to data size by an inverse square root rule. A similar fourth root rule relates the write miss ratio and the ratio of buffer pool size to data size. In addition, we characterize the reference characteristics of workloads similar to the Transaction Processing Performance Council (TPC) benchmarks C (TPC-C) and D (TPC-D), which are de facto standard performance measures for online transaction processing (OLTP) systems and decision support systems (DSS), respectively. Since benchmarks such as TPC-C and TPC-D can only be used effectively if their strength and limitation are understood, a major focus of our analysis is identifying aspects of the benchmarks that stress the system differently than the production workloads. We discover that for the most part, the reference behavior of TPC-C and TPC-D fall within the range of behavior exhibited by the production workloads. However, there are some noteworthy exceptions that affect well-known I/O optimization techniques such as caching (LRU for TPC-D), prefetching (TPC-C exhibites no significant sequentiality), and write buffering (write buffering is less effective for the TPC benchmarks). While the two TPC benchmarks generally complement on another in reflecting the characteristics of the production workloads, there remain aspects of the real workloads that are known represented by either of the benchmarks. [ABSTRACT FROM AUTHOR]

One of the features that distinguishes digital libraries from traditional databases is new cost models for client access to intellectual property. Clients will pay for accessing data items in digital libraries, and we believe that optimizing these costs will be as important as optimizing performance in traditional databases. In this article we discuss cost models and protocols for accessing digital libraries, with the objective of determining the minimum cost protocol for each model. We expect that in the future information appliances will come equipped with a cost optimizer, in the same way that computers today come with a built-in operating system. This article makes the initial steps towards a theory and practice of intellectual property cost management. [ABSTRACT FROM AUTHOR]

Recent advances in wireless data networking and portable information appliances have engendered a new paradigm of computing, called mobile computing, in which users carrying portable devices have access to data and information services regardless of their physical location or movement behavior. In the meantime, research addressing information access in mobile environments has proliferated. In this survey, we provide a concrete framework and categorization of the various ways of supporting mobile client-server computing for information access. We examine characteristics of mobility that distinguish mobile client-server computing from its traditional counterpart. We provide a comprehensive analysis of new paradigms and enabler concepts for mobile client-server computing, including mobile-aware adaptation, extended client-server model, and mobile data access. A comparative and detailed review of major research prototypes for mobile information access is also presented. [ABSTRACT FROM AUTHOR]