[Dmbu-l] Practice talks for WWW and SIGMOD
cmav at bu.edu
Wed May 6 13:31:31 EDT 2015
On Friday, May 8th, at 11:00 in MCS148, I will be practicing my two talks.
I would be really grateful if you could come and share your
comments/feedback. Both of these talks need to be shorter than 30', so we
won't go past 12:00. The abstracts follow below.
Thanks a lot,
Spanning edge centrality: Large-scale computation and applications
The spanning centrality of an edge in an undirected graph G is the
fraction of the spanning trees of G that contain e. Despite its appealing
definition and apparent value in certain applications in computational
biology, spanning centrality hasn’t so far received a wider attention as a
measure of edge centrality, mainly because of the perceived complexity of
computing it. However, spanning centrality can in fact be approximated
arbitrary well by very efficient near-linear time algorithms due to
Spielman and Srivastava, combined with progress in linear system solvers.
In this talk, we will bring theory into practice, by describing algorithms
that enable the fast computation of spanning centrality in graphs with
millions of nodes. We will also demonstrate experimentally that spanning
centrality is in fact a useful tool for the analysis of large networks.
Specifically, we will show that spanning centrality is more effective in
identifying edges whose removal causes a higher disruption in an
information propagation procedure, while being very resilient to noise.
Modular order-preserving encryption, revisited
Order-preserving encryption (OPE) schemes, whose ciphertexts preserve the
natural ordering of the plaintexts, allow efficient range query processing
over outsourced encrypted databases without giving the server access to the
decryption key. Such schemes have recently received increased interest in
both the database and the cryptographic communities. In particular,
modular order-preserving encryption (MOPE), due to Boldyreva et. al., is a
promising extension that increases the security of the basic OPE by
introducing a secret modular offset to each data value prior to encrypting
it. However, executing range queries via MOPE in a naive way allows the
adversary to learn this offset, negating any potential security gains of
In our work, we systematically address this vulnerability and show that
MOPE can be used to build a practical system for executing range queries on
encrypted data while providing a significant security improvement over the
basic OPE. We introduce two new query execution algorithms for MOPE and
show that our algorithms can be extended to the case where the query
distribution is adaptively learned online. Finally, we design a system
prototype that integrates our schemes on top of an existing database system
its performance under a number of different database and query
distributions, using both synthetic and real datasets.
-------------- next part --------------
An HTML attachment was scrubbed...
More information about the Dmbu-l