Efficient Nearest Neighbor (NN) search in high-dimensional spaces is a foundation of many multimedia retrieval systems. A common approach is to rely on Product Quantization, which allows the storage of large vector databases in memory and efficient distance computations. Yet, implementations of nearest neighbor search with Product Quantization have their performance limited by the many memory accesses they perform. Following this observation, André et al. proposed Quick ADC with up to 6× faster implementations of PQ m×4 product quantizers (PQ) leveraging specific SIMD instructions. Quicker ADC is a generalization of Quick ADC not limited to PQ m×4 codes and supporting AVX-512, the latest revision of SIMD instruction set. In doing so, Quicker ADC faces the challenge of using efficiently 5,6 and 7-bit shuffles that do not align to computer bytes or words. To this end, we introduce (i) irregular product quantizers combining sub-quantizers of different granularity and (ii) split tables allowing lookup tables larger than registers. We evaluate Quicker ADC with multiple indexes including Inverted Multi-Indexes and IVF HNSW and show that it outperforms the reference optimized implementations (i.e., FAISS and polysemous codes) for numerous configurations. Finally, we release an open-source fork of FAISS enhanced with Quicker ADC.

Hash tables are essential data-structures for networking applications (e.g., connection tracking, firewalls, network address translators). Among these, cuckoo hash tables provide excellent performance by processing lookups with very few memory accesses (2 to 3 per lookup). Yet, they remain memory bound and each memory access impacts performance. In this paper, we propose algorithmic improvements to cuckoo hash tables to eliminate unnecessary memory accesses, without altering the properties of the original cuckoo hash table so that all existing theoretical analysis remain applicable. We also present an implementation tailored to run efficiently on Intel Xeon processors, thus supporting NFV and softwarization trends and compare it to the optimized implementation of DPDK. On a single core, our implementation achieves 37M positive lookups per second (i.e., when the key looked up is present in the table), and 60M negative lookups per second, a 45% to 70% improvement over DPDK.

Efficient Nearest Neighbor (NN) search in high-dimensional spaces is a foundation of many multimedia retrieval systems. Because it offers low responses times, Product Quantization (PQ) is a popular solution. PQ compresses high-dimensional vectors into short codes using several sub-quantizers, which enables in-RAM storage of large databases. This allows fast answers to NN queries, without accessing the SSD or HDD. The key feature of PQ is that it can compute distances between short codes and high-dimensional vectors using cache-resident lookup tables. The efficiency of this technique, named Asymmetric Distance Computation (ADC), remains limited because it performs many cache accesses.

With the emergence of online platforms for (social) sharing, collaboration and backing up, mobile users generate ever-increasing amounts of digital data, such as documents, photos, and videos, which they upload while on the go. Cellular Internet connectivity (e.g., 3G/4G) enables mobile users to upload their data but drains the battery of their devices and overloads mobile service providers. Wi-Fi data offloading overcomes the aforementioned issues for delay-tolerant data. However, it comes at the cost of constrained mobility for users, as they are required to stay within a given area while the data is uploaded. The up-link of the broadband connection of the access point often constitutes a bottleneck and incurs waiting times of up to tens of minutes. In this paper, we advocate the exploitation of the storage capabilities of common devices located on the Wi-Fi access point's LAN, typically residential gateways, NAS units or set-top boxes, to decrease the waiting time. We propose Hoop, a system for offloading upload tasks onto such devices. Hoop operates seamlessly on http(s) post , which makes it highly generic and widely applicable; it also requires limited changes on the gateways and on the web servers and none to existing protocols or browsers. Hoop is secure and, in a typical setting, reduces the waiting time by up to a factor of 46. We analyze the security of Hoop and evaluate its performance by correlating mobility traces of users with the position of the Wi-Fi access points of a leading community network (i.e., FON) that relies on major national ISPs. We show that, in practice, Hoop drastically decreases the delay between the time the photo is taken and the time it is uploaded, compared to regular Wi-Fi data offloading. We also demonstrate the practicality of Hoop by implementing it on a wireless router.

Nearest Neighbor (NN) search in high dimension is an important feature in many applications (e.g., image retrieval, multimedia databases). Product Quantization (PQ) is a widely used solution which offers high performance, i.e., low response time while preserving a high accuracy. PQ represents high-dimensional vectors (e.g., image descriptors) by compact codes. Hence, very large databases can be stored in memory, allowing NN queries without resorting to slow I/O operations. PQ computes distances to neighbors using cache-resident lookup tables, thus its performance remains limited by (i) the many cache accesses that the algorithm requires, and (ii) its inability to leverage SIMD instructions available on modern CPUs. In this paper, we advocate that cache locality is not sufficient for efficiency. To address these limitations, we design a novel algorithm, PQ Fast Scan, that transforms the cache-resident lookup tables into small tables, sized to fit SIMD registers. This transformation allows (i) in-register lookups in place of cache accesses and (ii) an efficient SIMD implementation. PQ Fast Scan has the exact same accuracy as PQ, while having 4 to 6 times lower response time (e.g., for 25 million vectors, scan time is reduced from 74ms to 13ms).

In this paper, we study cache policies for cloud-based caching. Cloud-based caching uses cloud storage services such as Amazon S3 as a cache for data items that would have been recomputed otherwise. Cloud-based caching departs from classical caching: cloud resources are potentially infinite and only paid when used, while classical caching relies on a fixed storage capacity and its main monetary cost comes from the initial investment. To deal with this new context, we design and evaluate a new caching policy that minimizes the cost of a cloud-based system. The policy takes into account the frequency of consumption of an item and the cloud cost model. We show that this policy is easier to operate, that it scales with the demand and that it outperforms classical policies managing a fixed capacity.

Modern storage systems now typically combine plain replication and erasure codes to reliably store large amount of data in datacenters. Plain replication allows a fast access to popular data, while erasure codes, e.g., Reed-Solomon codes, provide a storage-efficient alternative for archiving less popular data. Although erasure codes are now increasingly employed in real systems, they experience high overhead during maintenance, i.e., upon failures, typically requiring files to be decoded before being encoded again to repair the encoded blocks stored at the faulty node.

Mobile users generate ever-increasing amounts of digital data, such as photos, which they upload, while on the go, to online services. 3G connectivity enables mobile users to upload their data while on the go but drains the battery of their devices and overloads mobile service providers. Wi-Fi data offloading overcomes the aforementioned issues for delay-tolerant data, at the cost of constrained mobility for users as they are required to stay within a given area while the data is uploaded. The up-link of the broadband connection of the access point is a bottleneck and incurs significant waiting times. In this paper, we advocate the exploitation of the storage capabilities of common devices located on the Wi-Fi access point LAN, typically residential gateways, to decrease the waiting time. We propose Hoop, a system for offloading upload tasks onto such devices. Hoop operates seamlessly on HTTP(S) POSTs, making it highly generic, it also requires limited changes on the gateways and on the web server and none to existing protocols or browsers. Hoop is secure and, in a typical setting, reduces the waiting time by up to a factor of 46. By correlating mobility traces with the positions of the Wi-Fi access points of a major community network, we show that Hoop drastically decreases the delay between the time a photo is taken and the time it is uploaded, compared to regular Wi-Fi offloading.

We study the exact and optimal repair of multiple failures in codes for distributed storage. More particularly, we examine the use of interference alignment to build exact scalar minimum storage coordinated regenerating codes (MSCR). We show that it is possible to build codes for the case of k = 2 and d ≥ k by aligning interferences independently but that this technique cannot be applied as soon as k ≥ 3 and d >; k. Our results also apply to adaptive regenerating codes.

The explosion of the amount of data stored in cloud systems calls for more efficient paradigms for redundancy. While replication is widely used to ensure data availability, erasure correcting codes provide a much better trade-off between storage and availability. Regenerating codes are good candidates for they also offer low repair costs in term of network bandwidth. While they have been proven optimal, they are difficult to understand and parameterize. In this paper we provide an analysis of regenerating codes for practitioners to grasp the various trade-offs. More specifically we make two contributions: (i) we study the impact of the parameters by conducting an analysis at the level of the system, rather than at the level of a single device, (ii) we compare the computational costs of various implementations of codes and highlight the most efficient ones. Our goal is to provide system designers with concrete information to help them choose the best parameters and design for regenerating codes.

The availability of end devices of peer-to-peer storage and backup systems has been shown critical for usability and for system reliability in practice. This has led to the adoption of hybrid architectures composed of both peers and servers. Such architectures mask the instability of peers thus approaching the performances of client-server systems while providing scalability at a low cost. In this paper, we advocate the replacement of such servers by a cloud of residential gateways, as they are already present in users' homes, thus pushing the required stable components at the edge of the network. In our gateway-assisted system, gateways act as buffers between peers, compensating for their intrinsic instability. This enables to offload backup tasks quickly from the user's machine to the gateway, while significantly lowering the retrieval time of backed up data. We evaluate our proposal using real world traces including existing traces from Skype and Jabber as well as a trace of residential gateways for availability, and a residential broadband trace for bandwidth. Results show that the time required to backup data in the network is comparable to a server-assisted approach, while substantially improving the time to restore data, which drops from a few days to a few hours. As gateways are becoming increasingly powerful in order to enable new services, we expect such a proposal to be leveraged on a short term basis.

Network coding has been successfully applied in large-scale content dissemination systems. While network codes provide optimal throughput, its current forms suffer from a high decoding complexity. This is an issue when applied to systems composed of nodes with low processing capabilities, such as sensor networks. In this paper, we propose a novel network coding approach based on LT codes, initially introduced in the context of erasure coding. Our coding scheme, called LTNC, fully benefits from the low complexity of belief propagation decoding. Yet, such decoding schemes are extremely sensitive to statistical properties of the code. Maintaining such properties in a fully decentralized way with only a subset of encoded data is challenging. This is precisely what the recoding algorithms of LTNC achieve. We evaluate LTNC against random linear network codes in an epidemic content-dissemination application. Results show that LTNC increases communication overhead (20\%) and convergence time (30\%) but greatly reduces the decoding complexity (99%) when compared to random linear network codes. In addition, LTNC consistently outperforms dissemination protocols without codes, thus preserving the benefit of coding.

We propose Phosphite, a mechanism to preserve out of order download in peer to peer video-on-demand applications, in the presence of selfish peers. In such applications, peers have a natural trend to download blocks in order to start watching videos as soon as possible. Without specific mechanism to enforce a fair amount of out of order download, the last blocks of the video tend to be lost due to peers leaving soon after having downloaded the last blocks thus forcing peers to rely on the central server for re-introducing those lost blocks. This issue can be solved if peers dedicate a portion of their bandwidth for out of order downloads. Yet, this heavily relies on the goodwill of peers to collaborate. Phosphite is a simple yet efficient approach ensuring that all peers dedicate a part of their bandwidth to out of order download. Phosphite relies on a computational challenge where peers are provided with a combination of the requested blocks and other blocks. This forces peers to download out of order blocks to be able to decode the requested blocks. We evaluate Phosphite and show that it successfully prevents the system from losing blocks, even in the presence of selfish peers, thus offering an appealing alternative to state of the art approaches. With Phosphite, the last blocks remain available (with a probability higher than 0.98), while such result cannot be guaranteed (with a probability lower than 0.5) without enforcement mechanism. Phosphite ensures that a peer to peer download is almost always possible, even in the presence of selfish peers.

This paper introduces the application of an unconventional approach to Grid programming. The proposed programming model is based on the chemical metaphor for expressing coordination of large grain computations. A chemical program can be seen as a set of chemical reactions, representing computations, that transform a set of floating molecules, representing data, within a chemical solution until an inert solution is reached. This model is intrinsically parallel and possesses nice autonomic properties, which are expected for programming Grids. We illustrate this novel programming model with a simple ray-tracing application and describe an implementation in the context of Desktop Grids.