Hoarding location-based data using clustering

ABSTRACT

The proliferation of mobile devices and the fact that high-bandwidth and continuous connectivity is not available everywhere, has led to the creation of hoarding algorithms that attempt to mitigate the problems related with disconnected operation and with the operation in areas where bandwidth is either scarce or expensive. In this paper, we present a hoarding scheme for location-based data in semi-structured information spaces, such as the World Wide Web, which relies on clustering of semantically related data items. We show by means of experimental evaluation that our clustering-based approach outperforms existing hoarding techniques that do not make use of clustering by a factor of more than 2 in terms of hoard cache hit ratio.

REFERENCES

• 1: Characterizing the scalability of a large web-based shopping system, ACM Transactions on Internet Technology (TOIT), v.1 n.1, p.44-69, Aug. 2001 [doi>10.1145/383034.383036]
• 2: D. Badrinath, T. Imielinski, R. Frenkiel, and D. Goodman. Nimble: Many-time, many-where communication support for information systems in highly mobile and wireless environments. http://www.cs.rutgers.edu/dataman/nimble/, 1996.
• 3: Albert-László Barabási and Eric Bonabeau. Scale-free networks. Scientific American, May 2003.
• 4: Doug Beeferman , Adam Berger, Agglomerative clustering of a search engine query log, Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining, p.407-416, August 20-23, 2000, Boston, Massachusetts, United States [doi>10.1145/347090.347176]
• 5: Susanne Burklen , Pedro Jose Marron , Serena Fritsch , Kurt Rothermel, User Centric Walk: An Integrated Approach for Modeling the Browsing Behavior of Users on the Web, Proceedings of the 38th annual Symposium on Simulation, p.149-159, April 04-06, 2005 [doi>10.1109/ANSS.2005.44]
• 6: Susanne Bürklen, Pedro José Marrón, and Kurt Rothermel. An enhanced hoarding approach based on graph analysis. In Proc. of the IEEE Int. Conf. on Mobile Data Management (MDM 2004), Berkeley, CA, USA, pages 358--369, 2004.
• 7: Keith Cheverst , Nigel Davies , Keith Mitchell , Adrian Friday , Christos Efstratiou, Developing a context-aware electronic tourist guide: some issues and experiences, Proceedings of the SIGCHI conference on Human factors in computing systems, p.17-24, April 01-06, 2000, The Hague, The Netherlands [doi>10.1145/332040.332047]
• 8: D. B. Crouch , C. J. Crouch , G. Andreas, The use of cluster hierarchies in hypertext information retrieval, Proceedings of the second annual ACM conference on Hypertext, p.225-237, November 1989, Pittsburgh, Pennsylvania, United States [doi>10.1145/74224.74243]
• 9: Stephen Dill , Ravi Kumar , Kevin S. McCurley , Sridhar Rajagopalan , D. Sivakumar , Andrew Tomkins, Self-similarity in the Web, Proceedings of the 27th International Conference on Very Large Data Bases, p.69-78, September 11-14, 2001
• 10: Jim Griffioen and Randy Appleton. Reducing file system latency using a predictive approach. In USENIX Summer, pages 197--207, 1994.
• 11: James J. Kistler , M. Satyanarayanan, Disconnected operation in the Coda File System, ACM Transactions on Computer Systems (TOCS), v.10 n.1, p.3-25, Feb. 1992 [doi>10.1145/146941.146942]
• 12: Uwe Kubach , Kurt Rothermel, Exploiting location information for infostation-based hoarding, Proceedings of the 7th annual international conference on Mobile computing and networking, p.15-27, July 2001, Rome, Italy [doi>10.1145/381677.381680]
• 13: Geoffrey H. Kuenning , Wilkie Ma , Peter Reiher , Gerald J. Popek, Simplifying automated hoarding methods, Proceedings of the 5th ACM international workshop on Modeling analysis and simulation of wireless and mobile systems, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570758.570762]
• 14: Geoffrey H. Kuenning , Gerald J. Popek, Automated hoarding for mobile computers, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.264-275, October 05-08, 1997, Saint Malo, France
• 15: Kwong Lai and Zahir Tari and Peter Bertok. Supporting Disconnected Operations Through Cooperative Hoarding. In Proc. of Int. Conf. on Computer Communications and Networks (ICCCN), October 2005.
• 16: Xiaoyong Liu , W. Bruce Croft, Cluster-based retrieval using language models, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009026]
• 17: Bruce A. Mah, An Empirical Model of HTTP Network Traffic, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.592, April 09-11, 1997
• 18: Manuel J. Maña-López , Manuel De Buenaga , José M. Gómez-Hidalgo, Multidocument summarization: An added value to clustering in interactive retrieval, ACM Transactions on Information Systems (TOIS), v.22 n.2, p.215-241, April 2004 [doi>10.1145/984321.984323]
• 19: O. Ratsimor and S. Balaji Kodeswaran and A. Joshi and T. Finin and Y. Yesha. Combining Infrastructure and Ad hoc Collaboration For Data Management in Mobile Wireless Networks. In Workshop on Ad hoc Communications and Collaboration in Ubiquitous Computing Environments, 2002.
• 20: Stefan Podlipnig , Laszlo Böszörmenyi, A survey of Web cache replacement strategies, ACM Computing Surveys (CSUR), v.35 n.4, p.374-398, December 2003 [doi>10.1145/954339.954341]
• 21: Qun Ren , Margaret H. Dunham, Using semantic caching to manage location dependent data in mobile computing, Proceedings of the 6th annual international conference on Mobile computing and networking, p.210-221, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345948]
• 22: A. Reyes-Lecuona, E. González-Parada, E. Casilari, and A. Díaz-Estrella. A page-oriented www traffic model for wireless system simulations. In Proceddings of the 16th Int. Teletraffic Congress (ITC'16), Edinburgh, UK, pages 1271--1280, 1999.
• 23: Carl Tait , Hui Lei , Swarup Acharya , Henry Chang, Intelligent file hoarding for mobile computers, Proceedings of the 1st annual international conference on Mobile computing and networking, p.119-125, November 13-15, 1995, Berkeley, California, United States [doi>10.1145/215530.215564]
• 24: N. J. Tuah , M. J. Kumar , S. Venkatesh, Performance modelling of speculative prefetching for compound requests in low bandwidth networks, Proceedings of the 3rd ACM international workshop on Wireless mobile multimedia, p.83-92, August 11-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345867.345899]
• 25: Tao Ye , H.-Arno Jacobsen , Randy Katz, Mobile awareness in a wide area wireless network of info-stations, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.109-120, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288264]
• 26: Jinsuo Zhang , Abdelsalam (Sumi) Helal , Joachim Hammer, UbiData: ubiquitous mobile file service, Proceedings of the 2003 ACM symposium on Applied computing, March 09-12, 2003, Melbourne, Florida [doi>10.1145/952532.952708]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.5 On-line Information Services

General Terms:
Algorithms, Management

Keywords:
hoarding, location-based systems