Map IP Addresses to cities

Question

Can you suggest the most efficient algorithm to solve the below problem:

If there are multiple IP addresses, how would you classify them into different cities that they belong to. If range for New York is: 134.123.65.5 - 135.123.124.21. and then the IP address is 134.126.232.12 does not belong to NY and IP address 134.123.89.45 does belong to NY.

My approach :

1. Convert each range in the following format : 134*(256^3) + 123*(256^2) + 65*(256^1) + 5*(256^0)
2. Store above value in a TreeMap with mapping - (ConvertedIpAddress, CityName)
3. When given a query, convert address to a similar format and find map.floorKey(query)

Please tell me if approach is alright or if better approach exists.

Answer 1

Using a tree is already quite efficient since the resulting complexity to find one IP is O(log n) where n is the number of ranges (assuming there is no overlapping). The overall complexity is O(m log n) for m IPs.

Since ranges are likely not dynamically modified, a faster solution is to use a prebuilt sorted array. Sorted arrays are especially faster for few ranges and should be faster even for a relatively big amount of ranges since they are contiguous and more compact in memory.

Another probably faster solution is to use lookup-tables (LUT). Indeed, LUT accesses are in O(1) (for a given IP). You can build a LUT with 65536 items for the first half part of the IP (x*256+y for x.y.z.w). For each LUT item, you can store an ID to another array storing informations about the range structure. If there is multiple ranges for the given LUT item, then you can iterate over them or use another LUT if there is a large amount of cities with the same IP upper part. If the number of cities is small (eg. <256), then the LUT solution will be significantly more efficient because ID can be stored in 1 octet each. The resulting complexity should be about O(m).

If you have a lot of IPs and cities, the best solution is probably to sort cities ahead of time once (if possible), then sort the all the IPs, and then iterate over the IPs and cities at the same time like a merge does. This algorithm runs in O(n + m) where n is the number of cities (or ranges) and m is the number of IPs. This solution should be much faster than using LUTs for a big amount of cities.