Advanced
Topological Analysis in Indoor Shopping Mall using Ontology
Topological Analysis in Indoor Shopping Mall using Ontology
Journal of the Korean Society of Surveying, Geodesy, Photogrammetry and Cartography. 2013. Nov, 31(6_2): 511-520
Copyright © 2013, Korean Society of Surveying, Geodesy, Photogrammetry and Cartography
This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • Received : June 06, 2013
  • Accepted : December 12, 2013
  • Published : November 28, 2013
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
Kangjae Lee
Regular MemberㆍDept. of Geoinformatics, University of Seoul (E-mail:kjlee@uos.ac.kr)
Hye-Young Kang
Co-AuthorㆍDept. of Geoinformatics, University of Seoul (E-mail:hyezero@gmail.com)
Jiyeong Lee
Corresponding AuthorㆍDept. of Geoinformatics, University of Seoul (E-mail:jlee@uos.ac.kr)
Abstract
Recently, human activities have expanded from outdoor spaces to indoor spaces since a lot of complex buildings were constructed over the world. Especially, visitors in a shopping mall would like to receive specific information of interest regarding various shopping-related activities as well as shopping itself. However, when it comes to providing the information, existing guide services have some drawbacks. Firstly, the existing services cannot provide visitors with the information of other stores simply and promptly on the current location. Secondly, the services have difficulties in representation and share of the shopping-related knowledge, and in providing inferred information. Thus, the purpose of this study is to develop a method that allows topological analysis utilizing ontology technique around the current position in such shopping mall in order to provide shopping-related information. For this, the shopping activity ontology model is designed, and based on the ontology model, inferencing rules are defined in order to extract the information of interest efficiently through semantic queries. Also, a geocoding method in indoor spaces is used regarding the current location, and optimal routing analysis, which is one of topological analysis, is applied with the result from the semantic queries. As a result, an Android application is developed for 3D visualization and user interface.
Keywords
1. Introduction
Recently, human activities have expanded from outdoor spaces to indoor spaces since a lot of complex buildings were constructed such as Pacific place in Seattle and Glendale galleria in Los Angeles, USA, COEX in Gangnam, South Korea and Dubai mall in Dubai, UAE. In such large and complex malls, visitors would like to receive specific information of interest quickly and in detail regarding various shopping-related activities. For example, they may would like to find a movie theatre, the Italian restaurant serving Carbonara as well as shoe stores. However, when it comes to providing the information, existing guide services have some drawbacks. First of all, guide maps or installed guide systems provide categorized information and locations about stores or restaurants. But the problem is that visitors would like to receive the information simply and promptly on the position in which they are located. Second, the services have difficulties in representation and share of the shopping-related knowledge, and in providing inferred information. It means that since existing search system is generally developed based on relational model, the services cannot efficiently suggest related information semantically to visitors. So semantic search based on topological analysis in mobile computing environment can be very handy. With mobile devices, visitors can obtain information everywhere quickly in complex buildings. Also, semantic search can support providing shopping-related information with reasoning based on logical relationships between concepts. In order to support semantic search, an ontology model should be designed in advance for understanding the meaning of lexical-semantic information.
An ontology conceptually represents domain knowledge shared between users and computers. An ontology is an explicit specification of concepts and describable relationships in the knowledge of a domain(Gruber, 1995). And the ontology contains concepts of the knowledge, properties of each concept and restrictions on the properties(Noy et al ., 2001). So an ontology enables semantic search to identify the concept of given keyword finding related information for shopping or eating. In terms of utilization of ontology technique focusing on indoor spaces, a number of researches have been carried out so far(Wang et al ., 2004; Anacleto et al ., 2011). However, the researches pay attention to either an ontology model for indoor contexts roughly in high concept level or shopping recommendation system without efficient indoor positioning technique.
Thus, considering the rapid increase of complex malls, the purpose of this study is to develop a method that allows providing shopping-related information through semantic queries and topological analysis based on the current location in a shopping mall. For this, the scope of this study consists three steps. Firstly, a geocoding method on character matching(Lee and Lee, 2013) is used regarding the current location. The method is efficient in mobile computing environment without complex computational effort for indoor positioning. Secondly, the shopping activity ontology model is designed for the semantic queries, and inferencing rules are defined in order to extract the information of interest. The ontology model can structure and manage data semantically, and increase efficiency of semantic queries. Lastly, optimal routing analysis, one of topological analysis, is integrated with the result from the semantic queries. In other words, the semantic queries based on the shopping activity ontology are processed to find a Point of Interest(POI) such as a specific store, restaurant or theater using the optimal routing analysis. Especially, three-dimensional network data model in indoor spaces(Lee, 2004) is applied for topological analysis.
For the implementation of this research, the shopping activity ontology is stored as Resource Description Framework(RDF) structure in Oracle Database 11g Release 2, and Oracle Database Semantic Technologies are applied to handle semantic queries. Furthermore, user interface and the result of 3D topological analysis are displayed onto an Android application.
2. Related Works
- 2.1 Ontology modeling
When it comes to the process of developing ontologies, a research on a skeletal methodology was carried out(Uschold et al ., 1996). The methodology was designed as a comprehensive methodology including 5 stages : Identify Purpose and Scope, Building an Ontology, Evaluation, Documentation, and Guidelines for each phase. Also, a simple knowledge-engineering methodology was designed with 7 steps in another research(Noy et al ., 2001), and fundamental rules for the methodology were made as follows : 1) The methodology to model a domain can be two or more, not only one. 2) Process for developing an ontology is repetitive. 3) The developed ontology should describe concepts identical with objects and relationships among them.
For the use of ontologies, numerous researches have been carried out in various domains. In particular, an ontology dealing with location information semantically was proposed in Location Based Services(LBS) domain(Liu et al ., 2008). A spatial ontology was constructed in order to present semantic information. The spatial ontology was a domain ontology describing concepts on entities including services, people and mobile devices, and regions of indoor and outdoor spaces. Especially, Region Connection Calculus(RCC) (Randell et al ., 1992) was applied to the regions for spatial reasoning. In addition, a research on effective description of location based services was presented based on the proposed location ontology(Lemmens et al ., 2004). The location ontology differentiated location based services depending on the types of input and output data, and in particular, it defined operations and geo-data as a core part. The concept of features contained in geo-data class played an important role in the research. It included the descriptions with respect to locations depending on service types, geometry types and thematic information.
In terms of outdoor and indoor spaces, context ontology was developed considering a high-level ontology for general concepts of context as well as low-level ontologies for domain-specific knowledge(Wang et al ., 2004). The context entities such as location, person and activity with their subclasses, and properties of the classes were defined in the upper ontology. An application domain, for example, smart home or office domain ontology, were defined as the lower ontology.
- 2.2 Path finding and shopping information
For finding an optimal path in indoor spaces, firstly network- based topological data model should be defined. Researches on the definition of 3D topological data model(Lee, 2004) and its utilization(Lee, 2007; Lee, 2008; Lee and Lee, 2012) were carried out. The network data model used Node-Relation Structure(NRS) concept adopting Poincaréduality(Munkres, 1984) in order to transform topological spaces into duality spaces so that it could define duality graph. When it comes to Poincaréduality, a three-dimensional spatial object was presented as a zero-dimensional point object, and a two-dimensional spatial object was defined as a one-dimensional line object. Also, a one-dimensional spatial object was shown as a two-dimensional polygon object, and a zero-dimensional spatial object was expressed as a three-dimensional solid object. Particularly, connectivity and adjacency were defined between spatial objects such as rooms, corridors or elevators. Among the spatial objects, corridors were typically narrow and long, and connected with many rooms. Thus, subdividing the corridors( Fig. 1b ) was inevitable in order to prevent one node of a corridor from being connected with each node of rooms as radial form( Fig. 1a ). Eventually, subdividing enabled routing analysis to involve sub-divided corridor spaces and their connectivities to individual rooms considering geometric network structure as shown in Fig. 1c . The application of the network data model was studied in a way of emergency response like in case of fire so far.
PPT Slide
Lager Image
Network structure considering sub-dividing process(Lee, 2004)
On the basis of integrating network data model with ontology, a research on semantic navigation was carried out(Tsetsos et al ., 2005). OntoNav, proposed system in the research, provided human centric navigation services processing physical and perceptual capabilities as well as preference of passengers in indoor spaces. In particular, graph-based algorithm network data model was applied for navigation, and the resulting paths are searched taking into account the capabilities of handicapped people. With respect to shopping information, systems and methodologies for shopping assistance and advertising were proposed using indoor positioning technology. One research dealt with tracking users in a shopping center, and recommending services depending on a kind of users which might be a visitor, shop manager or security guard(Anacleto et al ., 2011). Although the research stated that interactions between users and recommended services should be modeled using an ontology, it remained for future work. Also, the proposed system in the research used several inefficient sensors on users' body for indoor tracking.
In this study, we concentrates on constructing an ontology model about available activities in large shopping malls. In addition, this research particularly focuses on integrating topological analysis based on 3D network data model into both indoor geocoding method on character matching and semantic queries.
3. Methodology
For topological analysis using semantic queries in indoor spaces, the core part of this research is divided into three sections as shown in Fig. 2 . First, a geocoding method on character matching using descriptive data is applied to find current location of a visitor. Second, shopping activity ontology is designed hierarchically through many steps. Third, semantic queries are applied using inferencing rules in order to find a destination, in which a visitor would like to go, and 3D network data model is used to estimate an optimal route.
PPT Slide
Lager Image
Overview of proposed methodology
- 3.1 Geocoding Method
A source location in indoor spaces should be determined using positioning technique. In this study, a geocoding method on character matching(Lee and Lee, 2013) is applied to extract geographic coordinates as room-level accuracy as shown in Fig. 3 . Character matching is a core technique in the method in order to extract text data from the descriptive data such as a business name, phone number or room number on the front sign of each store or restaurant in a shopping mall. The descriptive data is captured by digital camera equipped in a smart phone, and goes through parsing and matching processes making a comparison between the text data and reference database. As a result of the processes, geographic coordinates of a store or restaurant in which a visitor is located are extracted.
PPT Slide
Lager Image
Flow Diagram of geocoding method on character matching
- 3.2 Shopping Activity Ontology
The shopping activity ontology is developed based on the flow of 7 steps modeling approach(Noy et al ., 2001) mentioned in the previous chapter. The modeling process of the ontology is summarized into 4 steps as follows :
  • ① Determining domain
  • ② Listing terms
  • ③ Defining class hierarchy
  • ④ Generating instances
First of all, the domain of the shopping activity ontology is delimited in the range of possible activities in shopping malls. So the ontology focuses on physical spaces like rooms, and activities occurring in the spaces like buying clothing or watching a movie and having a meal. Specifically, the ontology modeling is oriented to the purposes and needs of shopping visitors. So we collected possible questions about activities in large shopping malls, and some of organized competency questions(Gruninger et al ., 1995) are listed as shown in Table 1 . The competency questions can help define the scope of domain information and a specific level of detail. Through the competency questions, considerations for modeling ontology are extracted including types of activities, class hierarchy and properties.
Competency questions for modeling shopping ontology
PPT Slide
Lager Image
Competency questions for modeling shopping ontology
Second, all the possible terms for shopping ontology can be found in many shopping mall homepages, shopping books and relevant ontology libraries. Individual terms are enumerated for corresponding to each class or property of the shopping activity ontology.
Third, the class hierarchy of the shopping activity ontology is developed based on competency questions, many shopping mall home-pages. The upper ontology is slightly modified based on the context ontology(Wang et al ., 2004), and the lower ontology, an important part in this research, is designed to focus on conceptualizing shopping activities and related indoor spaces. The structure of the shopping activity ontology is depicted partially in Fig. 4 . The structure is divided into two parts, upper ontology for a general concept and lower ontology for a domain-specific concept. The 'Thing' is the super concept of all kinds of upper ontologies. 'Activity' and 'Space' classes inherit from the 'Thing' class, and both of them include sub-classes separately. One of them, the 'Space' class is divided into 'IndoorSpace' and 'OutdoorSpace'. In particular, 'IndoorSpace' class derives 'Building' including 'Room', 'Passage' and 'Exit'sub-classes. The 'Activity' class can be classified into entertainment, shopping, eating, parking, rest and service.
PPT Slide
Lager Image
Overall hierarchy of shopping ontology
Specifically, each activity class has individual sub-classes depending on its own type as partially shown in Fig. 5 . Also each activity has its own properties according to its distinct characteristics using appropriate data types, relating to subclasses of 'Room'class. Because most activities in shopping malls occur in individual room, each activity has a 'occur_in' relation property to a room for business or facility. In addition, the product level relation properties between sub-classes of 'Activity' and 'Space' class are designed in the ontology. For example, the 'Store' class has 'sell' relation properties to the 'Top', 'Bottom', 'Belt', etc classes so that visitors can retrieve stores which sell a specific type of product.
PPT Slide
Lager Image
Specific classes of possible activities in a shopping mall
Lastly, instances are created according to the defined classes and their properties of the shopping activity ontology model, to store level and product level. Creating individual instances is described in the chapter 4 in detail.
- 3.3 Topological Analysis based on Semantic Query
Semantic queries are designed covering user requirements based on the competency questions noted in the previous section. Inferencing rules are applied to analyze the relations of classes. Inferencing helps semantic queries performed based on logical reasoning and semantic relationships. For instance, the'styleOf' rule can be defined considering predefined relation property named 'sells' and each instance of 'Italian restaurant' class so that it is used to deduce the style of restaurant as shown in Fig. 6 . Applying this rule, any other Italian restaurants can be searched and recommended apart from the 'Benigans' restaurant, in which a visitor might be located.
PPT Slide
Lager Image
Creating inferencing rule
Next, for utilizing the result of semantic queries topologically, 3D network-based topological data model(Lee, 2004) based on Node-Relation Structure(NRS) concept is applied. Structure of the network data model is a combination of connected nodes and edges as shown in Fig. 7 . In particular, connectivity as one of topological relationships is defined between spatial objects for optimal route analysis, and subdividing is performed.
PPT Slide
Lager Image
Network Data Structure
Finally, the whole optimal route analysis algorithm using indoor geocoding method on character matching and semantic query process is defined as shown in Fig. 8 . First of all, the given descriptive data d is used as an input data of IndoorGeocoding function. Next, the current position data extracted from the IndoorGeocoding function is stored in the pt1 . The pt1 is matched with each room node rn1 contained in vertex set V[N] , and after the process, a coincident node rn1 that is identical to the pt1 , is set as a source node s for route analysis. And next, a point pt2 that is extracted through the SemanticQP function, is also matched with each room node rn2 . A target node t is defined using a coincident node rn2 . Lastly, Dijkstra algorithm(Dijkstra, 1959) is implemented for finding an optimal route from the source node s to target node t with four kinds of parameters, namely, 3D network data model N , edge weight value w , and the source and target nodes. As a result, this whole procedure returns edge list e of the route.
PPT Slide
Lager Image
Route analysis based on geocoding method using semantic query
4. Implementation
For the implementation, the Android application is developed. In particular, Oracle 11g R2 is used to store sample data and process query statements.
Development environment for semantic queries and 3D visualization
PPT Slide
Lager Image
Development environment for semantic queries and 3D visualization
The study area is COEX building, in which a huge underground mall, convention halls, galleries and a few restaurants are located. The COEX is geometrically defined and displayed as three-dimensional footprint for the topological analysis. The implementation for this study consists of four stages as follows:
  • ① Indoor geocoding in order to find a source location
  • ② Creating sample data of shopping activity ontology
  • ③ Query processing based on the sample data and inferencing
  • ④ Finding an optimal route from a source location to a target location
In the first stage, descriptive data is captured by a built-in digital camera of a smart phone, and a current position of a visitor is displayed through indoor geocoding method as shown in Fig. 9 .
PPT Slide
Lager Image
Indoor geocoding method for determining a source location (Lee and Lee, 2013)
In the second stage as shown in Fig. 10 , ontology table is created using semantic technologies in Oracle Database 11g R2 in order to store sample data in RDF format and use various semantic functions. RDF triple structure consists of a subject, predicate, and an object. For example, if a noun 'Starbucks' is a subject, a verb 'Sells' can be a predicate, and a noun 'Coffee' can be an object. And then, an ontology model is created based on the structured shopping mall ontology including designed classes through RDF_TRIPLE function.
PPT Slide
Lager Image
Creating tables and storing classes using PL/SQL statements
Next, each instance of many classes is stored along the structured ontology model in the table. For example, 'Benigans', a subject, is related to an object 'Italian' restaurant using a RDF property 'rdf:type', a predicate, as shown in Fig. 11 . Each relationship property like 'sells' between two kinds of instances can be defined in RDF format. Also, properties of each instance such as a phone number, store name, floor and room number can be stored as text or numeric data.
PPT Slide
Lager Image
Creating instances and defining properties using PL/SQL statements
In the third stage, inferencing rules, for example 'styleOf' rule, are stored using rule-base functions as shown in Fig. 12 . After shopping activity ontology model is defined well and sample data is stored completely, semantic query process is executed using JSP interacting between the Android application and the ontology database. For example, not only can a user find some restaurants serving Carbonara pasta but also other same style restaurants not serving the Carbonara be recommended using SEM_MATCH function with 'styleOf' inferencing rule. For receiving a food name or shopping product name, a parameter, in this example namely 'namevar1', is involved.
PPT Slide
Lager Image
Defining inferencing rules and retrieving semantic information
In the last stage, a user can input keywords in the user interface of the developed application( Fig. 13a ). A user can choose types of activities and find specific places such as stores or restaurants by typing a keyword. For example, if a user type 'Carbonara' and click the 'Search' button, the restaurants' list containing not only exact results serving the food but also other Italian style restaurants not serving the food is displayed with the information about individual place. Also, the user interface provides a user with useful information considering class hierarchy based on the shopping activity ontology. To be specific, a user can find stores selling accessories, and also check which kinds of accessories are sold in the stores in detail( Fig. 13b ). Lastly, if a user click the one of them in the displayed list, the target POI is decided and a 3D optimal route from the source location to the target location is analyzed and visualized based on 3D network model( Fig. 13c ).
PPT Slide
Lager Image
Semantic query process and topological analysis in the user interface
5. Conclusion
To sum up, the purpose of this study is to develop a method that allows topological analysis utilizing ontology technique around the current position in a shopping mall in order to provide shopping-related information. For this, firstly, a geocoding method on character matching was applied. Secondly, shopping activity ontology was designed to structure and manage data semantically. Thirdly, inferencing rules for semantic queries based on the shopping activity ontology were designed, and 3D network data model in indoor spaces was adopted for topological analysis. Finally, the route analysis algorithm was proposed according to the previous process.
For the implementation of this research, sample ontology data was stored as RDF structure in Oracle Database 11g Release 2, and Oracle Database Semantic Technologies were used to handle semantic queries. As a result, Android application was developed for 3D visualization of a shopping mall and semantic query process so that users can search the shopping-related information with high satisfaction.
This study has a great significance in that a standardized form of location-based services for the use of shopping-related information in indoor spaces is proposed and designed integrating ontology technique and semantic queries. Ultimately, semantic query process enables related search in order to allow to increase the availability of the ontology model. By searching the shopping-related information semantically and providing the desired information through topological analysis, the proposed method widened the availability of the ontology model, and could be an application method for location based services in indoor spaces.
For further researches, query processing using more various reasoning considering user preference for advertisement and recommendation can be considered. Also, advanced parsing and filtering method in order to develop a complete semantic search system in indoor spaces should follow.
Acknowledgements
This work was supported by the National Research Foundation of Korea(NRF) grant funded by the Korea government(MEST)(No. 2012-0002348).
References
Anacleto R. , Luz N. , Almeida A. , Figueiredo L. , Novais P. 2011 Shopping center tracking and recommendation systems, In Soft Computing Models in Industrial and Environmental Applications 6th International Conference SOCO 2011 299 - 308
Dijkstra E.W. 1959 A note on two problems in connexion with graphs Numerische mathematick 1 (1) 269 - 271
Gruber T. R. 1995 Toward principles for the design of ontologies used for knowledge sharing International journal of human computer studies 43 (5) 907 - 928
Gruninger M. , Fox M. S. 1995 Methodology for the design and evaluation of ontologies IJCAI Proceedings of the Workshop on Basic Ontological Issues in Knowledge Sharing
Lee J. 2004 A spatial access-oriented implementation of a 3-D GIS topological data model for urban entities GeoInformatica 8 (3) 237 - 264
Lee J. 2007 A three-dimensional navigable data model to support emergency response in microspatial builtenvironments Annals of the Association of American Geographers 97 (3) 512 - 529
Lee J. , Zlatanova S. , Zlatanova S. , Bristol J. Li. 2008 Geo-information technology for emergency response Taylor&Francis PA A 3D data model and topological analyses for emergency response in urban areas
Lee K. , Lee J. 2013 A Geocoding Method on Character Matching in Indoor Spaces Journal of Korea Spatial Information Society 21 (1) 87 - 100
Lee S. J. , Lee J. 2012 Finding Isolated Zones through Connectivity Relationship Analysis in Indoor Space Korean Journal of Geomatics 30 (3) 229 - 240
Lemmens R. , de Vries M. 2004 Semantic description of location based web services using an extensible location ontology Proceedings of Munster GI-days 261 - 276
Liu D. , Chen J. , Guo J. 2008 Wireless Communications, Networking and Mobile Computing WiCOM'08. 4th International Conference on IEEE An ontology-based LBS system 1 - 4
Munkres J. R. 1984 Elements of Algebraic Topology Addison-Wesley Menlo Park, CA
Noy N. F. , Deborah L. M. 2001 Ontology development 101: A guide to creating your first ontology Stanford University http://protege.stanford.edu/publications/ ontology_development/ontology101.html
Randell D.A. , Cui Z. , Cohn A.G. 1992 A spatial logic based on regions and connection Proc. of the 3rd International Conference on Knowledge Representation and Reasoning 165 - 176
Tsetsos V. , Anagnostopoulos C. , Kikiras P. , Hasiotis P. , Hadjiefthymiades S. 2005 A human-centered semantic navigation system for indoor environments Pervasive Services, ICPS'05, In Proceedings of International Conference on IEEE 146 - 155
Uschold M. , Gruninger M. 1996 Ontologies: Principles, methods and applications Knowledge engineering review 11 (2) 93 - 136
Wang X. H. , Zhang D. Q. , Gu T. , Pung H. K. 2004 Ontology based context modeling and reasoning using OWL Pervasive Computing and Communications Workshops, In Proceedings of the Second IEEE Annual Conference on IEEE 18 - 22