Archive for the ‘Traversal’ Category

You Up To Improving Traversals/DSLs/OLAP in TinkerPop 3.2.0?

Wednesday, January 13th, 2016

Big ideas for Traversals/DSLs/OLAP in TinkerPop 3.2.0 by Marko A. Rodriguez.

Marko posted a not earlier today that reads in part:

There is currently no active development on TinkerPop 3.2.0, however, in my spare time I’ve been developing (on paper) some new ideas that should make traversals, DSLs, and OLAP even better.

Problem #1: The Builder pattern for TraversalSources is lame. [https://issues.apache.org/jira/browse/TINKERPOP-971]

Problem #2: It is not natural going from OLTP to OLAP to OLTP to OLAP. [https://issues.apache.org/jira/browse/TINKERPOP-570]

I mention this because it has been almost seven (7) hours since Marko posted this note and its not like he is covered up with responses!

Myself included but I’m not qualified to comment on his new ideas. One or more of you are. Take up the challenge!

TinkerPop, the community and you will be better for it.

Enjoy!

OhmDB

Friday, November 15th, 2013

OhmDB

Billed as:

The Irresistible Database for Java Combining Great RDBMS and NoSQL Features.

Supposed to appear by the end of November 2013 so it isn’t clear if SQL, NoSQL are about to be joined by Irresistable as a database category or not. 😉

The following caught my eye:

Very fast joins with graph-based relations

A single join has O(1) time complexity. A combination of multiple joins is internally processed as graph traversal with smart query optimization.

Without details, “very fast” has too wide a range of meanings to be very useful.

I don’t agree with the evaluation of Performance for RDBMS as “Limited.” People keep saying that as a truism when performance of any data store depends upon the architecture, data model, caching, etc.

I saw a performance test recently that depended upon (hopefully) a mis-understanding of one of the subjects of comparison. No surprise that it did really poorly in the comparison.

On the other hand, I am looking forward to the release of OhmDB as an early holiday surprise!

PS: I did subscribe to the newsletter on the theory that enough legitimate email might drown out the spam I get.

GraphHopper Maps…

Tuesday, July 23rd, 2013

GraphHopper Maps – High Performance and Customizable Routing in Java by Peter Karich.

From the post:

Today we’re proud to announce the first stable release of GraphHopper! After over a year of busy development we finally reached version 0.1!

GraphHopper is a fast and Open Source road routing engine written in Java based on OpenStreetMap data. It handles the full planet on a 15GB server but is also scales down and can be embedded into your application! This means you’re able to run Germany-wide queries on Android with only 32MB in a few seconds. You can download the Android offline routing demo or have a look at our web instance which has world wide coverage for car, bike and pedestrian:

GraphHopper Java Routing

The trip to the current state of GraphHopper was rather stony as we had to start from scratch as there is currently no fast Java-based routing engine. What we’ve built is quite interesting as it shows that a Java application can be as fast as Bing or Google Maps (in 2011) and beats YOURS, MapQuest and Cloudmade according to the results outlined in a Blog post from Pascal and with tests against GraphHopper – although OSRM is still ahead. But how can a Java application be so fast? One important side is the used algorithm: Contraction Hierarchies – a ‘simple’ shortcutting technique to speed up especially lengthy queries. But even without this algorithm GraphHopper is fast which is a result of weeks of tuning for less memory consumption (yes, memory has something to do with speed), profiling and tweaking. But not only the routing is fast and memory efficient also the import process. And it should be easy to get started and modify GraphHopper to your needs.

Contraction hierarchies are a very active area of graph research.

Contraction Hierarchies at Wikipedia has a nice coverage with a pointer to Robert Geisberger’s thesis, Contraction Hierarchies: Faster and Simpler
Hierarchical Routing in Road Networks
.

You may also be interested in:

Efficient Route Planning by Prof. Dr. Hannah Bast. A wiki for a 2012 summer course on route planning. Includes videos, slides, exercises, etc.

GraphPack

Wednesday, July 11th, 2012

GraphPack

From the webpage:

GraphPack is a network of autonomous services that manage graph structures. Each node in those graphs may refer to a node in another service, effectively forming a distributed graph. GraphPack deals with the processing of such decentralized graphs. GraphPack supports its own traverse/query language (inspired by neo4j::cypher) that can executed as transparently distributed traverses.

Amit Portnoy wrote about GraphPack on the neo4j mailing list:

The prototype, called GraphPack, has a very lite design, actual persistence and communication aspects can be easily pluged-in by injection (using Guice).

GraphPack enables transperantly distributed traverses (in a decentralized graph), which can be specified by Cypher-inspired traverse specification language.

That is, clients of a GraphPack service (which may have a graph the refer to other nodes in other GraphPack services) can write a cypher-like expressions and simply receive a result, while the actual implementation may make many remote communication steps. This is done by deriving a new traverse specification in every edge a long specified paths and sending this derived specification to the next node (in other words, the computation moves along the nodes that are matched by the traverse specification).

Sounds like there should be lessons here for distributed topic maps. Yes?

Conditional Traversals With Gremlin

Sunday, July 8th, 2012

Conditional Traversals With Gremlin by Max Lincoln.

An eligibility test that depends upon the ability to traverse to a particular node in the graph.

Reminded me of my musings on transient properties/edges.

Is not choosing an edge is the same thing as the edge not being present? For all cases?

Max mentions that NoSQL Distilled says this use case isn’t the typical one for graphs.

My suggestion is to experiment and rely on your own requirements and experiences.

Authors have to paint with a very broad brush or their books would all look like the Oxford English Dictionary (OED). Fascinating but not for the faint of heart.


BTW, when looking up the reference for the Oxford English Dictionary, the wikipedia reference mentioned that:

The Dutch dictionary Woordenboek der Nederlandsche Taal, which has similar aims to the OED, is the largest and it took twice as long to complete.

I don’t read Dutch but the dictionary is reported to be available for free at: http://gtb.inl.nl/

If you read Dutch, please confirm/deny the report. I would like to send a little note along the the OED crowd about access as a public service. (Like they would care what I think. 😉 Still, doesn’t hurt to comment every now and again.)

Jogger: almost like named_scopes

Sunday, March 4th, 2012

Jogger: almost like named_scopes

From the post:

We talked about graph databases in this and this blog post. As you might have read we’re big fans of a graph database called neo4j, and we’re using it together with JRuby. In this post we’ll share a little piece of code we created to make expressing graph traversals super easy and fun.

Jogger – almost like named_scopes

Jogger is a JRuby gem that enables lazy people to do very expressive graph traversals with the great pacer gem. If you don’t know what the pacer gem is, you should probably check pacer out first. (And don’t miss the pacer section at the end of the post.)

Remember the named_scopes from back in the days when you were using rails? Jogger gives you named traversals and is a little bit like named scopes. Jogger groups multiple pacer traversals together and give them a name. Pacer traversals are are like pipes. What are pipes? Pipes are great!!

The most important conceptual difference is, that the order in which named traversals are called matter, while it usually doesn’t matter in which order you call named scopes.

A nice way to make common traversals accessible by name.

Does the “order of calling” scopes in topic maps matter? At least for the current TMDM I think not because scopes are additive. That is the value covered by a set of scopes must be valid in each scope individually.