Theory Seminar: Bryan Wilkinson, Aarhus University - Range Searching in Query-Dependent Categories
Info about event
Time
Location
Nygaard 395, (5335) Åbogade 34, 8200 Aarhus N
Organizer
Abstract:
We consider a variant of range searching in which points are coloured. A query, whose input consists of an axis-aligned rectangle as well as a subset of colours, must report all points that lie within the query range and match one of the query colours. Such queries are useful, for example, in searching databases with both numerical and categorical attributes. While previous work has solved the 1-D case in the pointer machine model, we make steps towards solving the 2-D case. We give an optimal data structure for 2-sided (dominance) queries and a data structure for 3-sided queries that is a mere log* factor from optimal.
Joint work with: Peyman Afshani
Host: Gerth Stølting Brodal