Authors:

Abstract

Cache is an important service to enable faster data access for distributed data storage systems. A cache system with a higher hit ratio and a lower query processing time is considered to be an efficient cache system. Semantic cache has a potential to maximise the hit ratio as compared to other cache organisation techniques because it has an ability to answer fully as well as partially overlapped queries. It is a challenge to determine the overlap between incoming queries and stored semantics (semantic matching) with minimum time. To store the semantics, one of the parameters which plays a significant role in the complexity of semantic matching is the indexing scheme. Existing indexing schemes store each disjoint query (on the base of projection) into different segments and the number of segments can grow to exponential (2n-1, where n is the number of queried attributes) in the worst case. This will lead to an exponential complexity semantic matching scheme. We propose a schema based on semantic indexing that enhances the efficiency of semantic matching process by reducing the time for query matching significantly. In the proposed indexing scheme, we have merged query semantics with the schema. On the basis of the proposed indexing scheme, we have designed a query matching algorithm (sMatch). It is proved that the time complexity of sMatch is polynomial while the complexity of other matching algorithms is exponential. In addition to reducing the complexity of semantic matching, schema based storage of semantics would reject incorrect queries and enhance the hit ratio in cases where the non-schema based schemes would not find the data from the cache. To show the rejection of incorrect queries and improved hit ratio, complexity based and experimental results are presented. The results show that the proposed scheme performs significantly better than the previous ones.

Keywords: Distributed databases,  knowledge management,  query matching,  query processing,  semantic cache,  semantic indexing 

How to Cite: Ahmad, M., Qadir, M.A. & Ali, T., (2017). Indexing for semantic cache to reduce query matching complexity. Journal of the National Science Foundation of Sri Lanka. 45(1), pp.13–22. DOI: http://doi.org/10.4038/jnsfsr.v45i1.8033