Multi-Dimensional Data Structures

Implementations and experimental evaluations of multidimensional indexing, temporal data structures, computational geometry, skyline processing, and orthogonal line-segment intersection algorithms.

The project was developed as university coursework in Multi-Dimensional Data Structures and contains four independent query modules implemented in Python.

Project overview

Query 1 — 3D R-tree

Implements a three-dimensional R-tree for spatio-temporal trajectory points of the form (x, y, t).

Main functionality:

• insertion using least-enlargement subtree selection;
• Guttman-style quadratic node splitting;
• three-dimensional bounding boxes;
• spatio-temporal range queries;
• counting matching points and unique vehicles;
• benchmark generation for different tree capacities and dataset sizes.

Query 2 — Interval tree and segment tree

Implements two temporal indexing structures:

• a dynamic interval tree based on a randomized treap;
• a segment tree with coordinate compression and canonical-node storage.

The module supports:

• interval-overlap queries;
• stabbing queries;
• insertion, update, and deletion;
• build-time and query-time benchmarking.

Query 3 — Convex hull and skyline processing

Processes movie data represented as two-dimensional points (budget, popularity).

The module includes:

• convex-hull computation;
• a skyline operator that minimizes budget and maximizes popularity;
• Python and SQL skyline implementations;
• benchmark comparison between Python and in-memory SQLite;
• preservation of separate movies with identical nondominated coordinates.

Query 4 — Orthogonal sweep line

Implements a sweep-line algorithm for intersections between horizontal and vertical line segments.

The module includes:

• normalized point and segment representations;
• CSV input validation;
• count-only and full-intersection modes;
• deterministic synthetic dataset generation;
• benchmark generation for multiple input sizes;
• validation that the requested number of segments is generated exactly.

Repository structure

Multi-Dimensional-Data-Structures/
├── Query1/
│   ├── parse_dataset.py
│   ├── README.md
│   ├── results.csv
│   ├── rtree3d.py
│   └── test.py
├── Query2/
│   ├── interval_tree.py
│   ├── parse_dataset.py
│   ├── README.md
│   ├── segment_tree.py
│   └── test.py
├── Query3/
│   ├── README.md
│   ├── skyline_sql.py
│   ├── test.py
│   └── generated CSV results
├── Query4/
│   ├── create_vdataset.py
│   ├── geometry.py
│   ├── README.md
│   ├── results.csv
│   ├── segments.csv
│   ├── sweepline_ortho.py
│   └── test.py
├── data/
│   ├── README.md
│   ├── Movies Dataset/
│   └── Planar Trajectories/
├── docs/
│   └── project-report.pdf
├── tests/
│   ├── test_query1_rtree.py
│   ├── test_query2_temporal_trees.py
│   ├── test_query3_geometry_skyline.py
│   └── test_query4_sweepline.py
├── .gitignore
├── requirements.txt
└── README.md

Generated benchmark and query-result CSV files are retained as experimental evidence. Python cache files, virtual environments, temporary files, and the two oversized raw datasets are excluded through .gitignore.

Requirements

• Python 3.10 or newer
• pandas
• openpyxl

The remaining modules use only the Python standard library, including sqlite3.

Setup

Create and activate a virtual environment.

Windows PowerShell

python -m venv .venv
.\.venv\Scripts\Activate.ps1
python -m pip install --upgrade pip
python -m pip install -r requirements.txt

macOS or Linux

python3 -m venv .venv
source .venv/bin/activate
python -m pip install --upgrade pip
python -m pip install -r requirements.txt

Dataset setup

Two large raw datasets are intentionally excluded because they exceed GitHub's normal file-size limits.

Place them at these paths before running the corresponding modules:

data/Planar Trajectories/trajectories-0750am-0805am.txt
data/Movies Dataset/movies_dataset_cleaned/data_movies_clean.xlsx

See data/README.md for complete dataset setup instructions and the supporting documentation retained in the repository.

Running the modules

Run all commands from the repository root.

Query 1

python Query1/test.py

Produces:

Query1/results.csv

Query 2

python Query2/test.py

Prints a benchmark summary for interval-overlap and stabbing queries.

Query 3

Run the Python implementation:

python Query3/test.py --mode run
python Query3/test.py --mode bench

Run the SQL skyline implementation:

python Query3/skyline_sql.py --mode run
python Query3/skyline_sql.py --mode bench

Main outputs include:

Query3/out_convex_hull.csv
Query3/out_skyline.csv
Query3/out_skyline_sql.csv
Query3/bench_python.csv
Query3/bench_sql.csv

Query 4

Generate a synthetic orthogonal dataset:

python Query4/create_vdataset.py --n 2000 --hv_ratio 0.5 --clustered --seed 42 --bbox 0 0 10000 10000 --min_len 50 --max_len 500 --out segments.csv

Run the sweep-line algorithm:

python Query4/test.py --input Query4/segments.csv

Run the benchmark:

python Query4/test.py --bench --n-list 500,1000,2000,4000,8000 --repeats 5 --hv_ratio 0.5 --clustered --out Query4/results.csv

Automated verification

Run the complete correctness suite from the repository root:

python -m unittest discover -s tests -v

The current project passes nine automated tests covering:

• R-tree bounding-box normalization;
• R-tree range-query results against brute force;
• interval-tree queries, updates, and deletion;
• segment-tree stabbing queries, updates, and deletion;
• convex-hull correctness;
• skyline handling of duplicate nondominated coordinates;
• closed-endpoint orthogonal intersections;
• sweep-line results against brute force;
• exact generation of 8,000 synthetic segments.

Reference result:

Ran 9 tests
OK

Documentation

The public project report is available here:

• Project report

The report should contain the four contributors' names but omit registration numbers, email addresses, and other unnecessary personal identifiers.

Contributors

This project was developed collaboratively by:

• Andreas Kerkidis
• Rafael Kyriakou
• Pantelis Petrou
• Rafael Kitromilidis

Academic context

This repository presents an educational implementation of multidimensional and temporal data structures, computational-geometry algorithms, and their experimental evaluation.

The implementations prioritize clarity, reproducibility, and correctness. They are not intended as production replacements for mature spatial databases or specialized geometry libraries.

License

No open-source license has currently been assigned to this collaborative project.

The repository is published for academic and portfolio viewing. Reuse, modification, or redistribution requires permission from the contributors.