R-tree Spatial Queries

Project Overview

This project implements an R*-tree spatial index in Java for efficient spatial querying of OpenStreetMap data (Malta). The system processes OSM XML files through a three-stage pipeline, builds spatial indexes, and supports multiple query types with comprehensive performance benchmarking against sequential scans.

• Language: Java 8+ with custom spatial data structures
• Data Source: OpenStreetMap (.osm) XML files
• Core Algorithm: R*-tree spatial indexing for 2D point data
• Query Types: Range queries, k-nearest neighbors, skyline queries
• Performance: Comprehensive benchmarking with speedup analysis

Data Pipeline

The application follows a structured three-stage pipeline for processing OSM data into an efficient spatial index:

Stage 1: OSM Parsing

• Input: OpenStreetMap XML file containing spatial data
• Output: List of Record objects with coordinates and metadata

Stage 2: DataFile Creation

• Function: Organizes records into 32KB blocks for efficient storage
• Output: datafile.dat - Binary file containing serialized spatial records

Stage 3: IndexFile Creation

• Process: R*-tree construction via RStarTree or BulkLoadingRStarTree
• Function: Builds spatial index structure pointing to datafile blocks
• Output: indexfile.dat - Binary file containing R*-tree nodes

Architecture Types

1. Standard R*-tree (Incremental Loading)

• Method: Records inserted one-by-one with dynamic tree restructuring
• Characteristics:
• Dynamic insertion with overflow treatment
• Supports insertions after initial construction

2. Bulk Loading R*-tree

• Method: Sorts all records and builds tree bottom-up
• Characteristics:
• More efficient initial construction
• Better space utilization

Query Types

Range Query (BoundingBoxRangeQuery)

Finds all points within a rectangular bounding box. Efficient for spatial range selections.

K-Nearest Neighbors (NearestNeighboursQuery)

Finds the k closest points to a given coordinate. Optimized for proximity-based searches.

Skyline Query (SkylineQuery)

Identifies non-dominated points within a bounding box region. Useful for multi-criteria optimization.

Performance Analysis

Comprehensive benchmarking comparing R*-tree performance against sequential scan for range and KNN queries with variable parameters.

Range Query Performance

Range query performance comparison between R*-tree and sequential scan

Speedup analysis for range queries showing when R*-tree outperforms sequential scan

K-Nearest Neighbors Performance

KNN query performance comparison showing R*-tree efficiency

Speedup analysis for KNN queries demonstrating spatial indexing benefits