A method of performing a search of heterogeneous data based on an input query includes: generating an index including at least two hash tables, where each hash table corresponds to a different data domain of the heterogeneous data and includes hash code sets, where at least one of the hash code sets is mapped to a hash code set of another one of the tables. The method further includes performing a hash on the input query to generate a hash code, by referring to the index, determining a first hash code set that the generated hash code belongs to, and determining a second hash code set that the determined first hash code set is mapped to, and providing at least one result based on the determined second hash code set.