Abstract
Location dependent information services can be characterized as the applications that coordinate a cell phone’s area or position with other data to give enhanced value of services to the client in the right place and at the right time from anywhere. Limited battery power and frequent disconnection due to moving environment prompts mobile distributed database to be a fertile land for many mobile databases researchers and specialists. New policies/protocols must be designed to efficiently handle the issued nearest neighbor queries. Our works involves design of new cache replacement policies, indexing, pre-fetching protocols with comparison of their performances from existing policies/protocols and reporting for future research directions.
Access provided by CONRICYT-eBooks. Download conference paper PDF
Similar content being viewed by others
Keywords
- Mobile computing
- Location dependent data
- Cache replacement
- Predicted region
- Root-mean squared distances
- Valid scope
- Cache invalidation
1 Introduction
Location-Based Services (LBS) are one of the emerging applications among various mobile and wireless based technology. LBS provide context aware information to the client at the right time in the right place. Many of the technological constrains are added to these applications to maintain integrity and consistency of result acquired from LBS-Server. The basic reference architecture of mobile databases contains three entities: fixed hosts, mobile units, and base stations. Mobile units are low power moving object having lesser computational functionality that move around a geographical region. These geographical regions are basically divided into wireless cells i.e. mobile client contains data centric applications and roams between wireless cells. LBSs [1, 2] are gaining popularity in current trends where most of the applications use some context-aware information included with the mobile host. Context-aware information includes time, location, and device identity nearby to a given entity. The potential sources of this information are web browser, camera, microphone, GPS Receiver, a server associated with the given entity. Here, entity can be person, device, or application. Location services can be characterized as services that incorporate a cell phone’s area or position with other data to give enhanced value to user. It answers the location-related queries which are initiated by moving user, where the location is the parameter of the query which are provided to the client either explicitly with query or implicitly using a global positioning system (GPS). Some of the applications [3,4,5,6,7] which are gaining popularity in our daily life can be local information access (Traveler information system, navigation maps, news etc.). Apart from this, user makes some nearest-neighbor queries (show me all nearest hotel, ATM, Saloon).
The rest of this paper is organized as follows. Section 2 explores the issues and research challenges important for the performance of LBS. Sections 3 and 4 describes the contributions, major findings of our experimentations. Section 5 has given conclusion and scope for future works in LBS.
2 Performance Issues and Research Challenges
Numerous research works have been done separately on Predictability & Consistency of LBS. To maintain consistency in nearest-neighbor based applications, system needs to identify the data-item’s valid scope and store it with them in the cache [8,9,10]. Due to the associated valid scope with given data item, the user might reject the received result if user has moved to different places and may ask to the server for reprocessing of the query to get valid result. To improve the performance of the system, there should be some mechanism to obtain fast and accurate answers to issued queries. Very little works has been done to optimize the location dependent query processing [11,12,13,14]. Data replication is employed in any distributed system to improve reliability and reduce communication costs and response time thus to reduce the incurred network traffic. Data replication technique creates various copies of same data and place it to various nodes based on some performance criteria. The problem of replication in LBS is to find the number of replica that system should create, the place where it should be put and maintain the consistency among various replica for better performance of given system [15,16,17]. The bandwidth of downlink communication is much greater than that of the uplink communication. The policy [18] should be designed in such a way that messages sent to the server would be less than message received from server. The order in which the query executed is defined as query scheduling [19,20,21]. Mobility of users makes it more challenging to handle the query scheduling task. One of the limitations in mobile host is its limited battery power. So this is also a considerable issue while making any application for mobile environment as if processing power is restrained; it compromises the capability of every mobile node offering applications and services [22, 23]. Based on previous theoretical studies and concepts, many focused implementations and simulation [24,25,26] has been done. However, none of the previous simulations has complete prototype consisting of all of the functionality for LBS. So, one of the important issues is implementation of complete prototype [27] for consistent location aware system.
2.1 Predictability and Consistency
For Nearest-Neighbor query applications, the cached spatial data result may become invalid because of the client movement. To maintain consistency, system needs to identify the data-item’s valid scope and store it with them in the cache [8,9,10]. The concept of valid scope information was first proposed by Zheng et al. [8], in which it was used to assemble a semantic cache that allows you to reuse the cached data. GPS serves to identification of the location of any mobile device in geometric location model. The ancient policy particularly Polygonal Endpoints and Approximate Circle schemes show poor performance for invalidation information in terms of overhead and imprecision. In [9] Kumar et al. gives a comparison of various methods to find best suitable candidate for valid scope (i.e. best suitable sub polygon of a given polygon). They proposed a generalized algorithm known as CEB_G which improves the caching efficiency in comparison to that of basic CEB algorithm. The CEB_G algorithm adjusts the overhead and accuracy of valid scope. Moreover, to further improve caching efficiency they proposed a new algorithm CEFAB which considers user’s movement pattern and speculation for its future access.
2.2 Cache Replacement Policy
Whenever a query issued, if cache doesn’t contains searched data items then system execute replacement process. The problem is to be addressed and also improve cache-hit ratio [28,29,30,31,32,33,34]. The conventional cache replacement policy such as LFU, LRU, LRU-K [28] have been widely used in various applications in past. The working principle of these policies are that the access pattern shows temporal locality i.e. the future access pattern dependent on only past access pattern rather than spatial information. Furthest Away Replacement policies [29] which considers both clients current location as well as movement direction in replacement policy. The eviction is made sequentially in the order of distance from the client. This policy dismisses the client’s temporal access properties. In the event when mobile clients’ direction updated frequently, then it will make unpredicted effect on membership of objects as it will show frequent switching between the in-direction set (towards valid scope) and the out-direction sets (moving far from valid scope). PAID policy evicts the data having the least cost when cache replacement is performed. PAID (Probability Area Inverse Distance) [30] has the limitation that the priorities for the client’s location nearby data objects in cache and the effect of the size of data object have not been considered. To overcome this limitation, Mobility Aware Replacement Scheme (MARS) [31] came into existence. The data objects updates are considered in this policy. This policy evaluates the various score such as spatial score, temporal score and an object retrieval cost. The update rate in location dependent data is very small as compared to that of temporal data. In deciding cache replacement data item, the anticipated region has major impact. None of the above described cache replacement policies is fit best if there is frequent updation in client’s movement direction because previous schemes consider data distance only and to work with frequent changing direction based location dependent, data the scheme should incorporate functionalities that can predict possible client’s near future region/area. In [32] Kumar et al. proposed Prioritized Predicted Region based Cache Replacement Policy (PPRRP) and compared it against previous cache replacement schemes Euclidean, FAR, Manhattan, LRU, PA and PAID. To improve the system performance predicted region is widely employed in location based services. Kumar et al. have given a scheme PPRRP which finds the predicted region of valid scope for client’s current position and assigns precedence to the closed data items. The client’s movement direction is not considered while assigning priorities to data item. Moreover, using moving interval length (MIc) as radius in this policy has a drawback that system needs to compute the predicted region on the changes in moving client’s direction or velocity.
2.3 Prefetching and Indexing
To answer mobile object database queries, searching each location in database is overwhelming task. It degrades the performance of the overall location dependent information system (LDIS). For better performance we would like to do the spatial indexing [35, 36] of location attributes but this indexing cannot be directly applied in LDIS to answer the queries. The reason behind this, the spatial index needs to be update continuously with changes in locations and which would further increase the work load on the system and communication overhead in excessive amount. To achieve better performance, indexing phenomenon is used in which server pre-computes index information and stores it with data for future queries. Here the question of indexing problem is how can we efficiently index the valid scopes of all data instances of a given query type? It is more difficult to index the geometric location mobile queries in comparison to symbolic location models query. In the spatial indexing, structures such as minimal bounding rectangle are used to map the spatial objects. If the MBR will overlaps to each other, then the search performance would be degraded as the overlapping area searched more than once. In air indexing server pre- computes the index information and broadcast it on the outgoing channel. A mobile client seeking for a query can search for its index and can predict the arrival time of the desired data; it is advantageous for mobile client as it allows going on power saving till the queried records arrive on the requested channel. The disadvantage of this phenomenon is searching for additional indexing data makes broadcast cycle longer.
3 New Direction for Research
The future scope of LBS is very vast and diverse. Meeting the issues and challenges discussed previously from all the characteristics would require more extensive and coordinated research efforts in the specific areas such as new metrics for location aware database, performance and predictability, methods and trade-off between various pairs of parameters etc. From the implementation point of view, the work undertaken will address the problems of Location Aware Information System. The main areas of research are listed below.
-
1.
Development of efficient geometric model for valid scope and cache invalidation policy [8,9,10].
-
2.
Optimization of location dependent query processing and reduce power consumption [11,12,13,14].
-
3.
Development of new algorithms for improvement in cache-hit ratio of replacement policy [28,29,30,31,32,33,34].
-
4.
Defining efficient process for data prefetching and indexing [35, 36].
-
5.
Performance evaluation of above algorithms with reference to database size, cache size, moving/prediction interval, query interval etc.
-
6.
Analyzing the effects of main memory, secondary storage and buffer size on system performance.
-
7.
Development of fault-Tolerant approaches, Recovery Scheme & Schedulable Conditions for LBS.
-
8.
Implementation of complete prototype for consistent location aware system.
4 Our Contributions
In [44], we have presented various research issues of location aware moving object databases. It includes various existing policies in location-aware mobile data management namely cache invalidation and replacement, mobility recommendation, location data map matching, replication and location privacy. Various sub-areas in the directions of location-aware information system are being explored, where there is any possible research scope. The work done by us gives better solutions for some of the listed research directions stated in the previous section.
-
1.
The accuracy of mobility prediction degrades in LDIS when it involves a lot of random movements [37,38,39]. Thus, these random movements must be reduced to get accurate mobility prediction. In [45] a sequential pattern mining method in moving client’s movement histories [40,41,42,43] for the coverage region is employed to find frequent mobility patterns. The paper investigates clustering technique to extract similar mobility behaviors in users moving histories. The SPMC-PRRP model for next location prediction in predicted region was proposed to be used in estimating the distance between data item’s valid scope reference point to the anticipated next location of the client. The cache replacement cost function for eviction of data item uses the next location prediction for effective cost computation of valued data items.
-
2.
In one of paper, a cache replacement policy MPRRP [46] is proposed that consists of weighted cache replacement cost function for eviction of data item when cache becomes full. A normalized negative cosine function which considers present moving direction of client is used to assign weight for replacement cost. The predicted region radius estimation method that was defined in PPRRP has been modified in the proposed MPRRP. The radius of predicted region circle is estimated by root mean square distance in the place of moving interval radius. This leads to reducing the unnecessary computation overhead. The proposed MPRRP policy added the temporal locality factor i.e. frequency of use in addition to spatial score for computation of the replacement cost. MPRRP achieves up to 5% performance improvement in terms of cache hit ratio compared to previous replacement policies [28,29,30,31,32,33,34].
-
3.
In one of the paper [47] mobility rules based on similarities between user’s movements data has be framed to be used in next location prediction. The conditional data distance equation has been revised and being used depending upon whether the data item’s valid scope falls within predicted region or outside the predicted region. The proposed policy achieves significant performance improvement in cache hit ratio on varying outlier ratio, minimum confidence and support threshold.
5 Conclusions
Handling of cache replacement policy is a key issue being studied by us. Despite this, there are many research accomplishments and techniques which have emerged from the area of location bases services. They lead to the increasingly growing interest in the performance mobile distributed database system. Many research accomplishments and techniques, which have emerged from the area of location aware moving database systems. In this research proposal, light has been shed on promising challenges in location aware moving database systems for applying our efforts and resources in a better way to cope up with them. Efforts will also be made to investigate these points for improving the performance for given research area. As for the future work in cache replacement policy, data dissemination schemes, pre-fetching and Hidden Markov Model with Bi-clustering for LDIS can be selected as research area which will overcome the challenges posed by it.
References
Weiser, M.: The computer for the 21st century. Sci. Am. Int. Edn. 265(3), 66–75 (1991)
Barbara, D.: Mobile computing and databases: a survey. IEEE Trans. Knowl. Data Eng. 11(1), 108–117 (1999)
Acharya, S., Franklin, M., Zdonik, S.: Balancing push and pull for data broadcast. In: Proceedings of the ACM SIGMOD International Conference on Management of Data, Phoenix, Ariz., pp. 183–194 (1997)
Xiao, X., Zheng, Y., Luo, Q., Xie, X.: Finding similar users using category-based location history. In: Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems - GIS 2010, pp. 442–445 (2010)
Zheng, Y., Zhang, L., Ma, Z., Xie, X., Ma, W.-Y.: Recommending friends and locations based on individual location history. ACM Trans. Web 5(1), 1–44 (2011)
Calabrese, F., Di Lorenzo, G., Ratti, C.: Human mobility prediction based on individual and collective geographical preferences. In: Proceedings of the IEEE Conference on Intelligent Transportation Systems, ITSC, pp. 312–317 (2010)
Jeong, J., Lee, K., Abdikamalov, B., Lee, K., Chong, S.: TravelMiner: on the benefit of path-based mobility prediction. In: 2016 13th Annual IEEE International Conference on Sensing, Communication, and Networking (SECON), London, UK, pp. 1–9 (2016)
Zheng, B., Xu, J., Member, S., Lee, D.L.: Cache invalidation and replacement strategies for location-dependent data in mobile environments. IEEE Trans. Comput. 51, 1141–1153 (2002)
Kumar, A., Misra, M., Sarje, A.K.: Strategies for cache invalidation of location dependent data in mobile environment. In: Proceedings of the 2005 International Conference on Parallel and Distributed Processing Techniques and Applications, PDPTA 2005, Las Vegas, Nevada, USA, pp. 38–44 (2005)
Ren, Q., Dunham, M.H.: Using semantic caching to manage location dependent data in mobile computing. In: 6th ACM/IEEE Mobile Computing and Networking (MobiCom), Boston, MA, USA, vol. 3, no. 2, pp. 210–221 (2000)
Seydim, A.Y., Dunham, M.H., Kumar, V.: Location dependent query processing. In: Proceedings of the 2nd ACM International Workshop on Data Engineering for Wireless and Mobile Access, pp. 47–53 (2001)
Madria, S.K., Bhargava, B., Pitoura, E., Kumar, V.: Data organization issues for location-dependent queries in mobile computing. In: Proceedings of the East-European Conference on Advances in Databases and Information Systems Held Jointly with International Conference on Database Systems for Advanced Applications: Current Issues in Databases and Information Systems, 05–08 September, pp. 142–156 (2000)
Ilarri, S., Mena, E., Illarramendi, A.: Location-dependent query processing: where we are and where we are heading. ACM Comput. Surv. 42(3), 12–73 (2010)
Wolfson, Y.Y.O., Sistla, A., Chamberlain, S.: Updating and querying databases that track mobile units. Distrib. Parallel Databases 7(3), 257–387 (1999)
Michael, K.: Location-based services : a vehicle for IT & T convergence. In: Advances in e-Engineering and Digital Enterprise Technology, pp. 467–477. Professional Engineering Publishing, University of Wollongong Research Online UK (2004)
Zhang, G., Liu, L., Seshadri, S., Bamba, B., Wang, Y.: Scalable and reliable location services through decentralized replication. In: 2009 IEEE International Conference on Web Services, ICWS 2009, pp. 632–638 (2009)
Wu, S.: Dynamic data management for location based services in mobile environments. In: Proceedings of the Seventh International Database Engineering and Application Symposium, pp. 180–189 (2003)
Patil, A.S.P., Nimbhorkar, S.U.: A survey on location based authentication protocols for mobile devices. IJCSN Int. J. Comput. Sci. Netw. 2(1), 44–47 (2013)
Babcock, B., Babu, S., Motwani, R., Datar, M.: Chain: operator scheduling for memory minimization in data. In: Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data - SIGMOD 2003, pp. 253–265 (2003)
Schroeder, B., Harchol-Balter, M., Iyengar, A., Nahum, E.: Achieving class-based QoS for transactional workloads. In: Proceedings of the International Conference on Data Engineering, vol. 2006, pp. 153–155 (2006)
Kjaergaard, M.B., Langdal, J., Godsk, T., Toftkjær, T.: EnTracked: energy-efficient robust position tracking for mobile devices. In: Proceedings of the 7th International Conference on Mobile Systems, Applications, and Services, pp. 221–234. ACM (2009)
Ravi, N., Scott, J., Han, L., Iftode, L.: Context-aware battery management for mobile phones. In: Proceedings of the Sixth Annual IEEE International Conference on Pervasive Computing and Communications, pp. 224–233. IEEE Computer Society (2008)
Thilliez, M., Delot, T., Lecomte, S.: An original positioning solution to evaluate location-dependent queries in wireless environments. J. Digit. Inf. Manag. Spec. Issue Distrib. Data Manag. 3(2), 108–113 (2005)
Zhu, X., Zhu, G., Guan, P.: Exploring location-aware process management. Geo-Informat. Resour. Manag. Sustain. Ecosyst. 399, 249–256 (2013)
Liang, T.Y., Li, Y.J.: A location-aware service deployment algorithm based on k-means for cloudlets. Mob. Inf. Syst. 2017, 1–10 (2017)
Michael, K.: Location-based services: a vehicle for IT & T convergence. In: Advances in e-Engineering and Digital Enterprise Technology, pp. 467–477. Professional Engineering Publishing, University of Wollongong Research Online UK (2004)
Joy, P.T., Jacob, K.P.: Cache replacement strategies for mobile data caching. Int. J. Ad Hoc Sens. 3(4), 1–9 (2012)
O’Neil, E.J., O’Neil, P.E., Weikum, G.: The LRU-K page replacement algorithm for database disk buffering. In: Proceedings of the ACM SIGMOD Conference, vol. 1, pp. 297–306 (1993)
Dar, S., Franklin, M.J., Jonsson, B.T., Srivastava, D., Tan, M.: Semantic data caching and replacement. In: VLDB, pp. 330–341 (1996)
Lai, K.Y., Tari, Z., Bertok, P.: Location-aware cache replacement for mobile environments. In: Global Telecommunications Conference, GLOBECOM 2004, vol. 6(11), pp. 3441–3447. IEEE, Dallas (2004)
Kumar, A., Misra, M., Sarje, A.K.: A predicted region based cache replacement policy for location dependent data in mobile environment. In: 10th Inter-Research-Institute Student Seminar in Computer Science, vol. 7, no. 2, pp. 1–8. IIIT, Hyderabad (2008)
Kumar, A., Misra, M., Sarje, A.K.: A weighted cache replacement policy for location dependent data in mobile environments. In: Proceedings of the 2007 ACM Symposium on Applied Computing, SAC 2007, Seoul, Republic, Korea, vol. 7, no. 3, pp. 920–924 (2007)
Kumar, A., Misra, M., Sarje, A.K.: A new cost function based cache replacement policy for location dependent data in mobile environment. In: 5th Annual Inter Research Institute Student Seminar in Computer Science, vol. 5, no. 1, pp. 1–8. Indian Institute Technology, Kanpur (2006)
Xu, J., Zheng, B., Lee, W.C., Lee, D.L.: The D-tree: An index structure for planar point queries in location- based wireless services. IEEE Trans. Knowl. Data Eng. 16(12), 1526–1542 (2004)
Huang, B., Wu, Q.: A spatial indexing approach for high performance location based services. J. Navig. 60(1), 83–93 (2007)
Jeong, J., Lee, K., Abdikamalov, B., Lee, K., Chong, S.: TravelMiner: on the benefit of path-based mobility prediction. In: 2016 13th Annual IEEE International Conference on Sensing, Communication, and Networking (SECON), London, UK, pp. 1–9 (2016)
Luo, X., Camp, T., Navidi, W.: Predictive methods for location services in mobile ad-hoc networks. IEEE Ubiquit. Comput. 3(4), 99–107 (2012)
Ying, J.J., Lee, W., Tseng, V.S.: Mining geographic-temporal-semantic patterns in trajectories for location prediction. ACM Trans. Intell. Syst. Technol. 5(1), 1–34 (2013)
Ying, J.J.-C., Lee, W.-C., Weng, T.-C., Tseng, V.S.: Semantic trajectory mining for location prediction. In: Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems - GIS 2011, pp. 34–40 (2011)
Körner, C., May, M., Wrobel, S.: Spatiotemporal modeling and analysis—introduction and overview. KI-Künstliche Intelligenz 26(3), 215–221 (2012)
Morzy, M.: Mining frequent trajectories of moving objects for location prediction. In: Proceedings of the 5th International Conference on Machine Learning and Data Mining in Pattern Recognition, MLDM 2007, pp. 667–680 (2007)
Lu, E.H.C., Tseng, V.S., Yu, P.S.: Mining cluster-based temporal mobile sequential patterns in location-based service environments. IEEE Trans. Knowl. Data Eng. 23(6), 914–927 (2011)
Gupta, A.K., Prakash, S.: Secure communication in cluster-based ad hoc networks: a review. In: Lobiyal, D.K., Mansotra, V., Singh, U. (eds.) Next-Generation Networks. AISC, vol. 638, pp. 537–545. Springer, Singapore (2018). https://doi.org/10.1007/978-981-10-6005-2_54
Gupta, A.K., Shanker, U.: Recent research trends on location dependent information systems. In: Springer International Conference on Pattern Recognition Techniques (ICPR 2017). Ambedkar Institute of Advanced Communication Technologies and Research, New Delhi, 22–23 December 2017
Gupta, A.K., Shanker, U.: SPMC-CRP: a cache replacement policy for location dependent data in mobile environment. In: Proceedings of the 6th International Conference on Smart Computing and Communications (ICSCC 2017), 7–8 December 2017, pp. 632–639. NIT, Kurukshetra (2017). https://doi.org/10.1016/j.procs.2017.12.081
Gupta, A.K., Shanker, U.: Modified predicted region based cache replacement policy for location dependent data in mobile environment. In: Proceedings of the 6th International Conference on Smart Computing and Communications (ICSCC 2017), 7–8 December 2017, pp. 917–924. NIT, Kurukshetra (2017). https://doi.org/10.1016/j.procs.2017.12.117
Gupta, A.K., Shanker, U.: SPMC-PRRP: a predicted region based cache replacement policy. In: Proceedings of the International Conference on Data and Information System (ICDIS-2017). Indira Gandhi National Tribal University (IGNTU), Amarkantak, 17–18 November 2017
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Gupta, A.K., Shanker, U. (2018). Location Dependent Information System’s Queries for Mobile Environment. In: Liu, C., Zou, L., Li, J. (eds) Database Systems for Advanced Applications. DASFAA 2018. Lecture Notes in Computer Science(), vol 10829. Springer, Cham. https://doi.org/10.1007/978-3-319-91455-8_19
Download citation
DOI: https://doi.org/10.1007/978-3-319-91455-8_19
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-91454-1
Online ISBN: 978-3-319-91455-8
eBook Packages: Computer ScienceComputer Science (R0)