I created a wiki page for indexed relationships in the Git repo, see: https://github.com/peterneubauer/graph-collections/wiki/Indexed-relationships
> From: [email protected] > Date: Thu, 7 Jul 2011 22:53:05 +0200 > To: [email protected] > Subject: Re: [Neo4j] Indexed relationships > > Could you put these code examples into the Readme for the project or on a > wiki page? > > Am 07.07.2011 um 22:11 schrieb Niels Hoogeveen: > > > > > IndexedRelationship and IndexedRelationshipExpander are now in Git. See: > > https://github.com/peterneubauer/graph-collections/tree/master/src/main/java/org/neo4j/collections/indexedrelationship > > An example: > > class IdComparator implements java.util.Comparator<Node>{ > > public int compare(Node n1, Node n2){ > > long l1 = Long.reverse(n1.getId()); > > long l2 = Long.reverse(n2.getId()); > > if(l1 == l2) return 0; > > else if(l1 < l2) return -1; > > else return 1; > > } > > }static enum RelTypes implements RelationshipType{ > > DIRECT_RELATIONSHIP, > > INDEXED_RELATIONSHIP, > > }; > > Node indexedNode = graphDb().createNode(); > > IndexedRelationship ir = new > > IndexedRelationship(RelTypes.INDEXED_RELATIONSHIP, Direction.OUTGOING, new > > IdComparator(), true, indexedNode, graphDb()); > > > > Node n1 = graphDb().createNode(); > > n1.setProperty("name", "n1"); > > Node n2 = graphDb().createNode(); > > n2.setProperty("name", "n2"); > > Node n3 = graphDb().createNode(); > > n3.setProperty("name", "n3"); > > Node n4 = graphDb().createNode(); > > n4.setProperty("name", "n4"); > > > > indexedNode.createRelationshipTo(n1, RelTypes.DIRECT_RELATIONSHIP); > > indexedNode.createRelationshipTo(n3, RelTypes.DIRECT_RELATIONSHIP); > > ir.createRelationshipTo(n2); > > ir.createRelationshipTo(n4); > > > > IndexedRelationshipExpander re1 = new > > IndexedRelationshipExpander(graphDb(), Direction.OUTGOING, > > RelTypes.DIRECT_RELATIONSHIP); > > IndexedRelationshipExpander re2 = new > > IndexedRelationshipExpander(graphDb(), Direction.OUTGOING, > > RelTypes.INDEXED_RELATIONSHIP); > > > > for(Relationship rel: re1.expand(indexedNode)){ > > System.out.println(rel.getEndNode().getProperty("name")); > > } > > for(Relationship rel: re2.expand(indexedNode)){ > > System.out.println(re2.getEndNode().getProperty("name")); > > } > >> From: [email protected] > >> To: [email protected] > >> Date: Thu, 7 Jul 2011 16:55:36 +0200 > >> Subject: Re: [Neo4j] Indexed relationships > >> > >> > >> Hi Michael,I realize that the implementation of IndexedRelationship can in > >> fact support returning relationships, and I have a preliminary version > >> running locally now.The returned relationships can support all methods of > >> the Relationship interface, returning the node pointing to the treeRoot as > >> the startNode, and returning the node set as the key_value as the > >> endNode.All relationship properties will be stored on the KEY_VALUE > >> relationship pointing to the endNode.There is one caveat to this solution, > >> the returned relationships cannot support the getId() method,and will > >> throw an UnsupportedOperationException when being > >> called.IndexedRelationship will implement Iterable<Relationship>.With > >> these changes, it is possible to create an Expander and I am working right > >> now to implement that.Niels > >> > >>> From: [email protected] > >>> To: [email protected] > >>> Date: Thu, 7 Jul 2011 14:46:35 +0200 > >>> Subject: Re: [Neo4j] Indexed relationships > >>> > >>> > >>> Hi Michael, > >>> > >>> I haven't yet worked on an example. > >>> > >>> There are tests for the SortedTree implementation, > >>> but didn't add those to the IndexedRelationship class, > >>> which is simply a wrapper around SortedTree. > >>> Having a test would have caught the error > >>> that no relationship to the treeNode was created > >>> (fixed that bug and pushed it to Git) > >>> (note to self: always create a unit test, > >>> especially when code seems trivial). > >>> > >>> There is no relationship expander that uses this. > >>> The RelationshipExpander has a method Iterable<Relationship> expand(Node > >>> node) > >>> which cannot be supported, since there is no direct relationship from > >>> startnode to endnode. > >>> Instead there is a path through the index tree. > >>> > >>> It's not possible to support the original relationship-traversal API > >>> since the IndexedRelationship class is not a wrapper around a node, > >>> but a wrapper around the relationships of a certain RelationshipType in > >>> the OUTGOING direction. > >>> > >>> As to the name of the class. > >>> It is essentially an indexed relationship, > >>> and not just a solution to the densely-connected-node problem. > >>> An indexed relationship can also be used to maintain > >>> a sorted set of relationships of any size, > >>> and can be used to guarantee unicity constraints. Niels > >>>> From: [email protected] > >>>> Date: Thu, 7 Jul 2011 13:27:00 +0200 > >>>> To: [email protected] > >>>> Subject: Re: [Neo4j] Indexed relationships > >>>> > >>>> Good work, > >>>> > >>>> do you have an example ready (and/or some tests that show how it > >>>> works/is used) ? > >>>> > >>>> In creation, manual traversal and automatic traversal (i.e. is there a > >>>> RelationshipExpander that uses it). > >>>> > >>>> And in the constructor if there is no relationship to the treeNode, you > >>>> create a new one, but that new treeNode is not connected to the actual > >>>> node? > >>>> > >>>> I'm not sure if it should support the original relationship-traversal > >>>> API / methods (getRelationships(Dir,type), etc). > >>>> > >>>> Perhaps that IndexedRelationship should rather be just a wrapper around > >>>> a SuperNode ? So probably rename it to "SuperNode(Wrapper) or > >>>> HeavilyConnectedNode(Wrapper) ?) > >>>> > >>>> Cheers > >>>> > >>>> Michael > >>>> > >>>> Am 07.07.2011 um 12:51 schrieb Niels Hoogeveen: > >>>> > >>>>> > >>>>> Finished the implementation of indexed relationships. The graph > >>>>> collections component now contains the package > >>>>> https://github.com/peterneubauer/graph-collections/tree/master/src/main/java/org/neo4j/collections/indexedrelationship, > >>>>> containing the IndexedRelationship class. > >>>>> This class can be used instead of regular relationships > >>>>> when:relationships need to be stored in a particular sort ordera > >>>>> unicity constraint needs to be guaranteed nodes become densely > >>>>> populated with relationships. > >>>>> The implementation is traverser friendly. Given a start nodes all end > >>>>> nodes can be found by following four relationships types in outgoing > >>>>> direction. Given an end node the start node can be found by following > >>>>> these four relationship types in incoming direction. Of course this > >>>>> functionality is also covered in the API. > >>>>> Niels > >>>>> > >>>>>> From: [email protected] > >>>>>> To: [email protected] > >>>>>> Date: Thu, 7 Jul 2011 02:36:29 +0200 > >>>>>> Subject: Re: [Neo4j] Indexed relationships > >>>>>> > >>>>>> > >>>>>> Pushed SortedTree to Git after adding a unit test and doing some > >>>>>> debugging. > >>>>>> TODO:Add API for indexed relationships using SortedTree as the > >>>>>> implementation.Make SortedTree thread safe. > >>>>>> With regard to the latter issue. I am considering the following > >>>>>> solution. Acquire a lock (delete a non existent property) on the node > >>>>>> that points to the root of the tree at the start of AddNode, > >>>>>> RemoveNode and Delete. No other node in the SortedTree is really > >>>>>> stable, even the rootnode may be moved down, turning another node into > >>>>>> the new rootnode, while after a couple of remove actions the original > >>>>>> rootnode may even be deleted. > >>>>>> Locking the node pointing to the rootnode, prevents all other > >>>>>> threads/transactions from updating the tree. This may seem > >>>>>> restrictive, but a single new entry or a single removal may in fact > >>>>>> have impact on much of the tree, due to balancing. More selective > >>>>>> locking would require a prebalancing tree walk, determining the > >>>>>> affected subtrees, lock them and once every affected subtree is > >>>>>> locked, perform the actual balancing. > >>>>>> Please let me hear if there are any objections to locking the node > >>>>>> pointing to the tree as the a solution to make SortedTree thread safe. > >>>>>> Niels > >>>>>> > >>>>>>> Date: Tue, 5 Jul 2011 08:27:57 +0200 > >>>>>>> From: [email protected] > >>>>>>> To: [email protected] > >>>>>>> Subject: Re: [Neo4j] Indexed relationships > >>>>>>> > >>>>>>> Great work Nils! > >>>>>>> > >>>>>>> /peter > >>>>>>> > >>>>>>> Sent from my phone. > >>>>>>> On Jul 4, 2011 11:39 PM, "Niels Hoogeveen" <[email protected]> > >>>>>>> wrote: > >>>>>>>> > >>>>>>>> Made some more changes to the SortedTree implementation. Previously > >>>>>>> SortedTree would throw an exception if a duplicate entry was being > >>>>>>> added. > >>>>>>>> I changed SortedTree to allow a key to point to more than one node, > >>>>>>>> unless > >>>>>>> the SortedTree is created as a unique index, in which case an > >>>>>>> exception is > >>>>>>> raised when an attempt is made to add a node to an existing key entry. > >>>>>>>> A SortedTree once defined as unique can not be changed to a > >>>>>>>> non-unique > >>>>>>> index or vice-versa. > >>>>>>>> SortedTrees now have a name, which is stored in the a property of the > >>>>>>> TREE_ROOT relationship and in the KEY_VALUE relationship (a new > >>>>>>> relationship > >>>>>>> that points from the SortedTree to the Node inserted in the > >>>>>>> SortedTree). The > >>>>>>> name of a SortedTree can not be changed. > >>>>>>>> SortedTrees now store the class of the Comparator, so a SortedTree, > >>>>>>>> once > >>>>>>> created, can not be used with a different Comparator. > >>>>>>>> SortedTree is now an Iterable, making it possible to use it in a > >>>>>>> foreach-loop. > >>>>>>>> Since there are as of yet, no unit tests for SortedTree, I will > >>>>>>>> create > >>>>>>> those first before pushing my changes to Git. Preliminary results so > >>>>>>> far are > >>>>>>> good. I integrated the changes in my own application and it seems to > >>>>>>> work > >>>>>>> fine. > >>>>>>>> Todo: > >>>>>>>> Decide on an API for indexed relationships. (Community input still > >>>>>>> welcome).Write unit tests.Make SortedTree thread safe (Community help > >>>>>>> still > >>>>>>> welcome). > >>>>>>>> Niels > >>>>>>>> > >>>>>>>>> From: [email protected] > >>>>>>>>> To: [email protected] > >>>>>>>>> Date: Mon, 4 Jul 2011 15:49:45 +0200 > >>>>>>>>> Subject: Re: [Neo4j] Indexed relationships > >>>>>>>>> > >>>>>>>>> > >>>>>>>>> I forgot to add another recurrent issue that can be solved with > >>>>>>>>> indexed > >>>>>>> relationships: guaranteed unicity constraints. > >>>>>>>>>> From: [email protected] > >>>>>>>>>> To: [email protected] > >>>>>>>>>> Date: Mon, 4 Jul 2011 01:55:08 +0200 > >>>>>>>>>> Subject: [Neo4j] Indexed relationships > >>>>>>>>>> > >>>>>>>>>> > >>>>>>>>>> In the thread [Neo4j] traversing densely populated nodes we > >>>>>>>>>> discussed > >>>>>>> the problems arising when large numbers of relationships are added to > >>>>>>> the > >>>>>>> same node. > >>>>>>>>>> Over the weekend, I have worked on a solution for the > >>>>>>> dense-relationship-nodes using SortedTree in the neo-graph-collections > >>>>>>> component. After some minor tweaks to the implementation of > >>>>>>> SortedTree, I > >>>>>>> have managed to get a workable solution, where two nodes are not > >>>>>>> directly > >>>>>>> linked by a relationship, but by means of a BTree (entirely stored in > >>>>>>> the > >>>>>>> graph). > >>>>>>>>>> Before continuing this work, I'd like to have a discussion about > >>>>>>> features, since what we have now is not just a solution for the dense > >>>>>>> populated node issue, but is actually a full fledges indexed > >>>>>>> relationship, > >>>>>>> which makes it suitable for other purposes too. > >>>>>>>>>> An indexed relationship can for example be used to maintain a > >>>>>>>>>> sorted > >>>>>>> set of relationships in the graph, that is not necessarily huge, but > >>>>>>> large > >>>>>>> enough to make sorting on internal memory too expensive an operation, > >>>>>>> or > >>>>>>> situations where only one out of a large number of relationships is > >>>>>>> actually > >>>>>>> traversed in most cases. > >>>>>>>>>> There are probably more use cases for in-graph indexed > >>>>>>>>>> relationships, > >>>>>>> so I'd like to know what features are desirable and what API would > >>>>>>> Neo4J > >>>>>>> users appreciate. > >>>>>>>>>> P.S. I still think it would be good to consider, if technically > >>>>>>> possible, partitioning the relationship store per relationship type > >>>>>>> and per > >>>>>>> direction. The indexed relationship solution works, but is of course > >>>>>>> slower > >>>>>>> than a direct relationship, both with respect to insert time and > >>>>>>> traversal > >>>>>>> time. If dense relationships are never traversed going out of the > >>>>>>> dense > >>>>>>> node, the extra structure maintained by the BTree is only extra > >>>>>>> burden. > >>>>>>>>>> P.P.S. If there are people with experience to make an > >>>>>>>>>> implementation > >>>>>>> thread safe, please volunteer to help make the implementation > >>>>>>> production > >>>>>>> proof. > >>>>>>>>>> Niels > >>>>>>>>>> _______________________________________________ > >>>>>>>>>> Neo4j mailing list > >>>>>>>>>> [email protected] > >>>>>>>>>> https://lists.neo4j.org/mailman/listinfo/user > >>>>>>>>> > >>>>>>>>> _______________________________________________ > >>>>>>>>> Neo4j mailing list > >>>>>>>>> [email protected] > >>>>>>>>> https://lists.neo4j.org/mailman/listinfo/user > >>>>>>>> > >>>>>>>> _______________________________________________ > >>>>>>>> Neo4j mailing list > >>>>>>>> [email protected] > >>>>>>>> https://lists.neo4j.org/mailman/listinfo/user > >>>>>>> _______________________________________________ > >>>>>>> Neo4j mailing list > >>>>>>> [email protected] > >>>>>>> https://lists.neo4j.org/mailman/listinfo/user > >>>>>> > >>>>>> _______________________________________________ > >>>>>> Neo4j mailing list > >>>>>> [email protected] > >>>>>> https://lists.neo4j.org/mailman/listinfo/user > >>>>> > >>>>> _______________________________________________ > >>>>> Neo4j mailing list > >>>>> [email protected] > >>>>> https://lists.neo4j.org/mailman/listinfo/user > >>>> > >>>> _______________________________________________ > >>>> Neo4j mailing list > >>>> [email protected] > >>>> https://lists.neo4j.org/mailman/listinfo/user > >>> > >>> _______________________________________________ > >>> Neo4j mailing list > >>> [email protected] > >>> https://lists.neo4j.org/mailman/listinfo/user > >> > >> _______________________________________________ > >> Neo4j mailing list > >> [email protected] > >> https://lists.neo4j.org/mailman/listinfo/user > > > > _______________________________________________ > > Neo4j mailing list > > [email protected] > > https://lists.neo4j.org/mailman/listinfo/user > > _______________________________________________ > Neo4j mailing list > [email protected] > https://lists.neo4j.org/mailman/listinfo/user _______________________________________________ Neo4j mailing list [email protected] https://lists.neo4j.org/mailman/listinfo/user
