I'm definitely not a Titan/Janus or ES expert so I'm not sure how it works.  But I imagine if you had an index by label, timestamp, asc, then you would only ever hit the tip of the index g.E().hasLabel('label').has('timestamp', lt(timestamp)). That should be very fast. Of course you would have to know all of the edge labels in advance. But again there's an opportunity for parallelism by label.