Ok I get it. I keep not thinking about relationships flexibly enough. I
need to take a little time to get used to thinking about problems this way.
Thanks for your help!
On Wed, Mar 17, 2010 at 5:43 PM, Craig Taverner <cr...@amanzi.com> wrote:
> I guess I could say that the approach is totally different, but in reality
> you start at the same point, working out what query you want. But after
> that
> things change. Let's consider two cases, the huge network and the paging
> examples you used below.
>
> For the first, keep in mind that if you scale the total database size,
> relational db's don't scale as well as graph db's, because in relational
> db's performance is related to total table size, whereas graph db's
> performance is not. However, both db's are affected by the result set size.
> So for twitter type cases, graph db's scale better with total subscriber
> base, but not necessarily for an individual 'mega-user'. But let's look at
> that case. I believe a real human user would never be able to process
> millions of messages a day, so I must assume that this is a bot use case,
> perhaps a script that subscribes to enormous numbers of people scanning for
> particular patterns of information. Both relational and graph db's will
> feel
> the strain on a huge resultset. Personally I would probably follow twitters
> example and return only paginated result, breaking up the load so the bot
> would not negatively impact the network for human users.
>
> So, getting to pagination, the query you want is perhaps 'give me the
> ordered results, as a block of n messages starting at message x'. Obviously
> this is easily translatable into SQL for relational databases. For the
> graph
> database, it is a little more work, but again you start with that verbal
> query and figure out what it really means in a graph. There are two key
> components:
>
> - Ordered results
> - Starting point and number of results
>
> For SQL this translates to 'order by', 'where id > x' and 'limit n'. For
> graph databases this translates into adding ordering relationships like
> message(X)-->PREVIOUS-->message(X+1). On each pagination, you can take the
> PREVIOUS message as the begining of the next pagination (possibly passing
> the node id in the session). Each pagination is simply a traverser that
> runs
> down the PREVIOUS chain, exiting the loop after n messages.
>
>
> On Wed, Mar 17, 2010 at 10:19 PM, Lincoln <linxbet...@gmail.com> wrote:
>
> > Wow dude, this is blowing my mind just a little.
> >
> > Ok, sticking with the twitter example, I'm concerned about the edge
> cases.
> > I'd say it's easy to optimize with a relational db or any other storage
> > for
> > that matter if I make the assumption that people only follow a few
> hundred
> > people and only want recent messages. However some people follow
> hundreds
> > of thousands of people. If Guy Kawasaki uses my app, I'd run into a
> > problem
> > quickly.
> >
> > However I see your point that I don't have to limit myself to just the
> > obvious relationships, but can create relationships that serve specific
> > purposes and use-cases such as your day example. I'm not sure how I
> would
> > want to model my use-case to allow for Guy Kawaski, I'll have to think
> more
> > about it. Is there a threshold beyond which adding relationships between
> > nodes causes problems? If not, or if it's high, you could create custom
> > relationships for every type of query you'd want to do.
> >
> > However, a secondary question comes up. If we continue with the twitter
> > example, and I want to be able to page through results, is that directly
> > supported through Neo4j's API? Coming from a more traditional storage
> > background I tend to think of what I'd want as a sort by time and then a
> > skip and limit on the results (so I could say give me messages 1-100
> sorted
> > by time descending). Is there anything equivalent in Neo4j or is the
> > approach totally different?
> >
> > Thanks,
> > Lincoln
> >
> >
> > On Wed, Mar 17, 2010 at 12:41 PM, Craig Taverner <cr...@amanzi.com>
> wrote:
> >
> > > Hi Lincoln,
> > >
> > > So it sounds like you don't need the IS_VISIBLE relations after all.
> The
> > > traverser works by following all relationships of the specified types
> and
> > > directions from each current node (as you traverse, or walk the graph).
> > You
> > > can have a complex graph and traverse to high depth very fast
> (thousands
> > of
> > > relationships per second). The traverser will also automatically check
> > that
> > > the same node is not returned twice. The test for the relationship type
> > is
> > > efficient. Still reasonable, but less efficient is the custom test you
> > > might
> > > put in the returnable evaluator, but if the limiting factor is usually
> > the
> > > number of relationships traversed, and if that is kept managable, the
> > > evaluator test is no concern.
> > >
> > > I think twitter is a good case in point, even with many millions of
> > users,
> > > you will still only follow perhaps a hundred and they will tweet
> perhaps
> > a
> > > hundred, or a thousand times, so your traverser will find the 10k-100k
> > > messages quite quickly. This can be speeded up further, but the right
> > > approach depends again on your use case. The idea with using a graph
> > > database is that the actual usage probably maps very well to the graph
> > > structure, so when deciding how to speed up your search, consider how
> it
> > > will be used. In twitter one normally only cares about recent messages,
> > so
> > > how about not linking directly from the user to the message, but link
> to
> > an
> > > intermediate node representing time, for example, a day-node. Then each
> > new
> > > message is added to the day node for that day, and that will
> > automatically
> > > become yesterday the next day. Then your traversal can have a stop
> > > evaluator
> > > to not follow old messages (unless your query is looking for old
> > messages,
> > > of course). So the 100k messages might drop to only a few hundred, or
> > even
> > > just a few dozen. Certainly that will be a query of the order of
> > > milliseconds!
> > >
> > > Moving away from the traverser, you also have the option to call
> directly
> > > the getRelationships() methods from the node. If you structure is
> > > predictable, like viewer-->FOLLOWS-->user-->CREATED-->message, then two
> > > nested for loops would work, the outer iterating over the followers and
> > the
> > > inner iterating over the messages. If you changed to add a time-based
> > > interim node (which is a kind of graph-index), then you need to have
> > three
> > > loops. If you made your time index a deeper tree (months->days->hours,
> > > etc.), then you would need to further refactor the code. However, if
> you
> > > stuck with a traverser, you might not need to change the traverser even
> > of
> > > the graph structure changed, as long as the same relationship types
> were
> > > maintained. Does that make sense?
> > >
> > > Cheers, Craig
> > >
> > > On Wed, Mar 17, 2010 at 4:00 PM, Lincoln <linxbet...@gmail.com> wrote:
> > >
> > > > Thanks Craig,
> > > >
> > > > I'd like to clarify my question (I don't think it changes your answer
> > > > though).
> > > >
> > > > I wanted all messages visible to me created by users I follow. Thus,
> > the
> > > > FOLLOWS relationship is not enough. I'd need to see messages that
> are
> > > > visible to me and then check if they were created by users I follow,
> or
> > > I'd
> > > > need to see messages created by users I follow and then see if
> they're
> > > > visible to me.
> > > >
> > > > I assume your last example still yields the result I'm looking for.
> > > Could
> > > > you describe what actually happens here though? I'm unclear on what
> > the
> > > > traversal looks like. Would it first traverse every outgoing FOLLOWS
> > > > relationship from the viewer, yielding other users, and then traverse
> > all
> > > > the CREATED relationships to get to messages?
> > > >
> > > > Also, given very large numbers of FOLLOWS and CREATED relationships
> > (with
> > > > say, a twitter graph), how is this made efficient?
> > > >
> > > > Sorry for all the basic questions but I couldn't find this
> information
> > in
> > > > the docs. If there's something I should be reading before posting
> > these
> > > > questions, please point me to it.
> > > >
> > > > Thanks!
> > > >
> > > > Lincoln
> > > >
> > > > On Wed, Mar 17, 2010 at 7:06 AM, Craig Taverner <cr...@amanzi.com>
> > > wrote:
> > > >
> > > > > I'm uncertain about one ambiguity in your model, you are able to
> find
> > > > > messages through FOLLOWS and IS_VISIBLE_BY. These will give two
> > > different
> > > > > sets, and my first impression was that FOLLOWS gives you the right
> > > > answer.
> > > > > In other words you want to query for 'all messages by users I
> > follow'?
> > > In
> > > > > that case you do not need IS_VISIBLE_BY. However, if there are
> > messages
> > > > by
> > > > > people you follow, but are not allowed to see, then you also need
> the
> > > > > IS_VISIBLE_BY. But I would still reconsider linking directly from
> the
> > > > > viewer
> > > > > to the message for that case. I'd rather have the messages linked
> to
> > > some
> > > > > categorization structure for things like 'public', 'private', etc.
> > > > >
> > > > > Anyway, here are some suggestions for the various approaches above:
> > > > > *'all messages by users I follow'*
> > > > > val msgs = viewer.traverse(
> > > > > Order.BREADTH_FIRST, StopEvaluator.END_OF_GRAPH,
> > > > > (tp: TraversalPosition) => IsMessage(tp.currentNode()),
> > > > > Rels.FOLLOWS, Direction.OUTGOING,
> > > > > Rels.CREATED, Direction.OUTGOING)
> > > > >
> > > > > *'all messages visible to me'*
> > > > > val msgs = viewer.traverse(
> > > > > Order.BREADTH_FIRST, StopEvaluator.END_OF_GRAPH,
> > > > > ReturnableEvaluator.ALL_BUT_START_NODE,
> > > > > Rels.IS_VISIBLE_BY, Direction.INCOMING)
> > > > >
> > > > > *'all messages, visible to me, by people I follow'*
> > > > > val msgs = viewer.traverse(
> > > > > Order.BREADTH_FIRST, StopEvaluator.END_OF_GRAPH,
> > > > > (tp: TraversalPosition) => {
> > > > > val msg = tp.currentNode()
> > > > > IsMessage(msg) && IsVisibleBy(msg,viewer)
> > > > > },
> > > > > Rels.FOLLOWS, Direction.OUTGOING,
> > > > > Rels.CREATED, Direction.OUTGOING)
> > > > >
> > > > > Of course I assume you make the utility functions IsMessage(node:
> > Node)
> > > > and
> > > > > IsVisibleBy(msg: Node, user: Node), and these will test the
> existance
> > > of
> > > > > properties and relations as appropriate to make the decision.
> > > > >
> > > > >
> > > > > On Wed, Mar 17, 2010 at 6:32 AM, Lincoln <linxbet...@gmail.com>
> > wrote:
> > > > >
> > > > > > Hi, I've just started looking at Neo4j and I'm quite intrigued.
> > > > However,
> > > > > > the cognitive dissonance that I've grown so used to in modeling
> > > storage
> > > > > is
> > > > > > proving to be a bit difficult to let go at this early stage :)
> > > > > >
> > > > > > I was hoping that if someone could help me through an example I
> > would
> > > > be
> > > > > > able to grok how to properly structure my data and query it in
> > Neo4j.
> > > > > >
> > > > > > Nodes:
> > > > > > Message( text: String )
> > > > > > User( id: Long )
> > > > > >
> > > > > > Relationships:
> > > > > > CREATED
> > > > > > FOLLOWS
> > > > > > IS_VISIBLE_BY
> > > > > >
> > > > > > So I might have a graph with entries like so:
> > > > > >
> > > > > > User(1) --> CREATED --> Message("i woke up late today")
> > > > > > User(2) --> CREATED --> Message("hello")
> > > > > > User(3) --> CREATED --> Message("ugh, i hate mondays")
> > > > > >
> > > > > > User(1) --> FOLLOWS --> User(2)
> > > > > >
> > > > > > Let's also say all messages are visible to User 1.
> > > > > >
> > > > > > Message("i woke up late today") --> IS_VISIBLE_BY --> User(1)
> > > > > > Message("hello") --> IS_VISIBLE_BY --> User(1)
> > > > > > Message("ugh, i hate mondays") --> IS_VISIBLE_BY --> User(1)
> > > > > >
> > > > > > So, I can do a simple traversal for visible:
> > > > > >
> > > > > > val graphDb = new EmbeddedGraphDatabase( "path/to/neo4j-db" )
> > > > > > val index = new LuceneIndexService( graphDb )
> > > > > > val viewer = index.getSingleNode("id", 1)
> > > > > > val msgs = viewer.traverse( Order.BREADTH_FIRST,
> > > > > > StopEvaluator.END_OF_GRAPH,
> > > > > > ReturnableEvaluator.ALL_BUT_START_NODE, Rels.IS_VISIBLE_BY,
> > > > > > Direction.INCOMING)
> > > > > > msgs.toList.map(_.toJson).mkString("{ msgs : [", ",", "] }") //
> > > > assuming
> > > > > i
> > > > > > have the relevant functions
> > > > > >
> > > > > > But let's say that this is going to return too many messages.
> Just
> > > > > because
> > > > > > all the messages are possibly visible to me, doesn't mean I want
> to
> > > see
> > > > > > them
> > > > > > all. So, I'd like to additionally filter by the FOLLOWS
> > > relationship.
> > > > > I'd
> > > > > > like to express "get all messages that are visible and were
> created
> > > by
> > > > a
> > > > > > user that I follow." Can someone show me an example of how to do
> > > that?
> > > > > >
> > > > > > I'm guessing that you need to implement a custom
> > ReturnableEvaluator,
> > > > but
> > > > > I
> > > > > > don't understand how you traverse multiple relationships at the
> > same
> > > > > time.
> > > > > >
> > > > > > Thanks,
> > > > > > Lincoln
> > > > > > _______________________________________________
> > > > > > Neo mailing list
> > > > > > User@lists.neo4j.org
> > > > > > https://lists.neo4j.org/mailman/listinfo/user
> > > > > >
> > > > > _______________________________________________
> > > > > Neo mailing list
> > > > > User@lists.neo4j.org
> > > > > https://lists.neo4j.org/mailman/listinfo/user
> > > > >
> > > > _______________________________________________
> > > > Neo mailing list
> > > > User@lists.neo4j.org
> > > > https://lists.neo4j.org/mailman/listinfo/user
> > > >
> > > _______________________________________________
> > > Neo mailing list
> > > User@lists.neo4j.org
> > > https://lists.neo4j.org/mailman/listinfo/user
> > >
> > _______________________________________________
> > Neo mailing list
> > User@lists.neo4j.org
> > https://lists.neo4j.org/mailman/listinfo/user
> >
> _______________________________________________
> Neo mailing list
> User@lists.neo4j.org
> https://lists.neo4j.org/mailman/listinfo/user
>
_______________________________________________
Neo mailing list
User@lists.neo4j.org
https://lists.neo4j.org/mailman/listinfo/user
