please see: Titan Limitations
Edge Retrievals are not O(1)
Retrieving an edge by id, e.g tx.getEdge(edge.getId()), is not a constant time operation. Titan will retrieve an adjacent vertex of the edge to be retrieved and then execute a vertex query to identify the edge. The former is constant time but the latter is potentially linear in the number of edges incident on the vertex with the same edge label.
This also applies to index retrievals for edges via a standard or external index.
The reason for this behaviour is the way in which Titan stores vertices and edges (see Data Model). Only vertices can be accessed directly (O(1)).
Bottom line: Even if you have an Edge index for properties, Titan still has to iterate over all adjacent vertices to identify the edges by id.
Try to change your schema, so that you can query vertices from where you can continue the traversal.
Cheers, Daniel