*** NOTE the special time and place of this colloquium event! ***
Friday
October 8
3:00 - 4:00 PM *** NOTE: different time ***
Kelley 1003 *** NOTE: different place ***
Steph Durocher
Assistant Professor
Department of Computer Science
University of Manitoba
Linear-Space Static Data Structures for Range Mode Query in Arrays
A mode of a multiset S is an element x in S of maximum multiplicity; that is, x
occurs at least as frequently as any other element in S. Given a list A[1 : n]
of n items, we consider the problem of constructing a data structure that
efficiently answers range mode queries on A. Each query consists of an input
pair of indices (i, j) for which a mode of A[i : j] must be returned. We
present an O(n)-space static data structure that supports range mode queries in
O(min{sqrt(n), k, |j-i|+1}) time in the worst case, where k denotes the number
of distinct elements in A. This is the first linear-space data structure to
guarantee O(sqrt(n)) query time. Finally, we examine generalizing our data
structures to higher dimensions. This work is joint with Jason Morrison.
Biography
Steph Durocher is an assistant professor in the Department of Computer Science
at the University of Manitoba. His research interests are in computational
geometry, with a specialization in geometric problems in mobile computing and
wireless networks.
_______________________________________________
Colloquium mailing list
[email protected]
https://secure.engr.oregonstate.edu/mailman/listinfo/colloquium
