Predicting future locations using prediction-by-partial-match

ABSTRACT

We implemented the Prediction-by-Partial-Match data compression algorithm as a predictor of future locations. Positioning was done using IEEE 802.11 wireless access logs. Several experiments were run to determine how to divide the data for training and testing and how to best represent the data as a string of symbols. Our test data consisted of 198 datasets containing over 28,000

REFERENCES

• 1: Padgett, L. 1945. What You Need. Astounding Science Fiction, 37 (Oct. 1945), 133--146.
• 2: Daniel Ashbrook , Thad Starner, Using GPS to learn significant locations and predict movement across multiple users, Personal and Ubiquitous Computing, v.7 n.5, p.275-286, October 2003 [doi>10.1007/s00779-003-0240-0]
• 3: Chen, I. K., Coffey, J. T., and Mudge, T. N. 1996. Analysis of branch prediction via data compression. SIGOPS Oper. Syst. Rev. 30, 5 (Dec. 1996), 128--137. DOI= http://doi.acm.org/10.1145/248208.237171
• 4: Jeffrey Scott Vitter , P. Krishnan, Optimal prefetching via data compression, Journal of the ACM (JACM), v.43 n.5, p.771-793, Sept. 1996 [doi>10.1145/234752.234753]
• 5: Mukund Deshpande , George Karypis, Selective Markov models for predicting Web page accesses, ACM Transactions on Internet Technology (TOIT), v.4 n.2, p.163-184, May 2004 [doi>10.1145/990301.990304]
• 6: Das, S. K., Cook, D. J., Battacharya, A., Heierman, E. O., III, and Tze-Yun, L. 2002. The role of prediction algorithms in the MavHome smart home architecture. IEEE Wireless Communications, 9, 77--84,
• 7: Roy, A., Das, S. K., and Basu, K. 2007. A Predictive Framework for Location-Aware Resource Management in Smart Homes. IEEE Transactions on Mobile Computing, 6, 1284--1283.
• 8: Ziv, J. and Lempel, A. 1978. Compression of individual sequences via variable--rate coding. IEEE Transactions on Information Theory, 24, 530--536.
• 9: D. Ashbrook, Learning Significant Locations and Predicting User Movement with GPS, Proceedings of the 6th IEEE International Symposium on Wearable Computers, p.101, October 07-10, 2002
• 10: Song, L., Kotz, D., Jain, R., and He, X. 2004. Evaluating location predictors with extensive Wi-Fi mobility data. In Proceedings of the Joint Conference of the IEEE Computer and Communications Societies. INFOCOMM 2004. 2, 1414--1424.
• 11: LaMarca, A., Chawathe, Y., Consolvo, S., et al. 2005. Place Lab: Device Positioning Using Radio Beacons in the Wild. in Proceedings of Pervasive 2005 (Munich, Germany, May 8-13, 2005), 3468, 116--133.
• 12: Rosco Hill , James Begole, Activity rhythm detection and modeling, CHI '03 extended abstracts on Human factors in computing systems, April 05-10, 2003, Ft. Lauderdale, Florida, USA [doi>10.1145/765891.765989]
• 13: James Bo Begole , John C. Tang , Rosco Hill, Rhythm modeling, visualizations and applications, Proceedings of the 16th annual ACM symposium on User interface software and technology, p.11-20, November 02-05, 2003, Vancouver, Canada [doi>10.1145/964696.964698]
• 14: Begleiter, R., El-Yaniv, R., and Yona, G. 2004. On Prediction Using Variable Order Markov Models. Journal of Artificial Intelligence Research, 22, 385--421.
• 15: McNett, M. and Voelker, G. M. 2005.UCSD Wireless Topology Discovery Trace. Support for the UCSD Wireless Topology Discovery Trace was provided by DARPA Contract N66001--01--1--8933. URL= http://sysnet.ucsd.edu/wtd/
• 16: Cleary, J. and Witten, I. 1984. Data Compression Using Adaptive Coding and Partial String Matching. IEEE Transactions on Communications, 32, 396--402.
• 17: J. G. Cleary , W. J. Teahan , I. H. Witten, Unbounded length contexts for PPM, Proceedings of the Conference on Data Compression, p.52, March 28-30, 1995
• 18: Nelson, M. 1991. Arithmetic Coding + Statistical Modeling = Data Compression. Dr. Dobb's Journal, Feb 1991.
• 19: Chris Thornton, Truth from trash: how learning makes sense, MIT Press, Cambridge, MA, 2000

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Experimentation

Keywords:
data compression, prediction, supervised learning, wifi positioning