Research Articles
Indexing for semantic cache to reduce query matching complexity
Authors:
Munir Ahmad ,
PK
About Munir
Department of Computer Science, Faculty of Computing, Capital University of Science and Technology, Islamabad, Pakistan.
M Abdul Qadir,
PK
About M Abdul
Department of Computer Science, Faculty of Computing, Capital University of Science and Technology, Islamabad, Pakistan.
Tariq Ali
PK
About Tariq
Department of Computer Science, Faculty of Computing, Capital University of Science and Technology, Islamabad, Pakistan.
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.
How to Cite:
Ahmad, M., Qadir, M.A. and 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
Published on
24 Mar 2017.
Peer Reviewed
Downloads