Vida Dujmovic
An Affine Invariant $k$-Nearest Neighbor Regression Estimate.
Mon, 05/21/2012 - 15:01 — SomNambulAuthors: Gérard Biau, Luc Devroye, Vida Dujmovic, Adam Krzyzak
Subjects: Statistics
AbstractWe design a data-dependent metric in $\mathbb R^d$ and use it to define the
$k$-nearest neighbors of a given point. Our metric is invariant under all
affine transformations. We show that, with this metric, the standard
$k$-nearest neighbor regression estimate is asymptotically consistent under the
usual conditions on $k$, and minimal requirements on the input data.- 3 comments
- login or register to post comments
An O(loglog n)-Competitive Binary Search Tree with Optimal Worst-Case Access Times.
Tue, 03/02/2010 - 16:02 — SomNambulAuthors: Vida Dujmovic, Prosenjit Bose, Karim Douïeb, Rolf Fagerberg
Subjects: Data Structures and Algorithms
AbstractWe present the zipper tree, an $O(\log \log n)$-competitive online binary
search tree that performs each access in $O(\log n)$ worst-case time. This
shows that for binary search trees, optimal worst-case access time and
near-optimal amortized access time can be guaranteed simultaneously.Odds-On Trees.
Mon, 02/08/2010 - 16:01 — SomNambulAuthors: Luc Devroye, Vida Dujmovic, Pat Morin, Prosenjit Bose, Karim Douieb, James King
Subjects: Computational Geometry
AbstractLet R^d -> A be a query problem over R^d for which there exists a data
structure S that can compute P(q) in O(log n) time for any query point q in
R^d. Let D be a probability measure over R^d representing a distribution of
queries. We describe a data structure called the odds-on tree, of size
O(n^\epsilon) that can be used as a filter that quickly computes P(q) for some
query values q in R^d and relies on S for the remaining queries.Point Location in Disconnected Planar Subdivisions.
Mon, 01/18/2010 - 16:01 — SomNambulAuthors: Luc Devroye, Vida Dujmovic, Pat Morin, Prosenjit Bose, Karim Douieb, James King
Subjects: Computational Geometry
AbstractLet $G$ be a (possibly disconnected) planar subdivision and let $D$ be a
probability measure over $\R^2$. The current paper shows how to preprocess
$(G,D)$ into an O(n) size data structure that can answer planar point location
queries over $G$. The expected query time of this data structure, for a query
point drawn according to $D$, is $O(H+1)$, where $H$ is a lower bound on the
expected query time of any linear decision tree for point location in $G$. This
extends the results of Collette et al (2008, 2009) from connected planar
subdivisions to disconnected planar subdivisions.Memoryless Routing in Convex Subdivisions: Random Walks are Optimal.
Mon, 11/16/2009 - 16:01 — SomNambulAuthors: Luc Devroye, Vida Dujmovic, Pat Morin, Dan Chen
Subjects: Computational Geometry
AbstractA memoryless routing algorithm is one in which the decision about the next
edge on the route to a vertex t for a packet currently located at vertex v is
made based only on the coordinates of v, t, and the neighbourhood, N(v), of v.
The current paper explores the limitations of such algorithms by showing that,
for any (randomized) memoryless routing algorithm A, there exists a convex
subdivision on which A takes Omega(n^2) expected time to route a message
between some pair of vertices.Notes on large angle crossing graphs.
Wed, 08/26/2009 - 14:59 — SomNambulAuthors: Vida Dujmovic, Joachim Gudmundsson, Pat Morin, Thomas Wolle
Subjects: Data Structures and Algorithms
AbstractA graph G is an a-angle crossing (aAC) graph if every pair of crossing edges
in G intersect at an angle of at least a. The concept of right angle crossing
(RAC) graphs (a=Pi/2) was recently introduced by Didimo et. al. It was shown
that any RAC graph with n vertices has at most 4n-10 edges and that there are
infinitely many values of n for which there exists a RAC graph with n vertices
and 4n-10 edges. In this paper, we give upper and lower bounds for the number
of edges in aAC graphs for all 0 < a < Pi/2.
User login
