Re: [Neo4j] Neo4j in GIS Applications
Hello Peter, that sounds fine. I will probably compare some quad-tree against the existing R-tree implementation. It will take some time until I start with implementing something, but I will keep you informed. Regards, Daniel -- View this message in context: http://neo4j-community-discussions.438527.n3.nabble.com/Neo4j-in-GIS-Applications-tp3393925p3437567.html Sent from the Neo4j Community Discussions mailing list archive at Nabble.com. ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Neo4j in GIS Applications
Daniel, having an alternative index implementation would be great! We have pulled out the RTree from Spatial into https://github.com/neo4j/graph-collections which you can fork and add your index, possibly even testing it against a spatial fork. WDYT? Cheers, /peter neubauer GTalk: neubauer.peter Skype peter.neubauer Phone +46 704 106975 LinkedIn http://www.linkedin.com/in/neubauer Twitter http://twitter.com/peterneubauer http://www.neo4j.org - Your high performance graph database. http://startupbootcamp.org/ - Öresund - Innovation happens HERE. http://www.thoughtmade.com - Scandinavia's coolest Bring-a-Thing party. On Thu, Oct 13, 2011 at 10:10 PM, danielb wrote: > Hello there, > > first I have written a wall of text, previewed it and then the forum went > grey and all of the text has gone - AR! > > In short: I have read some papers about different spatial indices in the > last days. The standard R-tree can be improved in various ways or even > replaced by a quad-tree. In one of the upcoming PostgreSQL versions they > will probably have a quad-tree based SP-GiST implementation. Early > proto-typing shows a speedboost of a factor of 6 in several bounding box > queries. In Neo4j there are less spatial operations based on an index > compared to a relational database and therefore it should be easier to find > an appropriate index (which hopefully will speed up some spatial > operations). In the course of my master thesis (which starts next week - > wish me luck and success) I could have a look into this. > > So before everything is gone again - DOOOH - I finish this now... > > Regards, Daniel > > -- > View this message in context: > http://neo4j-community-discussions.438527.n3.nabble.com/Neo4j-in-GIS-Applications-tp3393925p3419657.html > Sent from the Neo4j Community Discussions mailing list archive at Nabble.com. > ___ > Neo4j mailing list > User@lists.neo4j.org > https://lists.neo4j.org/mailman/listinfo/user > ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Neo4j in GIS Applications
Hello there, first I have written a wall of text, previewed it and then the forum went grey and all of the text has gone - AR! In short: I have read some papers about different spatial indices in the last days. The standard R-tree can be improved in various ways or even replaced by a quad-tree. In one of the upcoming PostgreSQL versions they will probably have a quad-tree based SP-GiST implementation. Early proto-typing shows a speedboost of a factor of 6 in several bounding box queries. In Neo4j there are less spatial operations based on an index compared to a relational database and therefore it should be easier to find an appropriate index (which hopefully will speed up some spatial operations). In the course of my master thesis (which starts next week - wish me luck and success) I could have a look into this. So before everything is gone again - DOOOH - I finish this now... Regards, Daniel -- View this message in context: http://neo4j-community-discussions.438527.n3.nabble.com/Neo4j-in-GIS-Applications-tp3393925p3419657.html Sent from the Neo4j Community Discussions mailing list archive at Nabble.com. ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Neo4j in GIS Applications
Daniel,
of course you could use native external indicies instead of in-graph
structures, but then you loose much of the topology capabilities of a
connected graph. However, probably it's a good idea to provide some
example of that, too. Got a link to a good native RTree implementation
that could be used?
Cheers,
/peter neubauer
GTalk: neubauer.peter
Skype peter.neubauer
Phone +46 704 106975
LinkedIn http://www.linkedin.com/in/neubauer
Twitter http://twitter.com/peterneubauer
http://www.neo4j.org - Your high performance graph database.
http://startupbootcamp.org/ - Öresund - Innovation happens HERE.
http://www.thoughtmade.com - Scandinavia's coolest Bring-a-Thing party.
On Mon, Oct 10, 2011 at 11:56 AM, danielb wrote:
> Retrieving data in constant time sounds very promising especially for routing
> purposes. Did you allready have thoughts on algorithms that use hierarchies
> or contraction of the network? In our students project we implemented some
> approaches to reduce search space and have thoughts on the heuristics used
> for A*. When travel speed comes into concern we got very different results
> with SLD heuristics. Maybe this could be of interest for Neo4j.
> When doing bounding box queries the only advantage of Neo4j could be better
> spatial locality of data ('nodes' and 'ways' both stored in the same
> container). Everything else is up to the r-tree performance as in PostGIS,
> which uses an improved r-tree in GIST. Maybe you can do an r-tree search for
> the first node near the center of the bounding box and with some magic
> retrieve the surrounding nodes with graph traversing... At least I will
> think about this, if you can improve bounding box queries over PostGIS.
> When I switch to a low zoomlevel I want to use generalization and
> simplification of mapdata. In Neo4j I can model that within subgraphs I
> guess? For example have different relationships for different zoomlevels (I
> skip some nodes of a way for example). I could also build a routing network
> within subgraphs where I skip non-junction nodes for example?
> Btw what do you think from building a graph inside a relational database? As
> I understand now it would be very inefficient because you would have at
> least two tables (vertices and edges) and have to do time demanding joins
> with the two foreign key colums in the edge table.
>
> Regards, Daniel
>
>
> --
> View this message in context:
> http://neo4j-community-discussions.438527.n3.nabble.com/Neo4j-in-GIS-Applications-tp3393925p3409062.html
> Sent from the Neo4j Community Discussions mailing list archive at Nabble.com.
> ___
> Neo4j mailing list
> User@lists.neo4j.org
> https://lists.neo4j.org/mailman/listinfo/user
>
___
Neo4j mailing list
User@lists.neo4j.org
https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Neo4j in GIS Applications
Retrieving data in constant time sounds very promising especially for routing
purposes. Did you allready have thoughts on algorithms that use hierarchies
or contraction of the network? In our students project we implemented some
approaches to reduce search space and have thoughts on the heuristics used
for A*. When travel speed comes into concern we got very different results
with SLD heuristics. Maybe this could be of interest for Neo4j.
When doing bounding box queries the only advantage of Neo4j could be better
spatial locality of data ('nodes' and 'ways' both stored in the same
container). Everything else is up to the r-tree performance as in PostGIS,
which uses an improved r-tree in GIST. Maybe you can do an r-tree search for
the first node near the center of the bounding box and with some magic
retrieve the surrounding nodes with graph traversing... At least I will
think about this, if you can improve bounding box queries over PostGIS.
When I switch to a low zoomlevel I want to use generalization and
simplification of mapdata. In Neo4j I can model that within subgraphs I
guess? For example have different relationships for different zoomlevels (I
skip some nodes of a way for example). I could also build a routing network
within subgraphs where I skip non-junction nodes for example?
Btw what do you think from building a graph inside a relational database? As
I understand now it would be very inefficient because you would have at
least two tables (vertices and edges) and have to do time demanding joins
with the two foreign key colums in the edge table.
Regards, Daniel
--
View this message in context:
http://neo4j-community-discussions.438527.n3.nabble.com/Neo4j-in-GIS-Applications-tp3393925p3409062.html
Sent from the Neo4j Community Discussions mailing list archive at Nabble.com.
___
Neo4j mailing list
User@lists.neo4j.org
https://lists.neo4j.org/mailman/listinfo/user
Re: [Neo4j] Neo4j in GIS Applications
Hi all, I am certainly behind on my emails, but I did just answer a related question about OSM and fragmentation, and I think that might have answered some of Daniels questions. But I can say a little more about OSM and Neo4j here, specifically about the issue of joins in postgres. Let me start by describing where I think postgres might be faster than neo4j, and then move onto where neo4j is faster than postgres. Importing OSM data into postgres will be faster than neo4j because the foreign keys are simple integer references between tables and are indexed using postgres high performance indexes. In Neo4j the relationships are much more detailed explicit bi-directional references taking more disk space (but no index space). The disk write time is longer (more data written), but the advantages of not having an index make it worth while. So that leads naturally to where neo4j is faster. The reason there is no index on the foreign key is because there is no need for one. Each relationship contains the id of the node it points to (and points from), and that id is directly mapped to the location on disk of the node itself. So this is more like an array lookup, because all nodes are the same size on disk. So the 'join' you perform when traversing from one osm-node to another is extremely fast, but more importantly it is not affected by database size. It is O(1) in performance! Fantastic! In rdbms, the need for an index on the foreign key means you are building a tree structure to get the join down from O(N) to O(ln(N)) or something better, but never as good as O(1). In neo4j-spatial, if you perform a bounding box query, you are traversing an RTree, which does not exist in posgres, but does exist in PostGIS. In both Neo4j-Spatial and PostGIS you are working with a tree index that will slow things down if there is a lot of data, and currently the postgis rtree is better optimized than the neo4j-spatial rtree. But if you are performing more graph-like processing, for example proximity searches, or routing analysis, then you will get the full O(1) benefits of the graph database, and no way can postgres match that :-) OK. Lots of hype, but I get enthusiastic sometimes. Take anything I say with a pinch of salt. Believe the part that make sense to you, and try some tests otherwise. It would be great to hear your experiences with modeling OSM in neo4j versus postgres. Regards, Craig On Tue, Oct 4, 2011 at 7:18 PM, Andreas Kollegger < andreas.kolleg...@neotechnology.com> wrote: > Hi Daniel, > > If you haven't yet, you should check out the work done in the Neo4j Spatial > project - https://github.com/neo4j/spatial - which has fairly > comprehensive > support for GIS. > > Data locality, as you mention, is exactly a big advantage of using a graph > for geospatial data. Take a look at the Neo4j Spatial project and let us > know what you think. > > Best, > Andreas > > On Tue, Oct 4, 2011 at 9:58 AM, danielb wrote: > > > Hello everyone, > > > > I am going to write my master thesis about the suitability of graph > > databases in GIS applications (at least I hope so^^). The database has to > > provide topological queries, network analysis and the ability to store > > large > > amount of mapdata for viewing - all based on OSM-data of Germany (< 100M > > nodes). Most likely I will compare Neo4j to PostGIS. > > As a starting point I want to know why you would recommend Neo4j to do > the > > job? What are the main advantages of a graph database compared to a > > (object-)relational database in the GIS environment? The main focus and > the > > goal of this work should be to show a performance improvement over > > relational databases. > > In a student project (OSM navigation system) we worked with relational > > (SQLite) and object-oriented (Perst) databases on netbook hardware and > > embedded systems. The relational database approach showed us two > problems: > > If you transfer the OSM model directly into tables then you have a lot of > > joins which slows everything down (and lots of redundancy when using > > different tables for each zoom level). The other way is to store as much > as > > possible in one big (sparse) table. But this would also have some > > performance issues I guess and from a design perspective it is not a nice > > solution. The object-oriented database also suffered from many random > reads > > when loading a bounding box. In addition we could not say how data was > > stored in detail. > > The performance indeed increased after caching occured or by the use of > SSD > > hardware. You can also store everything in RAM (money does the job), but > > for > > now you have to assume that all of the data has to be read from a slow > disk > > the first time. Can Neo4j be configured to read for example a bounding > box > > of OSM data from disk in an efficient way (data locality)? > > Maybe you also have some suggestions where I should have a look at in > this > > work and what can be improved in Neo4j to get
Re: [Neo4j] Neo4j in GIS Applications
Hi Daniel, If you haven't yet, you should check out the work done in the Neo4j Spatial project - https://github.com/neo4j/spatial - which has fairly comprehensive support for GIS. Data locality, as you mention, is exactly a big advantage of using a graph for geospatial data. Take a look at the Neo4j Spatial project and let us know what you think. Best, Andreas On Tue, Oct 4, 2011 at 9:58 AM, danielb wrote: > Hello everyone, > > I am going to write my master thesis about the suitability of graph > databases in GIS applications (at least I hope so^^). The database has to > provide topological queries, network analysis and the ability to store > large > amount of mapdata for viewing - all based on OSM-data of Germany (< 100M > nodes). Most likely I will compare Neo4j to PostGIS. > As a starting point I want to know why you would recommend Neo4j to do the > job? What are the main advantages of a graph database compared to a > (object-)relational database in the GIS environment? The main focus and the > goal of this work should be to show a performance improvement over > relational databases. > In a student project (OSM navigation system) we worked with relational > (SQLite) and object-oriented (Perst) databases on netbook hardware and > embedded systems. The relational database approach showed us two problems: > If you transfer the OSM model directly into tables then you have a lot of > joins which slows everything down (and lots of redundancy when using > different tables for each zoom level). The other way is to store as much as > possible in one big (sparse) table. But this would also have some > performance issues I guess and from a design perspective it is not a nice > solution. The object-oriented database also suffered from many random reads > when loading a bounding box. In addition we could not say how data was > stored in detail. > The performance indeed increased after caching occured or by the use of SSD > hardware. You can also store everything in RAM (money does the job), but > for > now you have to assume that all of the data has to be read from a slow disk > the first time. Can Neo4j be configured to read for example a bounding box > of OSM data from disk in an efficient way (data locality)? > Maybe you also have some suggestions where I should have a look at in this > work and what can be improved in Neo4j to get better results. I also would > appreciate related papers. > > kindly regards, Daniel > > -- > View this message in context: > http://neo4j-community-discussions.438527.n3.nabble.com/Neo4j-in-GIS-Applications-tp3393925p3393925.html > Sent from the Neo4j Community Discussions mailing list archive at > Nabble.com. > ___ > Neo4j mailing list > User@lists.neo4j.org > https://lists.neo4j.org/mailman/listinfo/user > ___ Neo4j mailing list User@lists.neo4j.org https://lists.neo4j.org/mailman/listinfo/user
