GraphHopper.com | Forum | GitHub | Maps | Blog

Location Index Structure


#1

Hey there!

Thanks again for building this amazing OOS framework! I just have a very basic question that you might be able to answer within a few seconds. While the general structure of the nodes edges and other files is pretty obvious to me, the structure of the location_index file is not. I’ve been trying to wrap my had around it from the code, but while I read Peter’s blog posts and do understand them, I don’t get a feeling for the actual structure. Could you point me to any kind of resource or just tell me the structure, if it’s a simple table structure like the other files?

Thanks in advance!

Pascal


#2

Thanks for the kind words - it’s team work :slight_smile:

If you have a quadtree you store 4 pointers to the next level with 4 pointers again and so on until it reaches the leafs - one nodeID or a list of node IDs.

Now LocationIndexTree is only a bit different compared to this quadtree that it uses not a fixed number of 4 pointers for its levels but a higher one like 64 for higher levels and a decreasing number until 4 for lower ones. How many pointers are used is calculated in this while loop

Here is the part where we store the in memory data structure on disc (or in its memory efficient format).