When key-value (KV) stores use SSDs for storing a large number of items, oftentimes they also require large in-memory data structures including indices and caches to be traversed to reduce IOs. This paper considers offloading most of such data structures from the costly host DRAM to secondary memory whose latency is in the microsecond range, an order of magnitude longer than those of DIMM-mounted persistent memory and currently available CXL memory devices. While emerging microsecond-latency memory, such as one based on flash memory, is likely to cost much less than DRAM, it can significantly slow down pointer-chasing on those in-memory data structures of SSD-based KV stores if naively employed, although its impact has not been well studied. This paper analyzes and evaluates the impact of microsecond-level memory latency on the throughput of SSD-based KV operations. Our analysis finds that a well-known latency-hiding technique of software prefetching for long-latency memory from user-level threads is effective for SSD-based KV stores. The novelty of our analysis lies in modeling how the interplay between prefetching and IO affects performance, from which we derive an equation that well explains the throughput degradation due to long memory latency. The model tells us that the presence of IO in KV operations significantly enhances their tolerance to memory latency, and the throughput degradation is expected to be small even if the memory latency extends to a few microseconds, leading to a finding that SSD-based KV stores can be made latency-tolerant without devising new techniques for microsecond-latency memory. To confirm this through experiments, we design a microbenchmark as well as modify existing SSD-based KV stores so that they issue prefetches for long-latency memory from user-level threads, and run them while placing most of in-memory data structures on FPGA-based memory with adjustable microsecond latency. The results demonstrate that their KV operation throughputs for varying memory latency can be well explained by our model, and the modified KV stores achieve near-DRAM throughputs for up to a memory latency of around 5 microseconds. This suggests the possibility that SSD-based KV stores involving latency-sensitive in-memory data traversal can use microsecond-latency memory as a cost-effective alternative to the host DRAM.

In voltage imaging, where the membrane potentials of individual neurons are recorded at from hundreds to thousand frames per second using fluorescence microscopy, data processing presents a challenge. Even a fraction of a minute of recording with a limited image size yields gigabytes of video data consisting of tens of thousands of frames, which can be time-consuming to process. Moreover, millisecond-level short exposures lead to noisy video frames, obscuring neuron footprints especially in deep-brain samples where noisy signals are buried in background fluorescence. To address this challenge, we propose a fast neuron segmentation method able to detect multiple, potentially overlapping, spiking neurons from noisy video frames, and implement a data processing pipeline incorporating the proposed segmentation method along with GPU-accelerated motion correction. By testing on existing datasets as well as on new datasets we introduce, we show that our pipeline extracts neuron footprints that agree well with human annotation even from cluttered datasets, and demonstrate real-time processing of voltage imaging data on a single desktop computer for the first time.

Locality sensitive hashing (LSH) is one of the widely-used approaches to approximate nearest neighbor search (ANNS) in high-dimensional spaces. The first work on LSH for the Euclidean distance, E2LSH, showed how ANNS can be solved efficiently at a sublinear query time in the database size with theoretically-guaranteed accuracy, although it required a large hash index size. Since then, several LSH variants having much smaller index sizes have been proposed. Their query time is linear or superlinear, but they have been shown to run effectively faster because they require fewer I/Os when the index is stored on hard disk drives and because they also permit in-memory execution with modern DRAM capacity. In this paper, we show that E2LSH is regaining the advantage in query speed with the advent of modern flash storage devices such as solid-state drives (SSDs). We evaluate E2LSH on a modern single-node computing environment and analyze its computational cost and I/O cost, from which we derive storage performance requirements for its external memory execution. Our analysis indicates that E2LSH on a single consumer-grade SSD can run faster than the state-of-the-art small-index methods executed in-memory. It also indicates that E2LSH with emerging high-performance storage devices and interfaces can approach in-memory E2LSH speeds. We implement a simple adaptation of E2LSH to external memory, E2LSH-on-Storage (E2LSHoS), and evaluate it for practical large datasets of up to one billion objects using different combinations of modern storage devices and interfaces. We demonstrate that our E2LSHoS implementation runs much faster than small-index methods and can approach in-memory E2LSH speeds, and also that its query time scales sublinearly with the database size beyond the index size limit of in-memory E2LSH.

A wireless ad hoc network (WANET) is an effective approach to disseminating digital content without the need for infrastructure networks. It is not only useful in the absence of commodity connections such as cellular networks, but also useful for avoiding overloading those connections in crowded scenarios, an example of which is delivering movie clips throughout spectators in a stadium. However, experiments of WANET have been oftentimes conducted using only up to 1,000 nodes in a simulator or dozens of real devices, both typically scattered across a wide area at a density of around 10-4node/m2. This paper focuses on the problem of disseminating common content to all the devices in the same area via 802.11-based WANET, and presents a pair of testbeds, one based on real devices and the other a simulator, both capable of high-density and large-scale experiments with roughly matched performance. We have found naive implementation of content dissemination protocols alone not to work in high density, and we identify necessary adjustment of wireless parameters to allow for experiments even with an extreme density of 20 nodes/m2. We show that 2.5 MB of data can be delivered to 100 real devices and to 10,000 simulated devices in a few minutes on our testbeds, demonstrating the feasibility of orders of magnitude larger-scale experiments.

Sharing digital content with others is now an important part of human social activities. Despite the increasing need to share, most sharing operations are not simple. Many applications are not interoperable with others, require an Internet connection, or require cumbersome configuration and coordination efforts. Our idea is to simplify digital content sharing on mobile devices by providing support for self-organizing heterogeneous networks and pervasive storage. That is, mobile devices can spontaneously connect to each other over a mixture of different available networks (e.g., 3G/4G, WiFi, Bluetooth, etc.) without requiring an explicit user action of network selection or mandatory Internet access. Moreover, indirect communication can be further augmented by pervasive storage. Mobile devices can store shared content on it, which can later be automatically downloaded by other devices in proximity, thus allowing location-based sharing with minimal coordination even when devices are not in the same location at the same time. This paper shows how these technologies can be incorporated into mobile content-sharing middleware to simplify sharing operations among mobile devices without any modification to commercially available devices or applications. In particular, (i) we provide an implementation of our approach as extension modules for existing content-sharing middleware, (ii) we present two example applications built on top of it, and (iii) we demonstrate our approach through experiments in representative situations.

ShAir is a middleware infrastructure that allows mobile applications to share resources of their devices (e.g., data, storage, connectivity, computation) in a transparent way. The goals of ShAir are: (i) abstracting the creation and maintenance of opportunistic delay-tolerant peer-to-peer networks; (ii) being decoupled from the actual hardware and network platform; (iii) extensibility in terms of supported hardware, protocols, and on the type of resources that can be shared; (iv) being capable of self-adapting at run-time; (v) enabling the development of applications that are easier to design, test, and simulate. In this paper we discuss the design, extensibility, and maintainability of the ShAir middleware, and how to use it as a platform for collaborative resource-sharing applications. Finally we show our experience in designing and testing a file-sharing application.

Recently, several camera designs have been proposed for either making defocus blur invariant to scene depth or making motion blur invariant to object motion. The benefit of such invariant capture is that no depth or motion estimation is required to remove the resultant spatially uniform blur. So far, the techniques have been studied separately for defocus and motion blur, and object motion has been assumed 1D (e.g., horizontal). This article explores a more general capture method that makes both defocus blur and motion blur nearly invariant to scene depth and in-plane 2D object motion. We formulate the problem as capturing a time-varying light field through a time-varying light field modulator at the lens aperture, and perform 5D (4D light field + 1D time) analysis of all the existing computational cameras for defocus/motion-only deblurring and their hybrids. This leads to a surprising conclusion that focus sweep, previously known as a depth-invariant capture method that moves the plane of focus through a range of scene depth during exposure, is near-optimal both in terms of depth and 2D motion invariance and in terms of high-frequency preservation for certain combinations of depth and motion ranges. Using our prototype camera, we demonstrate joint defocus and motion deblurring for moving scenes with depth variation.

Light field photography has gained a significant research interest in the last two decades; today, commercial light field cameras are widely available. Nevertheless, most existing acquisition approaches either multiplex a low-resolution light field into a single 2D sensor image or require multiple photographs to be taken for acquiring a high-resolution light field. We propose a compressive light field camera architecture that allows for higher-resolution light fields to be recovered than previously possible from a single image. The proposed architecture comprises three key components: light field atoms as a sparse representation of natural light fields, an optical design that allows for capturing optimized 2D light field projections, and robust sparse reconstruction methods to recover a 4D light field from a single coded 2D projection. In addition, we demonstrate a variety of other applications for light field atoms and sparse coding, including 4D light field compression and denoising.

ABSTRACT String‐like objects in our daily lives, for example shoelaces, threads, rubber cords, plastic fiber and spaghetti, have a wide variety of materials. Such string‐like objects also exhibit interesting behaviors such as twisting, tearing (by stretching or twisting), and bouncing back when pulled and released. In this paper, we present a method that enables these behaviors and simulates such materials in traditional string simulation methods that explicitly represent a string by particles and segments. Specifically, we offer the following three contributions. First, we introduce a method for handling twisting effects with both uniform and non‐uniform torsional rigidities. Second, we propose a method for estimating the tension acting on inextensible strings in order to reproduce tearing and flicking (bouncing back), whereas the tension for anextensibleobject can be computed via stretched length. The length of aninextensibleobject is maintained constant in general, and thus, we need a novel approach. Third, we introduce an optimized grid‐based collision detection for accelerating the computation. We demonstrate that our method can produce visually plausible animations of string‐like objects with various material properties, and it is a fast framework for interactive applications such as games. Copyright © 2012 John Wiley & Sons, Ltd.

Abstract Image blur caused by object motion attenuates high frequency content of images, making post‐capture deblurring an ill‐posed problem. The recoverable frequency band quickly becomes narrower for faster object motion as high frequencies are severely attenuated and virtually lost. This paper proposes to translate a camera sensor circularly about the optical axis during exposure, so that high frequencies can be preserved for a wide range of in‐plane linear object motion in any direction within some predetermined speed. That is, although no object may be photographed sharply at capture time, differently moving objects captured in a single image can be deconvolved with similar quality. In addition, circular sensor motion is shown to facilitate blur estimation thanks to distinct frequency zero patterns of the resulting motion blur point‐spread functions. An analysis of the frequency characteristics of circular sensor motion in relation to linear object motion is presented, along with deconvolution results for photographs captured with a prototype camera.

In traditional image composition methods for cutting out a source object from a source image and pasting it onto a target image, users have to segment a foreground object in a target image when they want to partially hide a source object behind it. While recent image editing tools greatly facilitate segmentation operations, it can be tedious to segment each object if users try to place a source object in various positions in a target image before obtaining a satisfying composition. We propose a method which allows users to drag a source object and slip it behind a target object as shown in Fig. 1, so that users can move a source object around without manually segmenting each part of a target image.

Abstract Woven cloth can commonly be seen in daily life and also in animation. Unless prevented in some way, woven cloth usually frays at the edges. However, in computer graphics, woven cloth is typically modeled as a continuum sheet, which is not suitable for representing frays. This paper proposes a model that allows yarn movement and slippage during cloth tearing. Drawing upon techniques from textile and mechanical engineering fields, we model cloth as woven yarn crossings where each yarn can be independently torn when the strain limit is reached. To make the model practical for graphics applications, we simulate only tearing part of cloth with a yarn‐level model using a simple constrained mass‐spring system for computational efficiency. We designed conditions for switching from a standard continuum sheet model to our yarn‐level model, so that frays can be initiated and propagated along the torn lines. Results show that our method can achieve plausible tearing cloth animation with frayed edges.

This paper presents a method for automatically extracting a scene depth map and the alpha matte of a foreground object by capturing a scene through RGB color filters placed in the camera lens aperture. By dividing the aperture into three regions through which only light in one of the RGB color bands can pass, we can acquir three shifted views of a scene in the RGB planes of an image in a single exposure. In other words, a captured image has depth-dependent color misalignment. We develop a color alignment measure to estimate disparities between the RGB planes for depth reconstruction. We also exploit color misalignment cues in our matting algorithm in order to disambiguate between the foreground and background regions even where their colors are similar. Based on the extracted depth and matte, the color misalignment in the captured image can be canceled, and various image editing operations can be applied to the reconstructed image, including novel view synthesis, postexposure refocusing, and composition over different backgrounds.

This paper explores an image processing method for synthesizing refocused images from a single input photograph containing some defocus blur. First, we restore a sharp image by estimating and removing spatially-variant defocus blur in an input photograph. To do this, we propose a local blur estimation method able to handle abrupt blur changes at depth discontinuities in a scene, and we also present an efficient blur removal method that significantly speeds up the existing deconvolution algorithm. Once a sharp image is restored, refocused images can be interactively created by adding different defocus blur to it based on the estimated blur, so that users can intuitively change focus and depth-of-field of the input photograph. Although information available from a single photograph is highly insufficient for fully correct refocusing, the results show that visually plausible refocused images can be obtained.

Abstract This paper presents a practical approach to the animation of hair at an interactive frame rate. In our approach,we model the hair as a set of particles that serve as sampling points for the volume of the hair, which covers thewhole region where hair is present. The dynamics of the hair, including hair‐hair interactions, is simulated usingthe interacting particles. The novelty of this approach is that, as opposed to the traditional way of modeling hair,we release the particles from tight structures that are usually used to represent hair strands or clusters. Therefore,by making the connections between the particles loose while maintaining their overall stiffness, the hair can bedynamically split and merged during lateral motion without losing its lengthwise coherence. Categories and Subject Descriptions (according to ACM CCS): I.3.7 [Computer Graphics]: Three‐DimensionalGraphics and Realism, I.3.3 [Computer Graphics]: Picture/Image Generation

Realism of rendered human skin can be strongly enhanced by taking into account skin wrinkles. However, modeling wrinkles is a difficult task, and considerable time and effort are necessary to achieve satisfactory results. This paper presents a simple method to easily model wrinkles on human skin, taking into account the properties of real wrinkles. Wrinkles are specified using intuitive parameters, and are generated over a triangle mesh representing a body part, such as a hand or a face. Wrinkled skin surfaces are rendered at an interactive frame rate, dynamically modulating wrinkle amplitude according to skin surface deformation while animating the body part. We demonstrate the ability of our method to model realistic wrinkle shapes by comparing them with real wrinkles.