Question About Coming Up With Own Function for Distance Matrix (For Clustering)
It's trivial to see that you don't want to compute the distance matrix. Just compute the size of the entire matrix, even assuming zero memory overhead... 35 million x 35 million x 8 bytes per double /2 for optimizing symmetry. That is something like 5 Petabyte?

Forget anything that is not linear. Try to shrink your data first by weeding out the easy cases first: duplicates, single-time visitors where you have too little data to say much, etc.

Then begin experimenting with a manageable sample first. If you find something on a sample then it might be useable on the entire data, too. And if a method does not work in the samples it likely will not work on the entire data (but you'll have to wait much less to know it doesn't work).