| With the development of the computer storage technology,a new type of memory called byte-addressable non-volatile memory,also known as NVM,has appeared in recent years.The byte-addressability and non-volatility make NVM a promising component of the computer storage hierarchy in the future.However,existing algorithms may not be applicable to NVM because of the asymmetry of NVM’s read and write costs.Based on the background given above,this thesis focuses on finding an efficient subgraph matching algorithm on NVM.The main content of the research work can be summarized as follows.Firstly,this thesis studies the problem of efficient exact subgraph matching on NVM.Since the write cost is significantly higher than the read cost on NVM,the key to increasing efficiency on NVM is to reduce write operations by increasing read operations.This thesis gives a detailed qualitative and quantitative analysis on existing algorithms to find the part with the most write operations.Based on the analysis,this thesis presents a novel index called ILD-List to reduce write operations during the matching process.The ILD-List solves the problem of too much writes in the existing backtracking framework,thus improving efficiency on NVM.Secondly,this thesis extends the problem to dynamic graphs with updates based on the research results in the first part.To increase efficiency,this thesis modifies the storage structure of the ILD-List so that it can be updated with as few write operations as possible.This thesis also gives a new strategy to reduce the search space of the updating algorithm by giving a tight bound of the region where new matches can be found and thus improves efficiency on NVM.Thirdly,this thesis studies the problem of approximate subgraph matching on NVM in order to find a way to further increase efficiency with little loss on accuracy.This thesis gives a new definition of dual simulation to fix the problem of mismatches in existing subgraph matching algorithms based on simulation.This thesis also presents 2 efficient algorithms based on dual simulation by limiting the construction of indices in the process of existing algorithms.Finally,all algorithms are implemented and experiments are conducted on an NVM simulator.Experimental results show a significant improvement on the efficiency of the algorithms the thesis presents compared to existing ones. |
