CNR Author
operator:
and / or
Typology
operator:
and / or
Language
operator:
and / or
Date
operator:
and / or
Rights
operator:
and / or
2013
Conference article
Open Access
Design of practical succinct data structures for large data collections
Grossi R., Ottaviano G.
We describe a set of basic succinct data structures which have been implemented as part of the Succinct library, and applications on top of the library: an index to speed-up the access to collections of semi-structured data, a compressed string dictionary, and a compressed dictionary for scored strings which supports top-k prefix matching.Source: SEA 2013 - Experimental Algorithms. 12th International Symposium, pp. 5–17, Rome, Italy, 5-7 June 2013
DOI: 10.1007/978-3-642-38527-8_3
Metrics:
Grossi R., Ottaviano G.
We describe a set of basic succinct data structures which have been implemented as part of the Succinct library, and applications on top of the library: an index to speed-up the access to collections of semi-structured data, a compressed string dictionary, and a compressed dictionary for scored strings which supports top-k prefix matching.Source: SEA 2013 - Experimental Algorithms. 12th International Symposium, pp. 5–17, Rome, Italy, 5-7 June 2013
DOI: 10.1007/978-3-642-38527-8_3
Metrics:
See at:
link.springer.com 
| www.di.unipi.it | doi.org 
| CNR ExploRA
2013
Conference article
Open Access
Compressible motion fields
Ottaviano G., Kohli P.
Traditional video compression methods obtain a compact representation for image frames by computing coarse motion fields defined on patches of pixels called blocks, in order to compensate for the motion in the scene across frames. This piecewise constant approximation makes the motion field efficiently encodable, but it introduces block artifacts in the warped image frame. In this paper, we address the problem of estimating dense motion fields that, while accurately predicting one frame from a given reference frame by warping it with the field, are also compressible. We introduce a representation for motion fields based on wavelet bases, and approximate the compressibility of their coefficients with a piecewise smooth surrogate function that yields an objective function similar to classical optical flow formulations. We then show how to quantize and encode such coefficients with adaptive precision. We demonstrate the effectiveness of our approach by com- paring its performance with a state-of-the-art wavelet video encoder. Experimental results on a number of standard flow and video datasets reveal that our method significantly out- performs both block-based and optical-flow-based motion compensation algorithms.Source: CVPR 2013 - 2013 IEEE Conference on Computer Vision and Pattern Recognition, pp. 2251–2258, Portland, USA, 23-28 June 2013
DOI: 10.1109/cvpr.2013.292
Metrics:
Ottaviano G., Kohli P.
Traditional video compression methods obtain a compact representation for image frames by computing coarse motion fields defined on patches of pixels called blocks, in order to compensate for the motion in the scene across frames. This piecewise constant approximation makes the motion field efficiently encodable, but it introduces block artifacts in the warped image frame. In this paper, we address the problem of estimating dense motion fields that, while accurately predicting one frame from a given reference frame by warping it with the field, are also compressible. We introduce a representation for motion fields based on wavelet bases, and approximate the compressibility of their coefficients with a piecewise smooth surrogate function that yields an objective function similar to classical optical flow formulations. We then show how to quantize and encode such coefficients with adaptive precision. We demonstrate the effectiveness of our approach by com- paring its performance with a state-of-the-art wavelet video encoder. Experimental results on a number of standard flow and video datasets reveal that our method significantly out- performs both block-based and optical-flow-based motion compensation algorithms.Source: CVPR 2013 - 2013 IEEE Conference on Computer Vision and Pattern Recognition, pp. 2251–2258, Portland, USA, 23-28 June 2013
DOI: 10.1109/cvpr.2013.292
Metrics:
See at:
doi.org | CNR ExploRA
2013
Conference article
Open Access
Space-efficient data structures for top-k completion
Hsu P., Ottaviano G.
Virtually every modern search application, either desktop, web, or mobile, features some kind of query auto-completion. In its basic form, the problem consists in retrieving from a string set a small number of completions, i.e. strings be- ginning with a given prefix, that have the highest scores according to some static ranking. In this paper, we focus on the case where the string set is so large that compres- sion is needed to fit the data structure in memory. This is a compelling case for web search engines and social networks, where it is necessary to index hundreds of millions of distinct queries to guarantee a reasonable coverage; and for mobile devices, where the amount of memory is limited. We present three different trie-based data structures to address this problem, each one with different space/time/ complexity trade-offs. Experiments on large-scale datasets show that it is possible to compress the string sets, including the scores, down to spaces competitive with the gzip'ed data, while supporting efficient retrieval of completions at about a microsecond per completion.Source: WWW 2013 - 22st International Conference on World Wide Web, pp. 583–594, Rio De Janeiro, Brazil, 13-17 May 2013
Hsu P., Ottaviano G.
Virtually every modern search application, either desktop, web, or mobile, features some kind of query auto-completion. In its basic form, the problem consists in retrieving from a string set a small number of completions, i.e. strings be- ginning with a given prefix, that have the highest scores according to some static ranking. In this paper, we focus on the case where the string set is so large that compres- sion is needed to fit the data structure in memory. This is a compelling case for web search engines and social networks, where it is necessary to index hundreds of millions of distinct queries to guarantee a reasonable coverage; and for mobile devices, where the amount of memory is limited. We present three different trie-based data structures to address this problem, each one with different space/time/ complexity trade-offs. Experiments on large-scale datasets show that it is possible to compress the string sets, including the scores, down to spaces competitive with the gzip'ed data, while supporting efficient retrieval of completions at about a microsecond per completion.Source: WWW 2013 - 22st International Conference on World Wide Web, pp. 583–594, Rio De Janeiro, Brazil, 13-17 May 2013
See at:
dl.acm.org | CNR ExploRA