Tobias, this mail probably should end up somewhere in the Wiki, very good information content in this :)
Cheers, /peter neubauer COO and Sales, Neo Technology 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 - Relationships count. http://www.linkedprocess.org - Distributed computing on LinkedData scale On Fri, Nov 20, 2009 at 4:14 PM, Tobias Ivarsson <[email protected]> wrote: > Hi Rafael, > > Thanks for the positive review, it's always nice to hear that the answers > provided were helpful, everyone on this list can take pride in that. This > was an interesting problem, from what I've identified there are three main > questions in your email, I'll answer them each bellow: > > 1. Regarding node types: > > There are no node types in Neo4j, since they would not provide any > additional value to the storage or traversal of the graph. > I've discussed this on the mailing list before, so I'll save myself a couple > of keystrokes by providing a link to that discussion: > http://lists.neo4j.org/pipermail/user/2008-October/000848.html > > In the particular case of dealing with node types in a graph matching > situation this is solved by defining PatternNode object, these are > structural types[1] for nodes used for finding nodes that match the type. > The main way to find nodes is still through graph traversal, so the most > important aspect of the "node type" is the relationships that brought us to > the node, even in the graph matching case. Several PatternNode objects could > theoretically match the same node, at different stages of the matching > process. > > 2. Regarding your graph structure: > > If a person could live in several different kinds of places (and not only > streets) your structure could be a good solution. But if a person always > lives in a street you already know that the node at the other end of the > relationship represents a street, and would not have to represent the type > in any other way. This could even be extended, so if a person could live in > either a street or at a farm (assuming that farms don't have street > addresses) you could differentiate using the relationship type: > > Node[name="Dan Citydweller"] --[LivesInStreet]--> Node[name="Baker st."] > Node[name="Farmer Bill"] --[LivesAtFarm]--> Node[name="Bills Farm"] > > In this situation you would not know the type of a node given to you at > random, this is solved by indexing the nodes in separate indexes for each > entity type (and use those to retrieve nodes to start traversing at, instead > of random nodes). So in this case you would have a street index and a person > index: > > Node getThePlaceWhereThisPersonLives(Node person) { > Iterable<Node> locations = person.traverse(Order.DEPTH_FIRST, > StopEvaluator.END_OF_GRAPH, ReturnableEvaluator.ALL_BUT_START_NODE, > LivesInStreet, Direction.OUTGOING, LivesAtFarm, Direction.OUTGOING); > Iterator<Node> iter = locations.iterator(); > if (iter.hasNext()) { > return iter.next(); // We know that a person only lives in one > place, so stop traversing and return that place > } else { > return null; > } > } > > Iterable<Node> getPersonsLivingInThisStreet(Node street) { > return street.traverse(Order.BREADTH_FIRST, StopEvaluator.END_OF_GRAPH, > ReturnableEvaluator.ALL_BUT_START_NODE, LivesInStreet, Direction.INCOMING); > } > > void execute() { > System.out.println("Dan lives in:" + > getThePlaceWhereThisPersonLives(personIndex.get("Dan > Citydweller")).getProperty("name") ); > System.out.println("These people live at Baker street:"); > for (Node person : getPersonsLivingInThisStreet(streetIndex.get("Baker > st."))) { > } > } > > > We would of course have to take care of keeping the indexes updated by > inserting into them when creating new persons / streets. > > You could of course achieve similar results by using the graph matching > component, and use indexes for finding the positions for starting traversals > as in the example above. i.e. the execute method would stay unchanged but > the other two methods would be updated to use the graph matching component: > > Iterable<Node> getPersonsLivingInThisStreet(Node street) { > // Create the pattern - this would be done on setup instead of each time > a query is made > final PatternNode personPattern = new PatternNode( "person" ); > PatternNode streetPattern = new PatternNode( "street" ); > personPattern.createRelationshipTo( streetPattern, LivesInStreet ); > // Do the actual matching > Iterable<PatternMatch> hits = PatternMatcher.getMatcher().match( > streetPattern, street ); > // Transform the result > return new IterableWrapper<Node, PatternMatch>( hits ) { > protected Node underlyingObjectToObject( PatternMatch match ) { > return match.getNodeFor( personPattern ); > } > }; > } > > // getThePlaceWhereThisPersonLives would be similar > > > 3. Regarding how well this scales: > > 2 million nodes are not much, given that I've understood your application > there should not be any problems with that size. > > What I don't understand however is what kinds of documents you were looking > for. Documents on how to design the graph structure or documents on how the > internals are implemented and the performance implications of that? Or > something else entirely? > For design document see the wiki at http://wiki.neo4j.org/ in particular: > * The design guide: http://wiki.neo4j.org/content/Design_Guide > * The domain modeling gallery: > http://wiki.neo4j.org/content/Domain_Modeling_Gallery > For documentation about the internals the source code is your friend, the > comments in there are actually quite good with ASCII-art describing the on > disk layout and all! > > Happy hacking! > > /Tobias > > Disclaimer: All examples are just quickly hacked up, and may contain small > errors, but should hopefully convey the general idea. > > [1] http://en.wikipedia.org/wiki/Structural_type_system > > On Thu, Nov 19, 2009 at 8:38 PM, Rafael Almeida <[email protected]>wrote: > >> Hello, I've sent a message here earlier this year regarding finding >> subgraphs inside a graph. I've got nice answers, but I didn't have the time >> then to implement the ideas. Now, having a little bit more time, I have been >> able to play with neo4j. >> >> I've been told to use the graph-matching component, it seems very nice, but >> I'm having trouble using it to solve my problem. I'll describe what I need >> right now: >> >> I have a graph which has different types of nodes and edges. I see that >> there is a RelationshipType, so I've created my types using it. However, I >> don't see a node type. So the types of nodes are described with a property >> called "type". Both relationships and nodes may have different attributes >> describing that relation and node. >> >> My user will give me a graph with a few properties filled in and I'll have >> to find that subgraph in the bigger graph I have stored. Example, the user >> will gives me something like: >> >> Node[type="Person"] --[LivesIn]--> Node[type="Street", name="Baker Street"] >> >> So I would have to match every person living in baker street. All two nodes >> and relationship should be returned with all their properties. >> >> In order to use the graph-matching component I think I need an initial >> node. So I was thinking in using index-util component to index all those >> types and properties. Then, for the search part, I'd fill in the properties >> of each node or connection, figure out which is the smallest set of nodes to >> start from and begin the matching from there. >> >> I think that would work, but is that the best way to do it? Would that >> scale well for a graph with 2 millions of nodes? I couldn't find much >> documentation on neo's design. Perhaps I didn't look hard enough. Could >> someone point me to a good document on that? Perhaps I'd need to implement >> something myself or read up on some theory. Any pointers will be >> appreciated. >> >> >> >> _______________________________________________ >> Neo mailing list >> [email protected] >> https://lists.neo4j.org/mailman/listinfo/user >> > > > > -- > Tobias Ivarsson <[email protected]> > Hacker, Neo Technology > www.neotechnology.com > Cellphone: +46 706 534857 > _______________________________________________ > Neo mailing list > [email protected] > https://lists.neo4j.org/mailman/listinfo/user > _______________________________________________ Neo mailing list [email protected] https://lists.neo4j.org/mailman/listinfo/user
