Rule-Based Data Mining Cache Replacement Strategy

Rule-Based Data Mining Cache Replacement Strategy

Ramzi A. Haraty (Department of Computer Science and Mathematics, Lebanese American University, Beirut, Lebanon) and Joe Zeitouny (Department of Computer Science and Mathematics, Lebanese American University, Beirut, Lebanon)
Copyright: © 2013 |Pages: 14
DOI: 10.4018/jdwm.2013010103
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

Caching in mobile environments is used for improving bandwidth usage and reducing query delays among resource constrained devices. It is used in multitudes of approaches. Some rely on the server occasionally broadcasting reports to inform clients of updated data while others permit clients to access data whenever they need it. Caching can be constrained by size and bandwidth; thus, coming up with a good invalidation scheme is critical in improving cache consistency solutions. In this work, the authors propose a new hybrid cache invalidation scheme that makes use of data mining concepts. They also compare their scheme with other related strategies.
Article Preview

Introduction

Caching in a mobile environment can leverage the relatively low bandwidth wireless channel constraint imposed by wireless and mobile computing. However, developing caching techniques has been a challenging task due to several factors such as the need to consider users’ mobility and client disconnected modes, which may show as a result of limited power availability or unpredictable disconnection circumstances. Thus, it is not enough to have a copy of the requested data reside in cache because data may have been changed over time and may not be valid anymore. Caching aims at providing users with the latest version of the data when it is requested.

Two primary models for data dissemination have been proposed: the push-based model and the pull-based model (Waluyo et al., 2005a, 2005b). In the first model, clients query for some data objects from the server which replies back with the requested information. In the second model, information is sent from the server to connected clients even though the clients have not requested it. The timing and the data chosen for broadcast is up to the server to decide on.

Data dissemination through broadcasting turned out to be efficient (Cao, 2002; Minh & Bich, 2010; Waluyo et al., 2003, 2004; Ilarri et al., 2012; Nicopolitidis et al., 2011; Lin et al., 2010). Broadcasting the data changes from the server in a periodic manner (either by sending data or by using invalidation reports), allows the server to share data information and status updates with an arbitrary number of mobile devices residing in the same network while minimizing the bandwidth consumption.

A multitude of methods that tackle data dissemination were suggested to ensure consistency among cache in mobile computing environments. Several of these methods consisted of stateless servers (Cao, 2003; Chand et al., 2009); whereas others used stateful servers in their design (Kahol et al., 2001; Chavan & Sane, 2011). Stateless servers do not store information about data objects that are stored in each mobile device; rather, they periodically transmit data discrepancy reports. Stateful servers maintain every mobile unit’s status and only transmit discrepancy reports in case data objects were updated or accessed. Combining the benefits of both approaches, a hybrid scheme was proposed – SACCS. SACCS or Scalable Asynchronous Cache Consistency Scheme uses as a cache invalidation scheme for a Least-Recently-Used (LRU) algorithm which takes into consideration the least recently used data object when replacing an old entry in the cache (Wang et al., 2004).

In this paper, we examine a multitude of cache invalidation schemes that were adapted to mobile environments. We also propose a new caching policy using data mining concepts, which we call apriori, and evaluate it against previous replacement strategies. Our proposal consists of using an association based rule mining algorithm in SACCS–based cache replacement system. The main reason behind choosing this type of mining is because data objects requested over a certain period are, most of the time related. Hence, any substitution of an item in the cache cannot be done without taking into consideration other related items. Thus, any substitution for a data item that is greatly related to a group of data items in the cache can lead to probable cache misses in the subsequent client queries.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 13: 4 Issues (2017)
Volume 12: 4 Issues (2016)
Volume 11: 4 Issues (2015)
Volume 10: 4 Issues (2014)
Volume 9: 4 Issues (2013)
Volume 8: 4 Issues (2012)
Volume 7: 4 Issues (2011)
Volume 6: 4 Issues (2010)
Volume 5: 4 Issues (2009)
Volume 4: 4 Issues (2008)
Volume 3: 4 Issues (2007)
Volume 2: 4 Issues (2006)
Volume 1: 4 Issues (2005)
View Complete Journal Contents Listing