A Short Survey on Process Model Similarity <s> Process Model Search and Indexing <s> The proliferation of information housed in computerized domains makes it vital to find tools to search these resources efficiently and effectively. Ordinary retrieval techniques are inadequate because sorting is simply impossible. Consequently, proximity searching has become a fundamental computation task in a variety of application areas. Similarity Search focuses on the state of the art in developing index structures for searching the metric space. Part I of the text describes major theoretical principles, and provides an extensive survey of specific techniques for a large range of applications. Part II concentrates on approaches particularly designed for searching in large collections of data. After describing the most popular centralized disk-based metric indexes, approximation techniques are presented as a way to significantly speed up search time at the cost of some imprecision in query results. Finally, the scalable and distributed metric structures are discussed. <s> BIB001 </s> A Short Survey on Process Model Similarity <s> Process Model Search and Indexing <s> Finding useful services is a challenging and important task in several applications. Current approaches for services retrieval are mostly limited to the matching of their inputs/outputs. In this paper, we argue that in several applications (services having multiple and dependent operations and scientific workflows), the service discovery should be based on the specification of service behavior. The idea behind is to develop matching techniques that operate on behavior models and allow delivery of approximate matches and evaluation of semantic distance between these matches and the user requirements. To do so, we reduce the problem of behavioral matching to a graph matching problem and adapt existing algorithms for this purpose. To validate our approach, we developed a BPEL ranking platform that allows to find in a service repository, a set of service candidates satisfying user requirements, and then, to rank these candidates using a behavioral-based similarity measure. <s> BIB002 </s> A Short Survey on Process Model Similarity <s> Process Model Search and Indexing <s> Due to the increasing adoption of business process management and the key role of process models, companies are setting up and maintaining large process model repositories. Repositories containing hundreds or thousands of process models are not uncommon, whereas only simplistic search functionality, such as text based search or folder navigation, is provided, today. <s> BIB003 </s> A Short Survey on Process Model Similarity <s> Process Model Search and Indexing <s> With the increasing influence of Business Process Management, large process model repositories emerged in enterprises and public administrations. Their effective utilization requires meaningful and efficient capabilities to search for models that go beyond text based search or folder navigation, e.g., by similarity. Existing measures for process model similarity are often not applicable for efficient similarity search, as they lack metric features. In this paper, we introduce a proper metric to quantify process similarity based on behavioral profiles. It is grounded in the Jaccard coefficient and leverages behavioral relations between pairs of process model activities. The metric is successfully evaluated towards its approximation of human similarity assessment. <s> BIB004
One of the applications of process similarity lies in finding all process models in a process model collection that are sufficiently similar to a so-called "search process model". Indexing techniques are required for implementing such a search efficiently. Pairwise computation of the distance of process models allows comparing a given query with models from a process repository, and thus, to find similar models. They also need to be ranked BIB002 . However, traditional indexes cannot be applied as the notion of pairwise similarity does not yield any ordering of process models.There are two competing approaches to indexing process models: (1) indexing process model elements   ; and (2) indexing complete process models, provided a similarity metric is used that satisfied the triangle inequality property BIB004 . The first approach is based on breaking each process model up into parts on which existing indexing techniques can be applied. In particular MTree  and B+ tree  indexing techniques have been used. The types of parts that have been used include: the labels of the tasks in the process models, paths of subsequent tasks and more complex constructs such as choices between tasks or parallel tasks. Using these indexing techniques, the search for similar models is executed by breaking the search model up into parts (e.g. only selecting the task labels) and then using the index to find the process models that have sufficiently many similar parts (e.g. similar task labels). The work on process model search and indexing is related to general graph search and its application to e.g. face recognition and fingerprint search. The second approach uses metric spaces BIB001 to tackle this problem, as they facilitate efficient search in the absence of coordinates and ordering of elements if the distance function, beside the properties mentioned above, satisfies the triangle inequality. This property allows determining minimum and maximum distance of two process models without computing the distance function, if their pairwise distance to a third model is given. Such transitivity improves search efficiency and can be applied to both structural BIB003 and behavioural BIB004 process model similarities.