title: MAR: A structure-based search engine for models
authors: José Antonio Hernández López Jesús Sánchez Cuadrado
text: 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
    Universidad de Murcia
  
  joseantonio.hernandez6@um.es
  
  
  Universidad de Murcia
  jesusc@um.es
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  The availability of shared software
  models provides opportunities for reusing, adapting and learning from
  them. Public models are typically stored in a variety of locations, including
  model repositories, regular source code repositories, web pages, etc. 
  To profit from them developers need effective search mechanisms to locate the models relevant
  for their tasks. However, to date, there has been little success in creating a generic and efficient search engine specially tailored to the modelling domain. 
  
  
  
  In this paper we present MAR, a search engine for models. MAR is generic 
  in the sense that it can index any type of model if its meta-model is known. MAR uses a query-by-example approach, that is, it uses example
  models as queries. The search takes the model structure into account using the notion of bag of paths, which encodes the structure of a model using paths between model elements and is a representation amenable for indexing.
  MAR is built over HBase using a specific design to deal with large repositories.
  Our benchmarks
  show that the engine is efficient and has fast response times
  in most cases.
  We have also evaluated the precision of the search engine by creating
  model mutants which simulate user queries. 
  A REST API is available to perform queries and an Eclipse plug-in allows end users to connect
  to the search engine from model editors. 
  We have currently indexed more than 50.000 models of different kinds, including
  Ecore meta-models, BPMN diagrams and UML models. MAR is available at <http://mar-search.org>.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  <ccs2012>
  <concept>
  <concept_id>10002951.10003317.10003365</concept_id>
  <concept_desc>Information systems Search engine architectures and scalability</concept_desc>
  <concept_significance>300</concept_significance>
  </concept>
  <concept>
  <concept_id>10011007.10010940.10010971.10010980.10010984</concept_id>
  <concept_desc>Software and its engineering Model-driven software engineering</concept_desc>
  <concept_significance>500</concept_significance>
  </concept>
  <concept>
  <concept_id>10011007.10011006.10011060.10011061</concept_id>
  <concept_desc>Software and its engineering Unified Modeling Language (UML)</concept_desc>
  <concept_significance>300</concept_significance>
  </concept>
  <concept>
  <concept_id>10011007.10011006.10011072</concept_id>
  <concept_desc>Software and its engineering Software libraries and repositories</concept_desc>
  <concept_significance>500</concept_significance>
  </concept>
  </ccs2012>
  
  
  [500]Software and its engineering Model-driven software engineering
  [300]Software and its engineering Unified Modeling Language (UML)
  [300]Information systems Search engine architectures and scalability
  [500]Software and its engineering Software libraries and repositories
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  MAR: A structure-based search engine for models
      Jesús Sánchez Cuadrado
      December 30, 2023
  ===============================================
  
  
  
  
  
  § INTRODUCTION
  
  
  
  
  
  
  
  Model repositories are essential for the success
  of the MDE paradigm <cit.>, since they have the potential to
  foster communities of modellers, improve learning by letting
  newcomers explore existing models and provide high-quality models which can be reused.
  
  
  
  There are several model repositories available <cit.>,
  some of which offer public models. 
  For instance, the GenMyModel[<https://www.genmymodel.com/>] cloud modeling service features a public
  repository with thousands of available models. To profit from them
  advanced search mechanisms are needed <cit.>.
  In particular, a search engine has the potential to 
  aggregate models from several sources, including 
  model repositories (e.g., the AtlanMod Zoo[<https://web.imt-atlantique.fr/x-info/atlanmod/index.php?title=Zoos>]) and code repositories (e.g., GitHub <cit.>), thus
  boosting the user chances to retrieve the desired results easily.
  Despite some efforts <cit.> there are still open challenges,
  which includes indexing models efficiently for search and retrieval, taking the model structure into account in the search, and
  aggregating models of different types and from different sources under a single plataform.
  
  
  
  
  
  
  
  
  
  
  
  In this paper we present , a search engine specifically designed for models. is generic, in the sense that it can handle any EMF model <cit.>
  regardless of its meta-model. An important challenge is how
  to encode the structure of the model in a manner that can
  be stored in an inverted index <cit.> (a map from items to documents containing such item). To tackle this we encode
  a model by computing paths of 
  maximum, configurable length n between objects and attribute values
  of the model.
  
  
  
  
  At the user level, our system employs a query-by-example approach in which the user
  just needs to create model fragments using a regular modelling tool. The system
  extracts the paths of the query and access the inverted index to perform the
  scoring of the relevant models.
  
  
  We have evaluated the precision of for finding relevant models by automatically deriving queries using mutation operators,
  obtaining good results. Moreover, we evaluate its performance  obtaining results that show its practical applicability.
  We also discuss several applications of beyond its main use case, that is, searching for models stored in repositories. Notably
  we have used MAR for meta-model classification
  showing that using a simple k-Nearest Neighbours approach can reach similar precision as state-of-the-art methods <cit.>.
  Finally, has currently indexed more than 50.000 models
  from several sources, including Ecore meta-models, UML models and BPMN models. is freely accessible at <http://mar-search.org>
  through a REST API, a web interface and an Eclipse plug-in.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  Organization. 
  Section <ref> presents an overview of our approach and the
  running example. The formal model of the search process is presented in Sect. <ref>, whereas Sect. <ref> describes the practical aspects in the design of our search engine. Section <ref> introduces applications of a search engine, while Sect. <ref> reports the results of the
  evaluation. Finally, Sect. <ref> discusses the related work and Sect. <ref> concludes.
  
  
  
  
  § OVERVIEW
  
  
  
  
  
  The design of a search engine for models requires considering several aspects <cit.>. The search should be meta-model based in the sense that only models conforming to the meta-model of interest are retrieved. 
  There exists search engines for specific modelling languages (e.g., UML <cit.> and WebML <cit.>), but the diversity of modelling approaches and the emergence of DSLs suggests that search engines should be generic.
  Moreover, the nature of the search process requires an algorithm to perform inexact matching because the user is interested in obtaining several search results, using
  some ranking mechanism to sort the results according to their relevance.
  A search engine requires an indexing mechanism for processing and storing the available models in a manner which is adequate for efficient look up.
  
  In addition, a good search engine should be able to handle large repositories of models
  while maintaining a good performance as well as search precision.
  Another aspect is how to present the results to the user. This requires considering the
  integration with existing tools and building dedicated web services.
  
  
  
  
  overview-usage0.5Usage and components of the search engine.
  
  Our design addresses these concerns by including the following features, which are depicted in Fig. <ref>.
  
      
    * Query by example. The user interacts with the system using a query mechanism  based on examples. 
      The user creates an example model containing elements that describe
      the expected results.
      The system receives the model (and the name of its meta-model) to drive the search and to present a ranked list of results.
      
      
    * Frontend. The functionality is exposed through a REST API which can be used directly
      or through some tool exposing its capabilities in a user friendly manner. In particular, we have implemented a web interface and an Eclipse plug-in which integrates the
      search engine with Ecore editors.
  
      
      
      
      
      
      
      
    * Indexing. An inverted index is populated with models crawled from existing software
            repositories and datasets (e.g., Github, GenMyModel). Implementation-wise, it is an HBase database,
            which stores the information needed for the search. 
            
            
  
      
    * Scoring algorithm. The results are obtained by accessing the index to collect 
            the relevant models among those available. They are ranked according to a scoring function and returned to the
            user. The IDE or the web frontend are responsible for presenting the results in
            a user-friendly manner.
  
      
    * Generic search. The search is meta-model based because it takes into account the structure given by the meta-model, but the engine is generic, in the sense that it can index and search models conforming to any EMF meta-model. 
  
  
  
  
  
  
  
  
  
  Running example. 
  Let us consider the task of searching
  for UML state machine models using a search engine, like , which has indexed thousands of UML models.
  An excerpt of the UML meta-model for state machine diagrams is shown in Fig. <ref>.
  Let us suppose that has indexed a state machine which represents making or receiving mobile phone calls, 
  similar to the diagram shown in Fig. <ref>(left). 
  A user interested in models representing phone calls may create a query like the one in Fig. <ref>(right).
  The query is different since it models only the reception of calls. The modelling style is also different because in the query the system waits for the incoming call in Wait and then transitions to Waiting to pick up, whereas in Fig. <ref>(left)
  the system automatically transitions to Talking when there is an incoming call.
  A search engine for models should be able to match attribute values (e.g., strings) and to detect which structures of the model match to which structures of the query,
  and provide a relevance score based on this. 
  
  statemachine-metamodel0.5Excerpt of the UML state machine meta-model.
  
  
  
  
  
  example_models0.5Repository model (left) and example query (right)
  
  
  
  
  
  
  
  
  
  
  
  
  
  § RETRIEVING MODELS
  
  
  
  Our approach is based on the conceptual model typically used to address text retrieval problems <cit.>,
  but it is adapted to cover the specific case of model retrieval in which the structure of models
  plays an important role. In this section, we present our approach formally, and the next
  section describes the practical aspects.
  
  
  
  
  
  Model retrieval. We define the model retrieval problem as follows: let ℳ = {m_1,…,m_t} be a set of models which conform to the same meta-model and a query q made by a user (which in our case is a model conforming to the same meta-model as the models in ℳ). We are interested in computing R(q)⊂ℳ the set of relevant models to the user who defined the query q. However, it is not realistic to find exactly that set, so typically an approximation R'(q) is considered. In particular, using a ranking approach, we have:
  
      R'(q) = {m ∈ℳ |r(q,m) ≥θ},
  
  where r(·,·) is called the ranking function and
  θ is a threshold. In practice, the user is given a list of models sorted decreasingly by the scores of each model, and the threshold is implicitly defined by the user who browses the list in descending order until she or he considers appropriate. A good ranking function should rank all relevant documents on top of all non-relevant ones.
  
  Our approach has two main ingredients, which are described in the rest of the section. First,
  encoding the set ℳ into a suitable type of document which represents the structure in a compact manner. 
  We use the notion of graph paths to transform the repository into a set of bags of paths. Second,
  choosing a scoring function to rank the models in the repository with respect to the query.
  
  
  
  
  
  
      
  
  
      
  
  
  
  
  
  
  
  
  
  
   §.§ Models as bags of paths
  
  
  
  
  
  A key element in our approach is the ability to perform fast, approximate structural matching.
  As noted in <cit.>, taking the structure of models into account is essential
  to precisely compare models in scenarios like search, clustering, clone detection, classification, etc.
  
  
  
  Graph construction.
  Our approach is based on representing the structure of a model as a bag of paths.
  To this end, we first define the structure of the graph from which paths will be extracted.
  
  
  
  A directed multigraph is a tuple (V,E,f) where V is a nonempty finite set whose elements are called vertices, E is a finite set whose elements are called edges and f:E ⟶ V × V is a function which defines the source and target vertex of an edge.
  The edges e_1 and e_2 are called multiple edges (or multi-edges) if and only if f(e_1)=f(e_2).
  
  
  
  
  
  A labeled directed multigraph is a tuple of the form G=(V,E,f,M_V,M_E) where
  
  
      
    * (V,E,f) is a directed multigraph.
      
    * M_V = {μ_V:V ⟶ L: 0<|L|<∞} is a set of vertex labeling functions.
      
    * M_E = {μ_E:E ⟶ L: 0<|L|<∞} is a set of edge labeling functions.
  
  
  
  
  In particular we are interested in a labeled directed multigraph G=(V,E,f,{μ^1_V,μ^2_V},{μ_E}) with three labeling functions: 
  
      
    * μ^1_V: V ⟶{attribute,class} which indicates if a vertex represents an attribute value or the class name of an object.
      
    * μ^2_V: V ⟶ L_V = L_A ∪ L_C maps vertices to a finite vocabulary which has two components:
      
          
          
          
    * L_A corresponds to the set of attribute values 
          in the model. 
          Given v∈ V, if μ^1_V(v) = attribute then μ^2_V(v) ∈ L_A.
          
    * L_C corresponds to the set of names of the different classes. Given v∈ V, if μ^1_V(v) = class then μ^2_V(v) ∈ L_C.
      
      
    * μ_E :E ⟶ L_E= L_R ∪ L_AR maps edges to a finite vocabulary which has two components:
      
          
    * L_R corresponds to the set of names of the different references. Given e∈ E where f(e) = (v,w), if μ^1_V(v) = class and μ^1_V(w) = class then μ_E(e)∈ L_R.
          
    * L_AR corresponds to the set of names of the different attributes. Given e∈ E where f(e) = (v,w), if μ^1_V(v) = class and μ^1_V(w) = attribute or μ^1_V(w) = class and μ^1_V(v) = attribute then μ_E(e)∈ L_AR.  
      
  
  
  As can be noted, we explicitly consider two types of nodes: attribute
  values and class names of individual objects (which will be referred to as “object class” nodes for brevity). The aim is to
  be able to construct paths between the model elements which carry
  the meaning of the model. For instance, the value Waiting of the State.name attribute would yield a node,
  and each object of type State would yield another node
  labeled as State.
  The construction of the graph is relatively straightforward,
  and we do not detail the algorithm for brevity.
  
  
  Fig. <ref> shows an excerpt of the graph
  that is obtained for the query model shown in Fig. <ref>(right). 
  There are explicit edges for both references and attributes.
  Nodes associated
  with objects classes are depicted as rounded rectangles, while nodes
  associated with attributes are depicted as ovals. 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  multigraph0.5Excerpt of the multigraph for Fig. <ref>(right).
  
  
  
  
  
  
  
  
  
  
   
  
  
  
  Bag of paths.
  In our approach a bag of paths (BoP) refers to the paths between each
  vertex of the multigraph to another one and the singleton paths with just one vertex. This is defined more formally 
  in the following.
  
  
  
  
  
  
  
  Let us have G=(V,E,f,{μ^1_V,μ^2_V},{μ_E}). A bag of paths for G is a multiset BoP whose elements are of the form:
  
  
      
    * (μ^2_V(v)) where v ∈ V or
      
    * (μ^2_V(v_1),μ_E(e_1),…,μ^2_V(v_n-1),μ_E(e_n-1),μ^2_V(v_n)) where
      
          
    * n ≥ 2
          
    * (v_1,…,v_n) a path of length n-1, i.e. a sequence of vertices where, for all 1≤ j≤ n-1, f(e_j) =(v_j,v_j+1).
      
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  This definition of BoP does not enforce which paths must be computed, but a criteria must be defined depending on the application domain.
  For instance, the criteria could be to select all paths of the graph of length 3. In this case, the following paths[To facilitate reading the paths we use ovals to denote attribute nodes,  superscripted arrows to denote edges and rounded rectangles for class nodes.] would be part of
  the BoP of Fig. <ref>: answer call, name, Transition, target, State, name, Talking, Transition, container, Region, transition, Transition, source, State, etc.
  
  The concrete criteria that we use in the BoP extraction for
  our search engine is explained in Sect. <ref>. 
  
  A BoP has two main characteristics: it is a compact representation of the model structure and it can be used to reveal relevant models with respect to the query. For instance, the path answer call, name, Transition, target, State, name, Talking extracted from the query graph encodes the fact that the user is interested models with a transition named answer call whose target state is named Talking. The same path exists in the repository model Fig. <ref>(left), hence this model become relevant to the query.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
   §.§ Scoring and ranking models
  
  
  
  
  
  
  
  Given a query q, our goal is to determine the relevance of the models with respect to it.
  
  To achieve this, the models that belong to ℳ are transformed into a set of graphs. For each graph, the paths are extracted generating a set of bags of paths, BoPs = {BoP_1,…,BoP_t}, where t = |ℳ| . On the other hand, the query q is processed in a similar way generating the bag of paths BoP_q.
  
  
  
  
  
  
  
  
  
  
  
  
  
  We are interested in comparing BoP_q with each BoP_i in the repository. The comparison must take into account the number of
  paths that appear in both BoP_q and BoP_i (matching paths) and the
  relevance that each matching path has within each BoP_i. 
  To this end, we have chosen the ranking function Okapi BM25 <cit.> which is computed using the matching paths between both BoP_q and BoP_i,
  and taking into account the relevance of each match according to the size  |BoP_i| in comparison to the sizes of the BoPs in the repository and the number of repetitions of each path in BoP_i.
  Thus, r(BoP_q,BoP_i) using our adapted
  version of Okapi BM25 is:
  
  
  
  
  
      ∑_ω∈ BoP_q ∩ BoP_ic(ω,BoP_q)(z+1)c(ω,BoP_i)/c(ω,BoP_i)+z(1-b+b|BoP_i|/avdl)log(t+1/df(ω)),
  
  where 1≤ i ≤ t, c(ω,BoP) is the number of times that a path ω appears in a bag BoP, df(ω) is the number of bags in BoPs which have that path, avdl is the average of the number of paths in all the BoPs in the repository and z ∈ [0,+∞), b ∈ [0,1] are hyperparameters. The parameter b controls the penalization of models which have a large size and z controls how quickly an increase in the path occurrence frequency results in path frequency saturation. If b → 1, larger models have more penalization. In our current version we take b=0.75 as default value. If z → 0 the saturation is quicker and if z →∞ the saturation is slower. We take z=0.1 (quick saturation) because a lot of repetitions of a path in a model does not imply that this model has much more relevance than other model that has this path repeated less times. 
  
  
  
  Computing a ranking using this formula is straightforward, just 
  by taking the query and all the models in the repository, computing r(BoP_q,·) for every model of the repository and sorting the models in decreasing order. However this approach is very inefficient since it has to visit all the models in the repository, performs the path extraction for each one and compute r. Next section describes how to engineer the search engine to efficiently 
  compute the ranking.
  
  
  
  § ENGINEERING A SEARCH ENGINE
  
  
  
  
  
  
  
  In this section, we describe the practical aspects of our search engine.
  The architecture is depicted in Fig. <ref>. There are
  two main processes: offline and online. The offline process is in charge
  of gathering models from one or more model repositories using
  dedicated crawlers. The indexer takes these models, process them, and 
  constructs an inverted index over Apache HBase using a specific encoding
  to make the search fast. For each model, a pipeline
  made of several components is applied: a model to graph transformation, a path extraction process to 
  obtain a bag of paths of a given length from the graph (see Sect. <ref>), a normalization
  process in which some standard Natural Language Processing (NLP) techniques are applied to have a more semantic handling of string values (see Sect. <ref>), and the stop path removal process which filters out some irrelevant paths from the bag of paths. 
  
  
  On the other hand, given a query we apply
  the same pipeline. In this case, the resulting bag of paths is used
  by the scorer, which implements the scoring function in Equation <ref> by accessing the index, and returns a ranked list of models according to their similarity.
  
  In the following we describe the design and some implementation details
  of these components.
  
  
  
  
      
      
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  offlineonline0.5Architecture and main components of MAR.
  
  
  
  
  
   §.§ Path extraction
  
  
  
  
  
  Path extraction is an important element of our search engine, since it transforms the structural information of the
  model into a form suitable for indexing. In the previous section we define the multiset BoP by describing the form of the elements that belong to it in a generic way. In practice, we need to
  define a criteria to extract a relevant BoP from a model. 
  To establish this criteria we follow this reasoning: 
  increasing the length of the path is equivalent to increasing the requirements that a model of the repository has to satisfy in order to be relevant to the user query. For instance, for the graph in Fig. <ref> we can extract these two paths:
  answer call, name, Transition and answer call, name, Transition, target, State, name, Talking. The first path (length one) is less restrictive in the sense that all models which have a transition called answer call will be relevant. The second path (length three) is more restrictive since it states that relevant models need to have a transition called answer call that has a target state of name Talking. 
  Therefore, we construct the BoP by considering all simple paths (no cycles) of length less or equal than a threshold (typically 4). On the other hand, even with a fixed length, considering all paths between all vertices will make a huge BoP. 
  Consequently, we consider the paths with the following forms:
  
  
  
  
  
  
  
  
      
    * All singleton paths for objects with no attributes: (μ^2_V(v)) where v ∈ V, μ^1_V(v) = class and ∀ w accessible from v, μ^1(w)=class. Path Region is the only one in the example.
      
      
    * All paths of length=1 between attribute values and its associated object class: (μ^2_V(v),μ_E(e),μ^2_V(u)) where μ^1_V(v) = attribute. These encode object data. For instance, initial, kind, PseudoState and Phone call, name, StateMachine.
      
      
    * All paths without cycles between attributes; and all paths without cycles between attributes and objects without attributes: (μ^2_V(v_1),μ_E(e_1),…,μ^2_V(v_n-1),μ_E(e_n-1),μ^2_V(v_n)) where n - 1 ≤ length threshold and one and only one of the following statements is true:
      
          
    * μ^1_V(v_1) = attribute and μ^1_V(v_n) = attribute.
          
    * μ^1_V(v_1) = attribute and μ^1_V(v_n) = class where ∀ w accessible from v_n, μ^1(w)=class.
          
    * μ^1_V(v_n) = attribute and μ^1_V(v_1) = class where ∀ w accessible from v_1, μ^1(w)=class.
          
    * μ^1_V(v_1) = class where ∀ w accessible from v_1, μ^1(w)=class. μ^1_V(v_n) = class where ∀ w accessible from v_n, μ^1(w)=class.
      
      For instance, with length≤4 we have paths like:
      
          
    * answer call,name,Transition,kind,external 
          
    * Phone call, name, StateMachine, region, Region
          
    * external,kind,Transition, source, State,name,Wait to pick up
          
    * Talking,name,State, container, Region,subvertex,State, name, Phone call
      
  
  
  The rationale is to represent the data of an object (its internal state) with 
  paths of length=1, or with length=0 if an object does not have attributes
  and we use the class name as a surrogate. We use paths of length > 1 to
  encode the model structure in terms of the relationships between the data of the objects (their attribute values).
  In practice, is configurable to reduce the BoP size
  even more by filtering out
  classes, attributes or references which might not
  be of interest for specific meta-models.
      
  
  
  
  
  
  
  
  
      
      
  
  
  
  
  
  
   §.§ Normalization
  
  
  Once the BoP of a model has been computed, the next step is to normalize to increase the chances of having matching paths.
  
  
  
    §.§.§ Word normalization
  
  Oftentimes attribute values are strings, which typically carry some meaning according to the model domain. However, small variations in the same word prevent matching similar words.
  Given an attribute of type string, we apply the following
  techniques typically used in Natural Language Processing (NLP):
  
  
  
  
  
      
    * Tokenization: Given a character sequence, tokenization is the task of dividing it into pieces, called tokens. This process is customizable. 
      
      In the running example we use a white space tokenizer
      and make characters lower case. The tokenization of  Waiting to pick up results in [waiting] [to] [pick] [up]. 
      
      
      
      
    * Stop words removal: The term stop word refers to a word that appears very frequently when using
      a language. Thus, a typical process in NLP systems is to remove them. In our case, we remove tokens
      containing English stop words. In the previous example we would apply stop word removal as follows: [waiting] [to] [pick] [up] ⟶ [waiting] [pick].
      
      
    * Stemming: This is a NLP technique whose goal is to reduce inflectional forms and sometimes derivationally related forms of a word to a common base form. In particular we use the Porter Stemming Algorithm <cit.>.
      In the example, the application of stemming would produces: 
      [stem(waiting)] [stem(pick)] ⟶ [wait] [pick].
  
  
  At the end of this process we might end up with a single string value (e.g., “Waiting to pick up“) split into zero or more tokens. If there are no tokens, the node is removed. If there are more than one token, the node is duplicated according to the split and all the paths including such node are duplicated accordingly. For instance, the path Waiting to pick up, name, State is transformed in these two paths: wait, name, State and pick, name, State.
  
  
  
  
  
  
  
  
  
  
  
  
  
    §.§.§ Stop paths removal
  
  There exists some paths which do not provide any information about the model, in the sense of how similar or different is from other models. This happens for paths which appear in the majority of the models, which we call stop paths. 
  For example, a path like initial,kind,PseudoState is a stop path because most state machines have an initial state. 
  Currently, we heuristically consider a path to be a stop path if it appears in the 70% of the models in the repository. This is calculated only once as a post-processing in the indexing.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
   §.§ Indexing models
  
  
  
  
  In a search engine, the indexer is in charge of organising the documents in a way that enables
  a fast response to the queries. In our case, the documents indexed by the
  search engine are models obtained by crawling existing model repositories.
  We have created a number of scripts to semi-automate
  this process for GitHub, GenMyModel and the AtlanMod Zoo. The results are
  collections of XMI files which are consumed by the indexer.
  
  The main data structure used by the indexer is the inverted index <cit.>.
  It is a large array with one entry per word in the global vocabulary and each entry points to a list of documents that contains such word. In , we index models, and therefore there is an entry per different
  path and, for each one, a pointer to the list of models which have this path. However, compared to text retrieval systems the size of the index is larger since there are much more paths than words and queries are bigger (in a text retrieval system the queries are keywords), that is, there are more accesses to the inverted index. For instance, in a repository of 17.000 models, we counted more than twenty million different paths and a small query could have hundreds of different paths. 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  We use Apache HBase <cit.> to implement the inverted index. HBase is a sparse, distributed, persistent multidimensional sorted map database, inspired by Google's BigTable <cit.>. 
  
  HBase is prepared to provide random access over large amounts of information, and its
  horizontally scalable, meaning that it scales just by adding more machines into the pool of resources.
  In HBase each
  table has rows identified by row keys, each row has some columns (qualifiers) and each column belongs to a column family and has an associated value. A distinctive feature of HBase is that two rows can have different columns, and a row may have thousands of columns. 
  
  HBase provides two read operations: scan and get. Scan is used to iterate over all rows that satisfy a given filter. Get is used for random access by key to a particular row.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  Building an inverted index over HBase can be straightforward if each path is a row key and the models that contain this path are columns
  whose qualifier (i.e., the column name) is the model identifier and whose value is a pair containing the number of times the models have the path and the total number of paths of the model (this information is pre-computed
  to calculate the score efficiently). 
  However, this approach is not optimal because to implement the scoring
  function we need to perform as
  many get calls as paths in the query. This causes a performance bottleneck because 
  each get is completely independent; that is, for each path in the query (e.g., a thousand paths) an independent look up is done just to recover the needed information about one and only one path. Another option is to use a scan with a prefix filter. However, this can return a lot of paths that we have to filter in the client side.
  
  An alternative is to organize the table schema in a way that 
  accommodates to the most common access pattern, so that 
  the data that is read together is stored together. In HBase the data is stored following a lexicographic order of the concatenation of the row key and the column qualifier in a column family. 
  
  Therefore, we propose a database schema similar to the one in 
  Fig. <ref>.
  Each type of model has an inverted index (a table). 
  
  Each path is split into two parts: the prefix and the rest, and
  the prefix is used as row key and the rest is a column qualifier. The split is different depending on whether it starts with a attribute
  node or an object class node.
  
  
  
  
  Path starts with attribute value. The prefix is
  the first sub-path of length 1. For instance, the path hang, name, Transition, source, State, name, talk is split into a row key: (hang, name, Transition and the column qualifier: , source, State, name, talk). The value associated to the column is a serialized map which associates the identifier of the models which have this path with the number of times the path appears in the models and the total number of paths of the models (these two numbers are necessary in the calculus of the score). In the figure, sm1: [1, 1032] means that the path appears in model sm1 only once and 1032 is the number of paths that sm1 has.
  For paths of length=1 we use the symbol ) as a marker for the column
  qualifier, as in hang, name, Transition.
  
          
  
  
  Path starts with object class. For instance, an example could be Region, subvertex, State, name, talk. This path is split into (Region and , subvertex, State, name, talk). (Region is going to be the row key and  , subvertex, State, name, talk) will be the column qualifier. 
  For paths of null length, for instance Region we use
  ) as column name as before.
  
  
  
  
  
  
  CFSchema10.4HBase table schema
  
  
  
  
   §.§ Scorer
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  Using this schema, the underlying idea to implement an optimized version of the
  scoring function is to gather 
  information about more than one path in each database get petition. Given a query, for each distinct prefix there is only one petition to HBase because it is possible add the columns that you want to retrieve in a single get. The main idea is to explode the lexicographic order in each petition returning the needed information about some paths that are stored together due to the fact that they have the same row key (i.e. the same prefix).
  The following algorithm shows how to implement the scoring function
  for HBase.
  
  
  
  
  
  
  
  In this algorithm paths are split into prefix and rest as explained in Sect. <ref>, and elements ω, c and df were explained in Sect. <ref>.
  If a user introduces the query Fig. <ref>(right) in our search engine, it would return a ranked list in which the first result is the one shown in Fig. <ref>(left) with a score of 1520.15. Some of the paths that contribute to the score (i.e. that match) are wait, name, State, talk, name, State, answer, name, Transition, target, State, name, talk, etc. 
  
  
  
  
  
  
  
  
  
  
  
  
  § APPLICATIONS
  
  
  The main application of our search engine is obviously searching for models, but it can also be 
  applied to other scenarios. 
  For instance,  it can be used as the basis to build a model recommender
  which searches in the background for relevant models and then extracts
  new features to suggest (e.g., a property for a class). It can also be used
  as a means to find reusable MDE components (e.g., transformations, editors, etc.) by indexing the meta-model footprint of each component. 
  In this section we discuss two applications for which we have
  already used and experimented with our search engine:
  searching for models and meta-model classification, but
  we want to implement new applications in the future.
  
  
  
  
  
  
   §.§ Model searching
  
  
  
  
  The availability of model repositories has been regarded as an
  important element for the success of MDE, since they may foster
  the reuse and sharing of software models, thus increasing the visibility
  of the MDE paradigm. There are several model repositories (e.g., ReMoDD, AtlanMod Zoo, GenMyModel), but models are also stored in regular code repositories 
  (e.g., as part of GitHub projects). This makes it difficult for users
  to retrieve relevant models, since it implies looking up in several locations. Moreover search tools in these repositories are not model-oriented or there might be no search tool at all <cit.>.
  is able to aggregate models coming from several
  sources and provides an unified access to them. 
  is available at <http://mar-search.org>,
  in which updated statistics about the number and types of models
  can also be checked. We also
  provide access to through a REST API and an Eclipse-plugin.
  
  
  
  
  
  
  
  
  
  Access through a REST API.
  We have implemented a simple REST API to allow the integration of
  the search engine in tools of diverse nature, like a web-based
  interface, extensions of modelling environments, or simply to perform experiments.
  
  The REST API has two main methods: search is a POST method which
  receives a file in XMI format, the type of model and an integer with 
  the maximum number of results. It connects with
  the search engine and returns as a response a JSON document with the list
  of relevant document as pairs of (id, score). The GET method get_model retrieves the data associated to a given model. 
  
  
  
  Eclipse plug-in. As a prototype we have implemented 
  an Eclipse plug-in to add search functionality to existing Eclipse 
  model editors. Fig. <ref> shows a screenshot. An Eclipse
  view connects to the active editor. The search
  button takes the contents of the current editor, serializes it and 
  submits the query. The results can be inspected using a dedicated view
  or downloaded for further manipulation.
  
  screenshot0.5Eclipse-plugin and REST API
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
   §.§ Meta-model classification
  
  
  
  The automated classification of model repositories is regarded as
  an important activity to support reuse in large model repositories <cit.>.
  Automated methods could annotate models with fine-grained metadata to help developers make decisions about what to reuse.
  
  
  Recent works have used supervised machine learning methods like neural networks <cit.> and 
  unsupervised methods like clustering <cit.> to
  classify meta-models into application domains automatically
  (e.g., state machines, class diagrams, etc.).
  
  An alternative and simpler method is to use a model search engine like ours to apply the
  k-Nearest Neighbors (k-NN) supervised learning algorithm to this task <cit.>. 
  
  Let us suppose that we have a repository labeled with the 
  domain of each meta-model. If we want to classify a new meta-model,
  we use it as a query for our search engine, we select the top k meta-models of the ranked list of results, and finally we assign to it the label of the majority. 
  
  
  
  
  
   
  To take advantage of the score provided by the search engine we use weighted k-NN, which is a modification of k-NN. Weighted k-NN is based on assigning weights to the votes of the test data's neighbors. In our case, the weights will be the score of each result.
  
  
  
  
  To evaluate the adequacy of this approach we replicate the 
  experiment carried out in <cit.> and compare
  the results. We use the same dataset of 555 metamodels <cit.> retrieved from GitHub. In this dataset,
  each meta-model is labeled with its domain (9 domains were identified).
  
  
  We follow this procedure to estimate the performance of weighted k-NN using .
  
  
  
  Selecting k.
  Split the 555 metamodels into two sets: training set (70% of them) and test set (30% of them). We use the training set to select the k hyperparameter (i.e., number of neighbours) and estimate the performance. We do a 10-fold cross-validation and, as evaluation metric, we use the accuracy (i.e., the percentage of correctly classified models). After the 10-fold cross-validation, for each considered k=2… 10, we choose the k that maximizes the accuracy's mean of validation sets.
  The best results are achieved with k = 2 with an accuracy of 93.23%.
  
  
  
  
  
   
    
     
      
  
  
  
  
  Test. Once the k hyperparameter has been chosen, 
  we can directly evaluate the test set. In particular, with 
  k=2 the accuracy of our method in the test set is 93.37%.
  
  
  
  
  
  
  Assessment.
  The approach in <cit.> uses a neural network
  and estimate an accuracy of 95.45%, which is slightly better
  than ours (93.23%). Hence, it can be claimed that can
  also be used for meta-model classification with results comparable
  to state-of-the-art techniques.
  It is also worth mentioning that neural networks are very powerful but they are black box, that is, you do not know the reason of its predictions. In this way, our approach is more transparent because the classification decision is determined easily by just looking at the models of the ranked list of results.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  § EVALUATION
  
  
  
  
  
  
  
  
   
   
    
      
     
      
       
        
         
      
  
  This section reports the results of the evaluation of our search engine.
  First, we evaluate its search precision, that is, the ability of to rank
  relevant models on top. Second, we show the performance results.
  The datasets and a replication package are available at <http://mar-search.org/experiments/models20>.
  
  
  
  
  
  
  
  
  
   §.§ Search precision
  
  The evaluation of the precision of a search engine requires
  some metric about the adequacy and relevance of the search results. A user-oriented study about
  the relevance of the search results would be an appropriate manner to evaluate the usefulness of our system.
  
  
  
  
  
  
  
  However, setting up this kind of study is out of the scope of the paper and it is left as future work. Instead,
  to have an initial evaluation of we have devised an automated approach.
  
  
  
  
  
  
  
  
  
  The underlying idea is to simulate a user who has in mind a concrete
  model and the query is automatically derived using mutation operators
  that generate a shrinked version of the model which includes some structural and naming changes. Thus, for each generated query mutant there is only one relevant model, which known beforehand. This type of evaluation is called known item search <cit.>.
  
  
  
  As target for the search, we have used all the Ecore meta-models indexed by (17975). 
  We perform the evaluation twice, with two different sets of mutants. The first set comes from 281 meta-models obtained from 
  the AtlanMod zoo (referred to as Mutants_AtlanMod).
  The second set comes from 2000 meta-models randomly selected from all the
  indexed meta-models (referred to as Mutants_All).
  To ensure a certain degree of quality in the query mutants, we require that the
  meta-models have at least 20 classes and 40 elements (adding up EClass and EStructuralFeature elements). The aim is to filter out small meta-models which may result in queries very close to the original.
  
  For each
  meta-model we apply in turn the mutation operators summarized in Table <ref>. First, we identify a potential root 
  class for the meta-model and we keep all classes within a given “radius” (i.e., the number of reference or supertype/subtype relationships which needs to be traversed to reach a class from the root), and the rest are removed. All EPackage elements are renamed to avoid any naming bias. From this, we apply mutants to
  remove some elements (mutations 2–6). Next, mutation #7 is intended to make the query more general
  by removing elements whose name is
  very specific of this meta-model and it is almost never used in other meta-models 
  (in text retrieval terms the element name has a low document frequency). Finally, to implement mutation #8 we have 
  applied clustering (k-means), based on the names of the elements of the meta-models, in order to group meta-models that belong to the same domain. In this way, this mutant attempts to apply meaningful renamings by picking up names from other meta-models
  within the same cluster. We apply this process with different
  radius configurations (5, 6 and 7) and we discard mutants
  with less than 3 classes or with less references than |classes| / 2.
  Using this strategy we generate 128 queries for Mutants_AtlanMod and  1595 queries for Mutants_All.
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  Given that we do not have access to any other model search engine,
  we have implemented a text-based
  model search engine on top of Whoosh <cit.> (a pure Python search engine library) as way to have a baseline to compare against. The full repository is translated to text documents which contain the names of each meta-model (i.e., property ENamedElement.name). These documents are indexed and we associate the original meta-model to the document. Similarly, we generate the text counterparts of the mutant queries. 
  
  
  
  
  
  The procedure to evaluate the precision of each search engine and query set is as follows. Each query has associated the meta-model from which it was derived. For each query we perform a search and we retrieve the ranked list of results. We look up the original meta-model in the list and take its position, r. Then, we
  compute the reciprocal rank which is 1/r.
  To summarize all reciprocal ranks we take the average of them (Mean Reciprocal Rank, MRR).
  
  To compare the precision of and Whoosh we use the parametric t-test for the two set of queries. In both cases, we have p-value<.001 indicating that the difference in the mean reciprocal rank is significant.
  Table <ref> shows the global results of the evaluation and
  Fig. <ref> shows the proportion of queries which are ranked in the first, second up to the fifth position or more.
  ranks more queries in the first position in both query
  sets. 
  It is also interesting to observe that the proportion of queries
  ranked in positions equal or greater than 5 is smaller in .  
  In addition, the results for Repo_AtlanMod are better than
  Repo_All in both and Whoosh. The reason is that the AtlanMod meta-models are generally more complete (e.g., more classes, features, etc.), than the random sample taken from 's index. Therefore the query mutants tend to be of better quality.
  
  
  
  From these results we conclude that has a good precision,
  and the precision seems to improve when we search for larger
  models using well defined queries. 
  The fact that is better in both query sets reinforces
  our hypothesis that outperforms plain text search in general.
  
  
  
  
  
  
  
  marvswhoosh0.5Precision evaluation results. Proportion of queries (y-axis), the position of the relevant document (x-axis) in the ranked list and engine/query set as colour of the bars.
  
  The main threat to validity of this experiment is that the obtained mutants might not represent
  the queries that an actual user would create. To minimise it we have tried several 
  mutation operators and configurations and reviewed the mutants manually until we found
  reasonable results. Nevertheless, we expect to understand better the user behaviour
  as is used by the community.
  
  
  
  
  
  
  
  
  
  
  
   §.§ Performance evaluation
  
  To evaluate the performance of we have used all mutant queries extracted from Mutants_All. We want to
  evaluate the effect of the index size in the 
  response time. Thus, we have incrementally indexed batches of 1.000 meta-models (randomly selected), and for each new batch we 
  measure the response time for each query mutant.
  Moreover, to evaluate the effect of the query size we 
  count the number of packages, classes, structural features
  and enumerations and we classify
  the queries in three types: small (less than 20 elements), medium
  (between 20 and 70) and large (more than 70).
  Table <ref> shows some details about the contents
  of the queries. 
  
  We run the experiments on a desktop machine with an i7-5820K CPU, with 6 cores at 3.30GHz and maximum heap 16GB. We use Docker to deploy HBase (which runs in a pseudo-distributed mode) and we 
  access it locally since we are mainly interested in understanding
  the raw performance of our design of the inverted index, and not 
  on potential network effects.
  
  
  
  
  
  Fig. <ref> shows the relationship between index size and response time, and Table <ref> summarizes the results for the largest index.
  As can be
  observed scales smoothly as the size of the index increases
  and, as expected, larger queries take more time (except some outliers because of the garbage collector).
  On the other hand, small queries correspond to scenarios in which
  the user would develop a query in a fast manner, possibly with
  little details. In this case, the average response time is 0.53 seconds for the larger index. The average response time for medium and large queries is 1.24 and 2.06 seconds respectively, which is quite acceptable since there are queries with up to 193 classes.
  This would be useful in scenarios like model clone detection.
  In general, the computation of the bag of paths and the scoring are 
  fast. The execution of get petitions to HBase consumes most
  of the execution time, and it is where we could improve more
  the overall performance. Nevertheless, this experiment shows that is already an efficient search engine. 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  § RELATED WORK
  
  In this section we review works related to our proposal,
  organised in three categories: model encoding techniques 
  which are relevant for model search and indexing, model repositories
  and search engines for models themselves.
  
  
  
  
  
  
  
  Model encoding techniques.
  Code2Vec is an technique for representing snippets of code as continuous distributed vectors <cit.>. For each code snipped, a multiset of paths (named bag of path-contexts) is extracted from the AST and it is used as an input of a neural network. Our idea of BoP was inspired by the concept of bag of path-contexts.
  SAMOS is a platform for model analytics, which employs a technique to transform models into vectors in order to apply supervised learning, unsupervised learning, statistical analysis, etc. SAMOS is used in <cit.> for model clustering and meta-model clone detection is proposed in <cit.>. The notion of n-grams is used to represent paths of length n between nodes in a graph associated to a model. Models are transformed into a set of n-grams and then to a explicit vector whose dimension is determined by the number of distinct n-grams in the repository. This is similar to , since we both use paths to encode the structure. However there are some key differences: our graph is different as we consider single attributes as independent nodes, and therefore the extracted paths are different. SAMOS considers paths of the same length, whereas our BoPs are formed by paths of length less or equal than a threshold. 
  
  SAMOS is, in principle, not oriented to implement a search engine since it uses similarity metrics (to build the vectors) which are not thought to perform a fast search.
  In <cit.> locality sensitive hashing is applied
  to summarize EMF models as a hash. This has different applications
  including intellectual property protection and fast model comparison. This could be
  an alternative strategy to organize a search index. On the other hand, AURORA <cit.> extracts tokens from an Ecore model following an encoding schema (they propose three encoding schemes that try to reflect the model structure) and then, using these tokens, models are transformed to a vector in a vector space that will be an input of a neural network. In <cit.>, the authors propose using graph kernels for clustering software modeling artifacts. The general idea is to transform a set of software models to a set of graphs and then use graph kernels to measure the distance between each other.
  For clone detection, Exas is a vector encoding of graph models to perform
  approximate matching of model fragments <cit.>, which has also
  been applied to detect model transformation clones <cit.>.
  
  In <cit.> both structural and syntactic metrics are used in order to compare two meta-models. Also, they used genetic algorithms for meta-model matching. However, their approach did not support indexing so the matching was not though to be fast.
  The notion of domain-specific distance is discussed in <cit.>, 
  which could be incorporated to improve the precision of the search.
  
  
  
  
  
  
  
  
  
  
  Model repositories.
  MDEForge is a collaborative modelling platform <cit.> intended to foster “modelling as a service” by providing facilities like model storage, search, clustering, workspaces, etc. It is based on a mega-model to keep track of the relationships between the stored modelling artefacts. 
  GenMyModel is a cloud service which provides online editors to create different types of models and
  stores thousands of public models <cit.>.
  
  
  ReMoDD is a repository of MDE artifacts of different nature, which is available through a web-based interface <cit.>.
  Hawk provides an architecture to index models <cit.>, typically for private projects and it can be queried with OCL.
  Regarding built-in search facilities in existing model repositories, the study in <cit.> shows that search is
  typically keyword-based, tag-based or simply there is no search
  facility.
  
  
  
  Search engines. Several search engines for models have been proposed in the past
  years, but as far as we know none of them is widely used. Table <ref> shows a summary
  of their characteristics.  
  In <cit.>, a search engine for WebML models is presented. It supports two query formats: keywords and example-based query. An index is supported only in the keyword query format so structured-based search could be slow if the repository is large. MOOGLE <cit.> is a generic search engine that only supports text queries in which the user can specify the type of the desired model element to be returned. MOOGLE uses the Apache Lucene query syntax and Apache SOLR as the backend search engine. In <cit.>, a similar approach to MOOGLE is proposed with some new features like megamodel-awareness (consideration of relations among different kinds of artifacts). On the other hand, <cit.> focuses on the retrieval of UML models using the combination of WordNet and Case-Based Reasoning. 
  
  MoScript is proposed in <cit.>, a DSL for querying and manipulating model repositories. This approach is model-independent, but the user has to type complex OCL-like queries that only retrieve exact models, not a ranking list of models. 
  Regarding our query-by-example approach, some graph transformation engines have been extended to support this feature. For instance, IncQuery has been extended to derive a graph query from an example model <cit.>, and VMQL (Visual Model Query Language) uses the concrete syntax of the source language as the query language <cit.>.
  
  
  
  
  
  
  Regarding the scale of the system in terms of the number of models handled, the closest system to is SAMOS <cit.>, which performs clustering of 22k meta-models. However, a clustering process is different from indexing, so
  the approaches are not really comparable. Nevertheless, clustering a huge model repository is computationally expensive. In particular, SAMOS is running over Apache Spark in <cit.> and takes 17 hours to process a repository of 7k meta-models. With respect to the size of the indexed models, our system increases in at least an order of magnitude existing proposals. For instance, MOOGLE <cit.> only indexes 146 models, <cit.> indexes 12 real-world WebML projects which consist on 342 models, and in <cit.> up to 3000 models are indexed. 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  § CONCLUSIONS
  
  In this work we have presented a novel search engine for models. 
  The key idea is to use paths between attribute values to encode
  the model structure in an indexable manner. Our evaluation
  shows that is both precise and efficient. 
  Moreover, we have applied to meta-model classification
  obtaining results comparable to state-of-the-art techniques.
  Regarding its practical usage,
  is able to crawl models in several sources and it has currently indexed more than 50.000 models of different kind, including Ecore meta-models, BPMN diagrams and UML models. This makes it a unique system in the MDE ecosystem, that we hope it is useful for the community.
  
  
  
  
  
  As future work we plan to improve
  our crawlers to reach more repositories. We also
  want to include information about the model quality
  in the ranking. Finally, as is used in practice we aim at
  thoroughly evaluating it with an empirical study.
  
  
  
  
  
  
  
  
  
  
  
  § ACKNOWLEDGMENTS
  
  Work funded by 
  the Spanish Ministry of Science, project TIN2015-73968-JIN AEI/FEDER/UE
  and a Ramón y Cajal 2017 grant.
  
  ACM-Reference-Format
  
  