Spatial Indexes

PhD Qualifying Examination


Title: "Spatial Indexes"

by

Mr. Moin Hussain MOTI


Abstract:

Spatial databases manage large datasets of objects with location
information (e.g., GPS positions of smartphone users, vessel, and aircraft
coordinates). Due to the sheer volume of data, and the absence of any
natural ordering in multidimensional space, linear search for objects
satisfying some spatial predicate (e.g., mobile users in the city center,
the closest airplanes to the airport) is impractical. This motivates the
need for spatial indexes that can efficiently filter and retrieve
information. Spatial indexes are usually trees that either partition the
space, or the data objects. The deepest tree level comprises leaf nodes,
whereas the rest, including the root, consist of branches. Each node is
associated with a spatial extent (e.g., a minimum bounding rectangle in 2D
space) which covers all the nodes and objects in its subtree. Spatial
indexes reside either in memory, or on the disk. This report focuses on
the disk-based indexes, where nodes are stored on the disk, with their
capacity limited by the disk-page size. The ability to fully utilize this
capacity is critical to an index's overall performance. While spatial
indexes are used in a variety of contexts, like moving objects,
spatio-temporal aggregation, and cloud-based partitioning of spatial data,
we focus on the most common spatial data processing tasks, such as the
range, and the k-NN queries. We implemented popular spatial indexes like
the Quad-Trees, the KDB-Trees, various R-Tree packing schemes, the
R*-Tree, and the Waffle, and conducted extensive experimental analysis to
understand how their characteristics contribute to their performances. We
discuss our evaluation in this report.


Date:                   Thursday, 4 May 2023

Time:                   10:00am - 12:00noon

Venue:                  Room 4472
                         Lifts 25/26

Committee Members:      Prof. Dimitris Papadias (Supervisor)
                         Prof. Siu-Wing Cheng (Chairperson)
 			Prof. Raymond Wong
 			Prof. Ke Yi


**** ALL are Welcome ****