The problem of integrating services is becoming increasingly pressing. In large, open environments such as the Semantic Web, huge numbers of services are developed by vast numbers of different users. Imposing strict semantics standards in such an environment is useless; fully predicting in advance which services one will interact with is not always possible as services may be temporarily or permanently unreachable, may be updated or may be superseded by better services. In some situations, characterised by unpredictability, such as the emergency response scenario described in this case, the best solution is to enable decisions about which services to interact with to be made on-the-fly. We propose a method of doing this using matching technique to map the anticipated call to the input that the service is actually expecting. To be practical, this must be done during run-time. In this case, we present our structure-preserving semantic matching algorithm (SPSM), which performs this matching task both for perfect and approximate matches between calls. In addition, we introduce the OpenKnowledge system for service interaction which, using the SPSM algorithm, along with many other features, facilitates on-the-fly interaction between services in an arbitrarily large network without any global agreements or pre-run-time knowledge of who to interact with or how interactions will proceed. We provide a preliminary evaluation of the SPSM algorithm within the OpenKnowledge framework.