One of the nicest UI's around when dealing with a large dataset is a good autocomplete. Facebook's search is a great example, same for Netflix, and recently Google launched "Google Instant", which returns search results as you type. Autocomplete can really complement hierarchical drill-down search (which is useful for discovery), as the goal of autocomplete is more for helping users find something they already know about with a minimum of effort.