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
