A project that implement R-tree libary for spatial searching.
GitHub Repository: https://github.com/yxuan0329/R-tree-Search-Engine
R-tree-Search-Engine/
│
├── datasets/
│ ├── generate_data.py
│ └── testdata.txt
│
├── includes/
│ ├── Node.h
│ └── Rtree.h
│
├── Makefile
│
├── main.cpp
│
├── performance/
│ ├── baseline.py
│ ├── ours.py
│ └── plot.py
│
├── README.md
|
├── run.py
|
├── src/
│ ├── Node.cpp
| ├── pybind.cpp
│ └── Rtree.cpp
│
└──tests/
└── test_Rtree.py
R-tree is a tree structure designed for efficient spatial data access. It has been widely used in real-world geographic searching because of its exceptional searching performance. In this project, we aim to serve a R-tree library to provide an efficient search for end-users.
In geographic searching application, the users would expect to swiftly receive a set of searching results upon entering the query. In real-world application, rapid access to geospatial information is crucial for the users, as delays can result in inconveniences and increased costs.
The fundamental concept behind the R-tree is to encapsulate nearby objects related to the searching target within a minimum bounding rectangle. Our goal is to develop an efficient R-tree library for spatial data retrieval that can address large-scale spatial data searches.
This project aims to provide to users who seek to build an efficient multi-dimensional searching service.
The library includes:
Rtree()
: Initialize a r-treeinsert()
: Insert a reactangle area in r-treeremove()
: Delete a rectangle area in r-treesearch()
: Search for all the available results in r-tree
This library provides to C++ and python users. The users can include the library by linking in their program.
- Clone this GitHub repository.
$ git clone https://github.com/yxuan0329/R-tree-Search-Engine.git
- Build. You should see
_Rtree.so
in your directory if it built successfully.
$ make
- Include the following scripts in your main function.
// add this at the head of your code
#include “.includes/Rtree.h”
- Compile your program with linking the library. The C++ users can include when compiling. See main.cpp for more details.
$ g++ main.cpp -o -l_Rtree
The Python users can import the library by adding the script. See main.py for more details.
import r-tree-lib
- Automatic build system: Makefile
- Version control: git
- Testing framework: Pytest
- Documentation: README.md
- Continuous Integration: GitHub Actions
Testing data source: random-generated testing datasets including location and the name of the place.
The testing mesurement includes correctness and time performance.