What kind of index is Google using here?
johngunderman: I am 100% postulating here, but this is what seems most likely to me:Google is known for MapReduce. It seems like it would make regex searches manageable when put in such an algorithm. All Google would have to do would be to take whatever key system they use for their big-tables and use MapReduce to expand the regex over the keys. Then they just have to return the data associated with those keys.