Some tips for coming up with a project:
 Find a big data set and implement an algorithm from class
on that data set. If you want to do more:
Compare the algorithm from class to
a linear time algorithm? Try a few versions of the sublinear time
algorithm? Invent a new version of the class algorithm and try it out?
 Can you get a better dependence on n or epsilon for
some algorithm in class? (check with me before you work too hard on that..
I may already know a better bound) Can you get a better lower bound?
Can you get a better dependence for a special class of inputs?
(say subgraphs of the grid? planar graphs? expanding graphs? random graphs?)

What if you add a stronger assumption on the form of the input?
For example, maybe the input is a set of points in sorted order?
(in this case, you can do binary search and a number of other things)
What can you do that is interesting in this case for other
problems that we considered in class?
Another way of viewin this question  what if I give you access
to some sort of famous data structure for the input (say range queries,
nearest neighbor queries, or something like that)  can you do anything
interesting with that?

What if I give you a weaker assumption on the form of the input  maybe
you can only get random examples of the input rather than query access.
Can you solve any interesting property testing problems in this case?

Most of our distance related results are in Hamming distance or L1 distance.
Is it easier or harder for a different distance metric  e.g. EMD, or
any other favorite distance?
e.g., are there sublinear time tests for whether the data is well approximated by a histogram under EMD (as opposed to L1,L2 distances, which has been studied).