Which Java data object to use for multidimensional range matching?

Project Background: I am writing a map tile overlay class for java that can use gdal2tile.py tiles. Basically I will end up with thousands of jpg files that are in a file structure like "Zoom Level/X coordinate/Y coordinate" The coordinates are ints but will not necessarily start at 0 or 1. I will have to search for tiles that are within a certain range to find out which ones I need to render.

My Problem: I tried iterating using the file structure itself but it is wicked slow (not surprising). I tried iterating using an ArrayList of strings of the file structure and .contains() but it seems to be even slower (not too surprising). Optimally I would like to use a data structure that would let me choose a range on multiple dimensions so that I can call something like.

Tiles.getWhere(Zoom Level,min X,max X,min Y,maxY);

I assume that some sort of Collection or TreeMap would be the right choice but I'm not experienced e开发者_运维问答nough with Java to know for sure and I'd prefer not to have to benchmark a lot of different approaches.

I could use SQLite to do it but that seems like overkill.

My Question: What is the most efficient way to check for the existence of datasets given multiple dimensional constraints?

---

May be you are looking for a map with multiple keys.

Commons-collections provides a map with multiple lookup keys:

http://commons.apache.org/collections/apidocs/org/apache/commons/collections/map/MultiKeyMap.html

a map guarantees a O(1) insertion and O(1) selection timings.

---

Thinking of your problem I could find out three directions to which you could aim your search next (this is not a hand-by-hand guide but rather a out-of-the-box brain opener for a stucked situation you have faced):

1) Usage of Java built in structures. Yes, indeed, a list is the worst case of a searching method. A Map, as the name suggests, is far more convenient for maps. It is not only the name, but the indexing to a Map is signifigantly less time consuming compared to a List. You can imagine your map as a cube, where you have to handle about half of the dots inside it, if you use List and probably only a narrow layer of it when you search by indexing a Map. There is a magnitude of difference. So, my answer here: Map is a key word towards the correct direction (assuming you want to do it in this way after reading on my answer).

2) Usage of a Map Server solution. This is probably too far from your approach, but entire frameworks are made for solving your type of question. An example is GeoServer. It has a ready made solution for the entire problem. It is a stable solution for the great big problem possibly in your hand: showing a map to a user from a source.

3) Sticking to the GDAL framework you were using, you could select slightly different py-file, like gdal_proximity.py and - wow! - you have a searching possibility in your hand! This particular one searches by a center point and a distance, but will do the stuff you need =)

There is a starting point, how I would make it. Could this serve for something?

---

Sounds to me like you are looking for something like an Interval Tree.

http://en.wikipedia.org/wiki/Interval_tree

I have implemented one of these in the past but only in one dimension. The Wikipedia reference mentions extensions to more dimensions.

Paul