Geo-proximity with sorted sets in Redis - Time & Space Complexity

Time Complexity: Geo-proximity with sorted sets

O(n)

Understanding Time Complexity

When we use Redis sorted sets to find nearby locations, we want to know how the time to get results changes as we add more places.

We ask: How does searching for nearby points grow when the list of locations grows?

Scenario Under Consideration

Analyze the time complexity of the following Redis commands.

GEOADD places 13.361389 38.115556 "Palermo"
GEOADD places 15.087269 37.502669 "Catania"
GEORADIUS places 15 37 200 km WITHDIST
    

This code adds two locations to a sorted set and then finds all places within 200 km of a point.

Identify Repeating Operations

Look for repeated work inside the GEORADIUS command.

• Primary operation: Checking each location's distance to the center point.
• How many times: Once for every location stored in the sorted set.

How Execution Grows With Input

As you add more places, Redis checks each one to see if it fits inside the radius.

Input Size (n)	Approx. Operations
10	About 10 distance checks
100	About 100 distance checks
1000	About 1000 distance checks

Pattern observation: The work grows directly with the number of locations you have.

Final Time Complexity

Time Complexity: O(n)

This means the time to find nearby places grows in a straight line with how many places you store.

Common Mistake

[X] Wrong: "Redis finds nearby places instantly no matter how many locations there are."

[OK] Correct: Redis must check each location's distance, so more places mean more work and more time.

Interview Connect

Understanding how Redis handles geo queries helps you explain how data size affects speed in real apps.

This skill shows you can think about performance, not just code.

Self-Check

"What if Redis used a spatial index to reduce the number of distance checks? How would the time complexity change?"

Practice

1. What does the Redis command GEOADD do in the context of geo-proximity with sorted sets?

easy

A. Returns the distance between two members

B. Finds all members within a radius from a point

C. Removes a location from the sorted set

D. Adds geographic locations (longitude, latitude) to a sorted set

Solution

1. Step 1: Understand the purpose of GEOADD

   The GEOADD command stores geographic coordinates (longitude and latitude) associated with a member in a sorted set.

2. Step 2: Differentiate GEOADD from other geo commands

   Commands like GEORADIUS find nearby members, while GEOADD adds new locations.

3. Final Answer:

   Adds geographic locations (longitude, latitude) to a sorted set -> Option D

4. Quick Check:

   GEOADD = Add locations [OK]

Hint: GEOADD always adds locations with coordinates [OK]

Common Mistakes:

• Confusing GEOADD with GEORADIUS
• Thinking GEOADD removes locations
• Assuming GEOADD returns distances

2. Which of the following is the correct syntax to find members within 5 kilometers of longitude 13.361389 and latitude 38.115556 using Redis GEO commands?

easy

A. GEOADD locations 13.361389 38.115556 5 km

B. GEODIST locations 13.361389 38.115556 5 km

C. GEORADIUS locations 13.361389 38.115556 5 km

D. GEORADIUSBYMEMBER locations 13.361389 38.115556 5 km

Solution

1. Step 1: Identify the command to find nearby members

   GEORADIUS is used to find members within a radius from given longitude and latitude.

2. Step 2: Check syntax correctness

   GEORADIUS locations 13.361389 38.115556 5 km correctly specifies key, longitude, latitude, radius, and unit.

3. Final Answer:

   GEORADIUS locations 13.361389 38.115556 5 km -> Option C

4. Quick Check:

   GEORADIUS + lon lat + radius + unit = correct syntax [OK]

Hint: Use GEORADIUS with lon lat radius unit for proximity search [OK]

Common Mistakes:

• Using GEOADD instead of GEORADIUS for searching
• Mixing GEORADIUSBYMEMBER syntax with coordinates
• Using GEODIST which calculates distance, not radius search

3. Given the following Redis commands executed in order:

GEOADD cities 13.361389 38.115556 Palermo
GEOADD cities 15.087269 37.502669 Catania
GEORADIUS cities 15 37 200 km WITHDIST ASC

What will be the output?

medium

A. [["Palermo", "56.4413"], ["Catania", "190.4424"]]

B. [["Catania", "56.4413"], ["Palermo", "190.4424"]]

C. ["Palermo", "Catania"]

D. Syntax error

Solution

1. Step 1: Add two cities with their coordinates

   Palermo and Catania are added with their longitude and latitude to the 'cities' key.

2. Step 2: Use GEORADIUS to find cities within 200 km of (15, 37) sorted by distance ascending

   Catania is closer (~56.44 km), Palermo is farther (~190.44 km), so output lists Catania first with distances.

3. Final Answer:

   [["Catania", "56.4413"], ["Palermo", "190.4424"]] -> Option B

4. Quick Check:

   GEORADIUS WITHDIST ASC sorts by nearest first [OK]

Hint: WITHDIST returns distances; ASC sorts nearest first [OK]

Common Mistakes:

• Confusing order of results when using ASC
• Ignoring WITHDIST option for distances
• Swapping longitude and latitude values

4. You run the command GEORADIUS cities 15 37 100 km WITHDIST but get no results, even though you know cities exist nearby. What is the most likely cause?

medium

A. The key 'cities' does not exist or is empty

B. The longitude and latitude are swapped

C. The radius is too small to include any city

D. WITHDIST option is not supported

Solution

1. Step 1: Check if the key exists and has data

   If the 'cities' key does not exist or is empty, GEORADIUS returns no results regardless of radius.

2. Step 2: Consider other causes

   Radius 100 km is reasonable, WITHDIST is supported, and longitude/latitude order is correct, so these are less likely.

3. Final Answer:

   The key 'cities' does not exist or is empty -> Option A

4. Quick Check:

   Empty key = no results [OK]

Hint: Check if key exists before searching [OK]

Common Mistakes:

• Assuming WITHDIST causes errors
• Swapping lat/lon but still expecting results
• Using too small radius without verifying data

5. You want to find all locations within 10 miles of 'Denver' stored in a Redis sorted set 'places'. Which command correctly finds these locations using the member name 'Denver' as center and returns results sorted from nearest to farthest?

hard

A. GEORADIUSBYMEMBER places Denver 10 mi WITHDIST ASC

B. GEORADIUS places Denver 10 mi WITHDIST ASC

C. GEORADIUSBYMEMBER places Denver 10 mi WITHDIST DESC

D. GEODIST places Denver 10 mi WITHDIST ASC

Solution

1. Step 1: Use GEORADIUSBYMEMBER to search by member name

   GEORADIUSBYMEMBER finds locations near a member's coordinates, here 'Denver'.

2. Step 2: Specify radius and unit, and sort ascending by distance

   10 miles radius with WITHDIST ASC returns nearby locations sorted nearest first.

3. Final Answer:

   GEORADIUSBYMEMBER places Denver 10 mi WITHDIST ASC -> Option A

4. Quick Check:

   GEORADIUSBYMEMBER + WITHDIST ASC = nearest first [OK]

Hint: Use GEORADIUSBYMEMBER for member-centered radius search [OK]

Common Mistakes:

• Using GEORADIUS with member name instead of coordinates
• Sorting DESC instead of ASC for nearest first
• Using GEODIST which returns distance between two members only