Section:
New Results
Compact and distributed data structures
Query optimization in databases
Participants :
Nicolas Hanusse, Sofian Maabout.
Datacubes are data structures designed to query optimization in databases. In [42] we provide some algorithmic solutions in a user centric setting: the request time is guaranteed and the amount of memory space is minimized.
Parallel computations of Borders
Participants :
Nicolas Hanusse, Sofian Maabout.
Borders are fundamental building blocks in data mining. They are used to find frequent patterns, dependencies between attributes, ... In[43] we provide an algorithm that computes borders with a speedup of (under reasonable hypothesis) for cores.
Node-disjoint multipath spanners and their relationship with fault-tolerant spanners
Participants :
Cyril Gavoille, Quentin Godfroy.
Motivated by multipath routing, we introduce a multi-connected variant
of spanners. For that purpose we introduce
in [40] the -multipath cost between
two nodes and as the minimum weight of a collection of
internally vertex-disjoint paths between and . Given a
weighted graph , a subgraph is a -multipath -spanner if
for all , the -multipath cost between and in is at
most times the -multipath cost in . The factor is called
the stretch.
Building upon recent results on fault-tolerant spanners, we show how
to build -multipath spanners of constant stretch and of
edges, for fixed
parameters and , being the number of nodes of the
graph. Such spanners can be constructed by a distributed algorithm
running in rounds.
Additionally, we give an improved construction for the case
. Our spanner has edges and the -multipath
cost in between any two node is at most twice the corresponding
one in plus , being the maximum edge weight.
On approximate distance labels and routing schemes with affine stretch
Participant :
Cyril Gavoille.
For every integral parameter , given an unweighted graph ,
we construct in polynomial time in [25] ,
for each vertex , a distance label of size
. For any , given we can
return in time an affine approximation on the
distance between and in such that . Hence we say that our distance label
scheme has affine stretch of . For our construction
is comparable to the size, affine stretch of the
distance oracle of Pǎtraşcu and Roditty (FOCS '10), it incurs
a storage overhead while providing the benefits of a
distance label.
For any , given a restriction of on the total
size of the data structure, our construction provides distance labels
with affine stretch of which is better than the stretch
scheme of Thorup and Zwick (J. ACM '05).
Our second contribution is a compact routing scheme with
poly-logarithmic addresses that provides affine stretch guarantees.
With -bit routing tables we obtain affine stretch
of , for any .
Given a restriction of on the table size, our routing
scheme provides affine stretch which is better than the stretch
routing scheme of Thorup and Zwick (SPAA '01).
Sparse spanners vs. compact routing
Participant :
Cyril Gavoille.
Routing with multiplicative stretch 3 (which means that the
path used by the routing scheme can be up to three times longer than a
shortest path) can be done with routing tables of
bits(Tilde-big- notation is similar
to big- notation up to factors poly-logarithmic in .) per
node. The space lower bound is due to the existence of dense graphs
with large girth. Dense graphs can be sparsified to subgraphs, called
spanners, with various stretch guarantees. There are spanners
with additive stretch guarantees (some even have constant
additive stretch) but only very few additive routing schemes are
known.
In [39] , we give reasons why routing in
unweighted graphs with additive stretch is difficult in the
form of space lower bounds for general graphs and for planar
graphs. We prove that any routing scheme using routing tables of size
bits per node and addresses of poly-logarithmic length has
additive stretch for general graphs, and
for planar graphs. Routing with tables of
size thus requires a polynomial additive stretch of
, whereas spanners with average degree
and constant additive stretch exist for all graphs. Spanners,
however sparse they are, do not tell us how to route. These bounds
provide the first separation of sparse spanner problems and compact
routing problems.
On the positive side, we give an almost tight upper bound: we present
the first non-trivial compact routing scheme with -bit
addresses, additive stretch , and table size
bits for planar graphs. Actually, our scheme applies to
general graphs, and the above bound of on the stretch and
the routing table size holds for all graphs of linear local
tree-width, a class of graphs including bounded-genus graphs and
apex-minor-free graphs.