Structures and access methods

Describe the organization of data in computer storage to facilitate efficient retrieval.

Highlights

• physical file organization affects database performance
• indexes are needed to go beyond the limitations of physical file organization
• non-spatial indexes, like B-trees, are inadequate for storing spatial data
• the key issue in spatial indexes is representing two dimensional data in a one-dimensional index

General structure and access methods

• physical data management
  • block: the atomic unit of data on a disk
  • unordered files
    • insertion is very efficient
    • linear search with time complexity O(n)
  • ordered files
    • slows the insertion of new records
    • support efficient binary search with time complexity of O(logn) on indexed field
• index: is an auxiliary structure specifically designed to speed retrieval of records
  • trade space for speed
  • the concept of an index to a file is similar to the index to a book
  • Spatial index is a special data structure for points and rectangles that allows you to perform queries like all items within this bounding box very efficiently (e.g. hundreds of times faster than looping over all items).
  • B-Trees: a self-balancing search tree
    • balanced = equal length through modification
    • all leaves are at the same level
    • time complexity O(logn)

From one to two dimensions

• spatial Queries
  • point query:retrieve all records with spatial references located at a particular point
  • range query: retrieve all records ith spatial references located within a given range (spatial ranges may be any shape, but are often rectangular)
• the main problem facing multidimensional spatial data structures is that data storage is essentially one-dimensional
• tile indexes: grid-based representation, convert multidimensional to 1-dimensional
  • row
  • row-prime
  • morton: z

Raster structures

• rasters provide a fixed grid for storing data
• cells are addressed using the row and column number
• store as arrays
  • easy to compute
  • waste space
• Quadtree: is a tree structure where every non-leaf node has exactly four descendants
• Region quadtree recursively subdivide non-homogeneous square arrays of cells into four equal sized quadrants
• decomposition continues until all squares bound homogenous regions
• pros: take full advantage of the spatial structure adapt to variable spatial detail
• cons: inefficient for highly inhomogeneous rasters
• very sensitive to changes in the embedding space (e.g., translation rotation)

Point object structure

• grid structures: partition of planar region into equal sized cells- without accounting for point distribution
  • improve range query
  • partition size depends on
    • number of points
    • magnitude of average range query
  • poor performance with non-uniform point distribution
• Point quadtree:combination of grid approach with multidimensional binary search tree
  • lead to exponential increases in descendants in k dimensions
• 2D tree
  • trade tree breadth for depth
  • structure depends on order of point insertion

Collection of objects

• efficient indexes for rectangles are important because rectangles can be used to approximate bounded planar spatial objects.
• each geometric object is enclosed in its MBB
• minimum bounding box (MBB): the smallest rectangle bounding a shape with its axes parallel to the sides
• using MBB, some queries may be answered without retrieving the geometry of an object
• e.g., find all objects which lie entirely within a specified region
• R-Tree: multidimensional dynamic spatial data structure similar to the B-tree
  • leaf nodes represent actual rectangles to be indexed
  • rectangles at any level may overlap
  • good subdivisions
    • minimize the total area of containing rectangles
    • minimize the total area of overlap of containing rectangles
  • overlap is critical-> point and range searches

Spherical data structures

• spherical tessellations provide closer approximation to surface of the Earth
• Quaternary triangular mesh(QTM) approximates the surface of the globe