Expected Application for Multi-version Spatial Indexing Idea

[JohnLyu94]

Hi, My name is Suxing Lyu. I am interested in the idea of "Multi-version Spatial Indexing". Following the application tutorial, I would like to take a brief self-introduction to the community and then expect a discussion with potential mentors about the GSOC application.

Self-Introduction

Currently, I am a second-year doctoral student at the Center for Spatial Information Science, University of Tokyo. My research theme is machine learning/deep learning/spatio-temporal data mining on human mobility. I have experience processing remote sensing imagery, GPS trajectory, geometric vector using python and GIS software, as these are critical before modelling specific tasks.

Why this idea

The version control of the dataset is necessary for research. Data may not be well and correctly processed every time. With full control of versions, data processing can be facilitated and reproducible. In my experiments, moreover, I often have to deal with geospatial data, which is the strong point of Kart. I am very interested in the scope of Kart and would like to contribute to the open-source community. I think GSOC is such a chance.

To be honest, this is the first time I would join in such a project. I have experience in python and C++ but not in software development. I want to practice myself through GSOC, but I am also worried about whether I have enough skills to handle it. I would like to know what your expectations are for this idea.

[rcoup]

Hi Suxing, thanks for getting in touch.

I have experience in python and C++ but not in software development

If you have C++ and Python experience you definitely have experience in software development!

I would explore the libspatialindex MVR-Tree implementation, try and understand the implementation (and the general MVR-Tree/TPR-tree/PPR-Tree/etc concepts) and see how we can apply it to Kart. There's many research papers on multi-dimensional spatial indexes, eg: SaIL: A Spatial Index Library for Efficient Application Integration which might be worth reading.

My understanding it that the libspatialindex uses numeric time as the third dimension, whereas in Kart's case we want to use a Git Tree OID to key into "version" dimension. Possibly this can be achieved in libspatialindex by abstracting the MVRTree implementation to a templated approach, or maybe it's better to build on a different base implementation. For our envisioned use cases we wouldn't need to do queries across time like a typical MVR-Tree, solely to provide efficient lookups and storage.

Once you've done some more reading and are comfortable with the ideas, maybe we can jump on a call/chat and discuss further.

[JohnLyu94]

Thanks for attaching the reading materials! I will read and understand them carefully during this week.

My understanding it that the libspatialindex uses numeric time as the third dimension, whereas in Kart's case we want to use a Git Tree OID to key into "version" dimension.

Once I can order my thoughts, I'll be in touch soon!

[JohnLyu94]

I pulled a fork of Kart and carefully read source codes. My understanding is that Kart is, as it mentioned, what is built on Git with supplements for geospatial usages specifically! I like it more after reading and understanding what Kart is. I organized my thoughts here, and if it is convenient, could we discuss further by chat?

Draft of Multi-Spatial Indexing Implementation Proposal

While collecting reading materials about spatial indexing, I found another option: Google published an R-Tree implementation in Python. They declared it should have comparable speed with others implemented in C. I am considering I can modify it to fit our target. Python implementation is more comfortable in my thoughts. Thus, in my proposal, I would like to create a schedule like:

1. R-Tree -> MVR Tree (if possible, add other algorithms)
2. Test script (performance, work with Kart, …)
3. Documentation (for usage, for developer)

The codes of spatial filtering could be a good reference for my first step.

Furthermore

I also noticed that the documentation for developers could be further improved. If there is time, I would also like to complete this part.

Challenges

I am embarrassed to say that I have no experience building software and testing developed modules. This is where I fall short. At this time, I actually can not completely understand every detail of how Kart goes on. I would like to overcome them along with mentors.

[rcoup]

I found another option: Google published an R-Tree implementation in Python

Can you send a link?

The codes of spatial filtering could be a good reference for my first step.

Spatial filtering is a slightly different concept, and it's important to understand the difference. In the spatial filtering case git is deciding which objects to send between a git server and the kart client, and the git implementation of filters basically asks the question "does object X match the filter (ie: intersect spatial area Q)?" over and over for each relevant object being considered. Our current implementation of the index used for spatial filtering is designed to answer that question.

This is different from our topic, a spatial query which aims to answer the question "find me all the objects in this collection that intersect spatial area Q" — this is what a R-Tree spatial index is designed to answer. But since we potentially have one collection per commit, the multi-version aspect should allow us to reuse the same R-tree as much as possible, since generally changes associated with each commit are relatively small.

I am embarrassed to say that I have no experience building software and testing developed modules. This is where I fall short. At this time, I actually can not completely understand every detail of how Kart goes on. I would like to overcome them along with mentors.

No need to be embarrassed. Can you provide a link to some code you've written elsewhere? I'd suggest you follow the contributing guide to get a development version of Kart up and running, and see if you can make a change to improve something confusing to you :-) We'll aim to add some good-first-issue tickets in the next few days which might provide a good starting point for you.

[JohnLyu94]

Can you send a link?

The R-Tree in Python was copied at pyrtree-github. It was published at pyrtree.

There are some issues:

2. The implementation is only 2D available.
3. Authors declared no guarantee for 3D indexing performance.

The codes of spatial filtering could be a good reference for my first step.

I'm sorry if my words have caused you to misunderstand. A good reference is that I could understand how to develop a module and employ it on Kart. Honestly, I have no experience on how to publish software how to work with developers like a project like Kart. The spatial filtering module made me understand.

Can you provide a link to some code you've written elsewhere?

Sure! I uploaded a gits about my recent research project. It was used to generate a batch of data for training models.

I'd suggest you follow the contributing guide to get a development version of Kart up and running

Thanks for the guide. I will continue reading and learning source codes and try to practice.

Once I go deeper, could I start to share my proposal with you? (like sharing Google Doc)

[rcoup]

Once I go deeper, could I start to share my proposal with you? (like sharing Google Doc)

Sure, my email address is in my Github profile.

[JohnLyu94]

Thanks a lot for your help! I am going busy through the beginning of a new semester, which caused the late reply. I will start formulating a proposal and share it as soon as possible.

One more thing:
As I am an M1 Mac user, I met trouble building a dev environment for a while. Fortunately, now I am able to use a remote server for development. I created a docker image as the virtual kart dev environment based on Ubuntu 20.04. I would like to share it.

See you soon!