Project Overview

Developed a memory-efficient live tracking system for electric vehicle charging station availability using the Count-Min Sketch probabilistic data structure. The project addresses range anxiety and charging infrastructure availability challenges by providing real-time route planning with optimal charging stops while using 88% less memory than traditional tracking methods with only 1.91% false positive rate.

Motivation

The adoption of electric vehicles has been slowed by range anxiety and uncertainty about public charging infrastructure availability. As a Tesla owner, I have experienced these challenges firsthand and wondered whether improvements could be made to existing tracking tools. This project applies streaming algorithms and probabilistic data structures to create a scalable, memory-efficient solution that can track thousands of charging stations in real time.

Key Achievements

Memory-Efficient Tracking with Count-Min Sketch

Implemented a Count-Min Sketch (CMS) based tracking system that achieves 88% memory reduction compared to traditional dictionary-based approaches with only 1.91% false positive rate. The CMS maintains a compact two-dimensional array of counters indexed by multiple hash functions, allowing us to track charging station occupancy across all timeslots without storing full per-station histories.

Real-Time Route Planning

Developed an intelligent route planning system that integrates with the Google Maps API to find optimal charging stops along a route. The system considers current location, destination, desired charge at arrival, and current battery level to select the best charging stations. It uses Haversine distance calculations to identify the 5 closest candidates along the route and greedily picks the furthest available station that satisfies availability constraints.

Statewide Coverage

Tracks 841 Level 3 DC Fast Charging stations across the entire state of Texas. Each station is divided into 10-minute timeslots to match realistic charging session durations. The system simulates a live environment by initializing station occupancy with a normal distribution (mean 50% capacity, standard deviation 20%) and handling charging sessions of 10, 20, or 30 minutes.

Technical Implementation

Count-Min Sketch Algorithm

The Count-Min Sketch is a probabilistic data structure for frequency estimation in data streams. Our implementation uses:

• Multiple Hash Functions: 8 independent hash functions to distribute updates across counters
• Width Parameter: 20,000 counters per row to minimize collision probability
• Minimum Estimation: Takes minimum of hashed counters to limit errors to false positives only
• Streaming Updates: Handles plug-in/unplug events in constant time O(k) where k is number of hash functions

Unlike traditional Count Sketch which takes the median, we use the minimum to ensure errors are only false positives (reporting a station as occupied when it's available) rather than false negatives (reporting as available when occupied), which would be more harmful to user experience.

Route Planning Algorithm

The system follows these steps to plan optimal routes with charging stops:

1. Input Collection: User provides current location, destination, current charge, and desired arrival charge
2. Route Generation: Google Maps API generates optimal driving route
3. Candidate Selection: Identifies 5 closest charging stations to the route using Haversine distance
4. Availability Check: Queries CMS for each candidate's availability in upcoming timeslots
5. Greedy Selection: Picks furthest available station along route (maximizes progress toward destination)
6. Fallback Strategy: If all stations full, checks 10-minute wait increments up to 30 minutes
7. Expansion: If no stations available within 30 minutes, expands search to next 5 closest stations
8. Reservation: Inserts charging session into selected timeslot in CMS

Simulation Environment

To test the system in a realistic scenario, we implemented a comprehensive simulation:

• Initial State: All 841 stations initialized with normal distribution (μ=50%, σ=20%)
• Charging Sessions: Randomly assigned 10, 20, or 30-minute durations
• Streaming Data: One continuous stream of events rather than batch processing
• Real-Time Updates: CMS updated as charging events occur throughout simulation
• Error Accumulation: Long stream captures any accuracy degradation as data structure fills

Experimental Results

Performance Comparison

We compared our CMS implementation against a baseline dictionary approach that stores full state for every charging station and timeslot. The following configurations were tested:

Configuration	Hash Functions	Width	Memory Ratio	FPR (%)
Baseline (Dictionary)	N/A	N/A	100%	0%
CMS Config 1	4	20,000	5.93%	7.84%
CMS Config 2	4	30,000	8.89%	3.29%
CMS Config 3	8	15,000	8.89%	5.08%
CMS Optimal	8	20,000	11.86%	1.91%
CMS Config 5	16	10,000	11.84%	6.24%
CMS Config 6	16	15,000	17.76%	0.99%

The optimal configuration (8 hash functions, width 20,000) achieves our target of 75% memory reduction with less than 5% accuracy loss, using only 11.86% of baseline memory with 1.91% false positive rate. This represents an 88% memory savings while maintaining over 98% accuracy.

Interactive Route Planning Application

Beyond the core CMS implementation, we developed a user-facing application with an interactive frontend. Users can input their trip details and receive real-time route suggestions with optimal charging stops. While the interface demonstrates the practical application of the algorithm, it has some limitations in less densely populated areas of West Texas where charging infrastructure is sparse.

Comparison to Existing Approaches

Most existing EV charging solutions focus on predicting future usage patterns rather than managing live availability:

• Predictive Models: LSTM-based approaches predict occupancy at future time horizons
• Machine Learning: Data-driven frameworks forecast waiting times using historical data
• Our Approach: Maintains lightweight, real-time view of actual availability using streaming algorithms
• Advantage: Memory-efficient tracking of current state rather than probability estimates

Learning Outcomes

• Deep understanding of probabilistic data structures and their tradeoffs
• Practical application of streaming algorithms to real-world infrastructure problems
• Experience with spatial algorithms (Haversine distance, route optimization)
• Integration with external APIs (Google Maps) for practical applications
• Performance analysis and parameter tuning for algorithmic systems
• Understanding when approximate solutions are preferable to exact ones