```
The Caesarea Rothschild Institute at the University of Haifa invites
you to a

Special CRI Summer Seminar

Date:  Monday 15 July 2013  at 12:00 noon

Speaker:  Prof. Hanan Samet (University of Maryland)

Title:    INDEXING METHODS FOR GAME DATABASES
TUNED FOR REDUCING MOTION UPDATE TIMES

Place: Room 665 Education Building, University of Haifa

This seminar is part of the ACM DISTINGUISHED SPEAKER PROGRAM

Abstract

Moving object databases arise in numerous applications such as
traffic monitoring, crowd tracking, and games.  They all require keeping
track of objects that move and thus the database of objects must be
constantly updated.  The cover fieldtree (more commonly known as the loose
quadtree and the loose octree, depending on the dimension of the underlying
space) is designed to overcome the drawback of spatial data structures that
associate objects with their minimum enclosing quadtree (octree) cells which
is that the size of these cells depends more on the position of the objects
and less on their size.  In fact, the size of these
cells may be as large as the entire space from which the objects are drawn.
The loose quadtree (octree) overcomes this drawback by expanding
the size of the space that is spanned by each quadtree (octree) cell c of
width w by a cell expansion factor p (p>0) so that the expanded cell is of
width \$(1+p)*w and an object is associated with its minimum enclosing
expanded quadtree (octree) cell. It is shown that for an object o with
minimum bounding hypercube box b of radius r (i.e., half the length of a
side of the hypercube), the maximum possible width w of the minimum
enclosing expanded quadtree cell c is just a function of r and p, and is
independent of the position of o.  Normalizing \$w\$ via division by \$2r\$
enables calculating the range of possible expanded quadtree cell sizes as a
function of p.  For p>= 0.5 the range consists of just two values and
usually just one value for p>=1.  This makes updating very simple and fast
as for p >= 0.5, there are at most two possible new cells associated with
the moved object and thus the update can be done in O(1) time.
Experiments with random data showed that the update time to
support motion in such an environment is minimized when p is infinitesimally
less than 1, with as much as a one order of magnitude increase in the number
of updates that can be handled vis-a-vis the p=0 case in a given unit of
time.  Similar results for updates were obtained for an N-body simulation
where improved query performance and scalability were also observed.

A video titled ``Crates and Barrels'' will accompany the lecture,
which is an N-body simulation of 14,000 objects.  The video as well as a
JAVA applet that illustrates the behavior of the loose quadtree are both
available from  <http://www.cs.umd.edu/~hjs/loosequad/> This talk is based on
the author's joint paper with Jagan Sankaranarayanan and Michael Auerbach
(Proc. of the ACM SIGMOD Conference, pp. 169--180, New York, June 2013).

Biography of the Speaker

Hanan Samet  <(http://www.cs.umd.edu/~hjs/)> is a Distinguished University
Professor of Computer Science at the University of Maryland, College Park
and is a member of the Institute for Computer Studies and of the Computer
Vision Laboratory at the Center for Automation Research where he leads a
number of research projects on the use of hierarchical data structures for
database applications involving spatial data. He is the author of the recent
book "Foundations of Multidimensional and Metric Data Structures" and of the
first two books on spatial data structures titled "Design and Analysis of
Spatial Data Structures" and "Applications of Spatial Data Structures:
Computer Graphics, Image Processing and GIS". He is the Founding
Editor-in-Chief of the ACM Transactions on Spatial Algorithms and System
(TSAS), the founding chair of ACM SIGSPATIAL, a recipient of the 2009 UCGIS
Research Award, 2011 ACM Paris Kanellakis Theory and Practice Award, the
2010 CMPS Board of Visitors Award at the University of Maryland, a Fellow of
the ACM, IEEE, AAAS, and IAPR (International Association for Pattern
Recognition), and an ACM Distinguished Speaker.

---------------------------------------------------------
Technion Math Net-2 (TECHMATH2)
Editor: Michael Cwikel   <techm@math.technion.ac.il>
Announcement from:   Martin Charles Golumbic   <golumbic@cs.haifa.ac.il>
```