A topology-based semantic location model for indoor applications

ABSTRACT

Location-based services (LBSs) play more and more important roles in our daily life with the prevalence of mobile devices and the internet. Location modeling is a significant research topic in LBSs, which is needed to provide a well-defined representation of location knowledge for location browsing, navigation and query processing. In this paper, we propose that a topological structure can be attached to an exit-location space model, which can preserve the topology and distance semantics between locations (exits). The Q-analysis developed by R. H. Atkin is used to analyze the semantic information of the model. Compared with those existing models which only reveal the relationships between two entities, this novel model can provide the analysis of n-ary relationships (i.e., the relations among n entities) from both local and global viewpoints. Moreover, by using the rich structures obtained from the topological analysis, we define a semantic distance which can support more meaningful navigation and queries on complicated indoor environments. Examples are described in detail to demonstrate the effectiveness of our model.

REFERENCES

• 1: R. Atkin. An approach to structure in architectural and urban design: 1. introduction and mathematical theory. Environment and Planning B, 1:56--67, 1974.
• 2: R. Atkin. An approach to structure in architectural and urban design: 2. algebraic representation and local structure. Environment and Planning B, 1:173--191, 1974.
• 3: R. Atkin. Mathematical Structure in Human Affairs. Heinemann, London, 1974.
• 4: R. Atkin. An approach to structure in architectural and urban design: 3. illustrative examples. Environment and Planning B, 2:21--57, 1975.
• 5: R. Atkin. Combinatorial Connectivities in Social Systems. Birkhauser, Basel, 1977.
• 6: R. Atkin. Multidimensional Man. Penguin Books, Harmondsworth, Middx, 1981.
• 7: John R. Beaumont, A description of structural change in a central place system: a speculation using q-analysis, International Journal of Man-Machine Studies, v.20 n.6, p.567-594, June 1984 [doi>10.1016/S0020-7373(84)80030-9]
• 8: J. R. Beaumont and A. C. Gatrell. An Introduction to Q-Analysis. Geo Abstracts, Norwich, 1982.
• 9: Christian Becker , Frank Dürr, On location models for ubiquitous computing, Personal and Ubiquitous Computing, v.9 n.1, p.20-31, January 2005 [doi>10.1007/s00779-004-0270-2]
• 10: B. Brumitt and S. Shafer. Topological world modeling using semantic spaces. In Proceedings of Location Modeling Workshop at Ubicomp, 2001.
• 11: R. Davies. Q-analysis: a methodology for librarianship and information science. Journal of Documentation, 41(4):221--246, 1985.
• 12: F. Dürr and K. Rothermel. On a location model for fine-grained geocast. In Proceedings of the 5th International Conference on Ubiquitous Computing (UbiComp'03), pages 18--35, 2003.
• 13: C. F. Earl and J. H. Johnson. Graph theory and q-analysis. Environment and Planning B: Planning and Design, 8(4):367--C391, 1981.
• 14: Max J. Egenhofer , Andrew U. Frank , Jeffrey P. Jackson, A Topological Data Model for Spatial Databases, Proceedings of the First Symposium on Design and Implementation of Large Spatial Databases, p.271-286, July 17-18, 1989
• 15: Prasanna Ganesan , Hector Garcia-Molina , Jennifer Widom, Exploiting hierarchical domain structure to compute similarity, ACM Transactions on Information Systems (TOIS), v.21 n.1, p.64-93, January 2003 [doi>10.1145/635484.635487]
• 16: P. Gould. Letting the data speak for themselves. Annals of the Association of American Geographers, 71:166--176, 1981.
• 17: P. Gould. A structural language of relations. Future Trends in Geomathematics, 1981.
• 18: P. Gould, J. Johnson, and G. Chapman. The Structure of Television. London: Pion Limited, 1984.
• 19: H. Hu and D. L. Lee. Semantic location modeling for location-aware application in mobile and ubiquitous computing. Technical Report, Hong Kong University of Science and Technology, 2003.
• 20: H. Hu and D. L. Lee. Semantic location modeling for location navigation in mobile environment. In Proceedings of the 5th International Conference on Mobile Data Management (MDM'04), pages 52--61, 2004.
• 21: P. Iravani. Discovering relevant sensor data by q-analysis. In Robot Soccer World Cup IX, pages 81--92, 2005.
• 22: Thomas L. Jacobson , David S. Fusani , Wenjie Yan, Q-analysis of user-database interaction, International Journal of Man-Machine Studies, v.38 n.5, p.787-803, May 1993 [doi>10.1006/imms.1993.1037]
• 23: B. Jiang and I. Omer. Spatial topology and its structure analysis based on the concept of simplicial complex. to appear in Transactions in GIS, 2007.
• 24: Changhao Jiang , Peter Steenkiste, A Hybrid Location Model with a Computable Location Identifier for Ubiquitous Computing, Proceedings of the 4th international conference on Ubiquitous Computing, p.246-263, September 29-October 01, 2002, Göteborg, Sweden
• 25: W. Kainz, M. Egenhofer, and I. Greasley. Modeling spatial relations and operations with partially ordered sets. International Journal of Geographical Information Systems, 7:215--229, 1993.
• 26: B. S. Karlsen. Enabling a Ubiquitous Location Based Service on Campus. Master Thesis, Norwegian University of Science and Technology, 2006.
• 27: C. P. Kwong. Simplexes, Q-analysis, and Information Retrieval. Technical Report CUHK-ACE-03-03, The Chinese University of Hong Kong, 2003.
• 28: Dik Lun Lee , Manli Zhu , Haibo Hu, When location-based services meet databases, Mobile Information Systems, v.1 n.2, p.81-90, April 2005
• 29: U. Leonhardt. Supporting Location-Awareness in Open Distributed Systems. PhD Thesis, Department of Computing, Imperial College London, 1998.
• 30: Dandan Li , Chung-Ping Kwong, Geometric and topological approaches to semantic text retrieval, The Chinese University of Hong Kong (People's Republic of China), 2007
• 31: D. D. Li and C. P. Kwong. Understanding latent semantic indexing: A topological structure analysis using q-analysis method. In Proceedings of the 2007 International Conference on Information and Knowledge Engineering, pages 110--116, 2007.
• 32: T. O'Connell, P. Jensen, A. Dey, and G. Abowd. Location in the aware home. In Proceedings of Location Modeling Workshop at Ubicomp, pages 41--44, 2001.
• 33: T. Pederson. Object location modeling in office environments - first steps. In Proceedings of Location Modeling Workshop at Ubicomp, 2001.
• 34: Salil Pradhan, Semantic Location, Personal and Ubiquitous Computing, v.4 n.4, p.213-216, August 2000 [doi>10.1007/s007790070005]
• 35: C. Schlieder, T. Vogele, and A. Werner. Location modeling for intentional behaviour in spatial partonomies. In Proceedings of Location Modeling Workshop at Ubicomp, 2001.
• 36: S. Steiniger, M. Neun, and A. Edwardes. Foundations of Location Based Services. Lecture Notes on LBS, Department of Geography, University of Zürich, 2006.
• 37: E. Valencia and J. L. Giavitto. Algebraic topology for knowledge representation in analogy solving. In European Conference on Artificial Intelligence (ECAI98), pages 23--28, 1998.
• 38: J. Ye, L. Coyle, S. Dobson, and P. Nixon. A unified semantic space model. In Lecture Notes in Computer Science, volume 4718, pages 103--120, 2007.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.2 Information Storage
      H.3.3 Information Search and Retrieval

General Terms:
Algorithms, Theory

Keywords:
Q-analysis, connectiveness, semantic location model, simplicial family, topology