Recent research has provided a framework for measuring similarity of incomplete database instances without considering the presence of complete key information; the aim is to identify similar tuples across database instances by purely relying on the tuples themselves. The framework proposes a straight forward approach for an approximate algorithm to reach sufficiently good results with computational efficiency. Introducing more advanced methods for nearest neighbour searches, such as locality sensitive hashing (LSH), is an opportunity to build on top of the original framework and further enhance the already achieved results. Hence, this paper introduces the appropriate definitions and proves the performance of an LSH integrated framework based on extensive experiments. Further, using an LSH integrated approach broadens the application space of the framework for more types of data as well as detecting partial instance matches, which highlights how promising this approach is for future work.