graphs databases like Neo4j are a very good fit, especially as you can add different indexing schemes dynamically as you go. Typical stuff you can do on your base data is of course 1D indexing (e.g. Timline or B-Trees) or funkier stuff like Hilbert Curves etc, see Nick’s blog. Also, for some live demonstration, look at the AWE open source GIS desktop tool here, the underlying indexed graph being visible around time 07:00 .