All projects
Solo developer Jun 2021
Social Network Query Engine
A C++ engine for querying social-network relationships, redesigned with the right data structures to drop runtime from quadratic to linear.
- C++
- Data Structures
- Red-Black Trees
- Graphs
Problem
Answering relationship queries over a social graph is easy to get working and hard to get fast. A straightforward implementation re-scans data on every query and degrades to quadratic time as the network grows.
What I built
A C++ social-network query engine that answers relationship and connectivity queries efficiently by choosing data structures that match the access patterns.
How it works
- Red-black trees for balanced, logarithmic lookups of members and their attributes.
- Adjacency lists to represent the graph compactly and iterate neighbors cheaply.
- Query paths restructured so repeated work is eliminated rather than recomputed.
Impact / results
- Improved overall runtime from quadratic to linear on the target workloads.
- Kept memory usage proportional to the graph rather than the query volume.
What I’d do next
- Add caching for hot queries and benchmark against a real graph database.
- Support incremental updates so the structures stay warm as the network changes.