-----------------------------------------------------------------------
                   B O S T O N   U N I V E R S I T Y
                      Computer Science Department
                          C O L L O Q U I U M
                     Wednesday, Oct 3, 3:00 PM
                       (Coffee served at 2:45PM)
                         Seminar Room / MCS 135

                   CS  Faculty Research Overviews

                         John Byers CS BU
       "On the Marginal Utility of Network Topology Measurements"

                       George Kollios CS BU
              "Discovering Similar Trajectories"

-------------------------------------------------------------------------  

"On the Marginal Utility of Network Topology Measurements"
Abstract

When conducting measurements or deploying measurement boxes in the
Internet, a very simple and widely applied rule of thumb is "more is
better".  In an effort to provide a more refined understanding, we seek to
answer the question "How much better?".  We focus on the specific problem
of discovering the underlying topology of the Internet using
point-to-point  traceroute measurements.  Using datasets consisting of
tens of thousands of such measurements from a set of distributed sources,
we study the marginal utility of adding additional sources, adding
additional (common)  destinations and we characterize the topology
observable from a collection of distributed vantage points.  Our
preliminary findings demonstrate the  substantial quantitative difference
in conducting measurements to O($k$) common destinations from O(1) sources
as opposed to (say) conducting measurements between all pairs of a set of
O($\sqrt{k}$) hosts.  I will touch on empirical, theoretical and
information-theoretic aspects of the work in the talk.

"Discovering Similar Trajectories"
Abstract

We investigate techniques for analysis and retrieval of object
trajectories in a two or three dimensional space. Such kind of
data usually contain a great amount of noise, that makes all
previously used metrics fail. Therefore, here we formalize
non-metric similarity functions based on the Longest Common
Subsequence (LCSS), which are very robust to noise and
furthermore provide an intuitive notion of similarity between
trajectories by giving more weight to the similar portions of the
sequences. Stretching of sequences in time is allowed, as well as
global translating of the sequences in space. Efficient
approximate algorithms that compute these similarity measures are
also provided. We compare these new methods to the widely used
Euclidean and Time Warping distance functions (for real and
synthetic data) and show the superiority of our approach,
especially under the strong presence of noise. We prove a weaker
version of the triangle inequality and employ it in an indexing
structure to answer nearest neighbor queries.


-------------------------------------------------------------------------  
For colloquium info, including directions, see http://cs-www.bu.edu/colloquium
-------------------------------------------------------------------------