Maybe you can do it with storing on S3, and query via Amazon Athena en AWS Glue. Don't know about the performance though. Fuzzy search could otherwise be done with storing a soundex value of the fields you want to search on in a MongoDB. In DynamoDB you would need indexes on every searchable field if you want it to be efficient.
