Matching millions of people: k-d tree or locality-sensitive hashing?

Question

I am looking for a performant algorithm to match a large number of people by location, gender and age according to this data structure:

• Longitude (denotes the persons location)
• Latitude (denotes the persons location)
• Gender (denotes the persons gender)
• Birthdate (denotes the persons birthdate)
• LookingForGender (denotes what the gender the person is looking for)
• LookingForMinAge (denotes what minimum age the person is looking for)
• LookingForMaxAge (denotes what maximum age the person is looking for)
• LookingForRadius (denotes what maximum distance the person is looking for)
• Processed (denotes which other persons this person has already processed)

For any person P the algorithm should return candidates C for which applies:

• Gender of C must be equal P.LookingForGender
• Gender of P must be equal C.LookingForGender
• Birthdate of C must be between P.LookingForMinAge and P.LookingForMaxAge
• Birthdate of P must be between C.LookingForMinAge and C.LookingForMaxAge
• Lat/Long distance between P and C must be smaller or equal P.LookingForRadius
• Lat/Long distance between P and C must be smaller or equal C.LookingForRadius
• Processed of P must not contain C

The algorithm should return the first 100 candidates C in order of distance (Lat/Long). The algorithm should be optimized for both search and updates because people may change their location often.

My current thinking is that k-d tree could be more suitable than locality-sensitive-hashing for these needs and that I should go into this direction.

What would be your advise for me? What should I look for? What risks do you see?

Thanks!

Update:

• Do I prefer to sacrifice space complexity for better time complexity? Yes I prefer to sacrifice space complexity. However I prefer to have a O(log n) solution that I actually understand and can maintain rather than a O(1) solution that I cannot grasp :)
• Does the data fit into main memory? No it does not. The data will be distributed across different nodes of a distributed document database (Azure Cosmos DB SQL API).
• Do you want exact results or are approximate results? Approximate results are OK however age/gender should be filtered exact.
• Added "Processed" to the algorithm, sorry for having missed that!
• How often do people change their location? Users will change their location whenever they start the app and look for candidates. Daily active users will therefore change their location one or multiple times a day. A location change may however be minor so just a few kilometers. From 100 app downloads, 15 users will use the app once or more a a month, and 3 users will use it once or more daily.

Answer 1

Here is some info by Microsoft how to use their spatial indexing ('spatial' is the keyword you want to search for).

The query you are looking for is a k-nearest neighbor query (kNN Search) with k=100.

If you want to serialize the index yourself, have a look at R+tree or R*trees, they are quite good for page based serialization. There are lots of open source example for these trees. Here is my own implementation in Java, unfortunately it does not support Serialization.

About the other indexes:

• I have no experience with LHS, so it can't say much about it. One thing I know though, since it's internally a HashMap, you need to take special care to make it scalable with large amounts of data. This definitely increases complexity. Another problem, I'm not sure LSH is good for kNN search, you will have to look that up.
• KD-trees are very simply and should to the job, but are bad for serialization and can have large memory overhead unless you implement a version that can have more than one entry in each node. KD-Trees can also degenerate when updated often, so they may need rebalancing.
• Otherwise I would suggest quadtrees, for example the qthypercube2. They are also quite simple, very fast in memory, and very well suited for frequent updates, especially if the entries move only a small distance.