Researches On Retrieval And Storage Technique Based On Concept Lattice In Context Management System

Context-aware computing is to provide suitable operations automatically according to context information, and to make systems more intelligent and personal. Context is any information which can be sensed and used to characterize the situation of any entity, even real or virtual. Context management system (CMS) is a core element that is responsible for data process and management in a context-aware system. It contains the functions such as context modeling, context data and knowledge management, providing query interface etc. It objective is to manage context and make data process better in its context-aware system. With the development of the Internet of Things, Semantic Computing, etc, context management system faces new challenge on the key function and performance. Location-based aware application is a kind of context-aware application with the high requirement of context data storage, which needs to store data for query later. The optimized design of context management system is useful to location-based aware application in practice. The thesis takes location-based aware application as the case.Formal Concept Analysis (abbr. FCA) is the core theory of the thesis. Concept lattice is the basic model of FCA, and it is applied to context data management in this thesis. It can build the hierarchy models for context and be provided to make query faster as lattice indices of the corresponding context storage model.To apply the concept lattice model in the context management system effectively, this thesis focuses on three issues as following:1. Instance retrieval by context scopes. Currently, many context-aware applications use the knowledge query way in the design and implementation process. In the most applications, low level context is converted as high level context after it is preprocessed, these high level context is instance of knowledge with semantic, to query and reason later. Now, including the context-aware technique, many domains have their schemes of instance query.In context applications, context scope query is the one of the query ways. This kind query needs context scope retrieval process. Valid index structures are useful to the context scope retrieval process. Concept lattice in Formal Concept Analysis is a valid kind index structure for information retrieval, and related researches show lattice retrieval has the advantage of object retrieval and navigation by attribute items. Therefore, this thesis focuses on context scope instance retrieval used by concept lattices.2. Concept lattice index storage. The storage of concept lattice index is to persist concept lattice for query later mainly. Concept lattice index proposed by this thesis is to keep the advantage of concept lattice query firstly and to reduce the space of lattice storage further. To knowledge instance query, the design of concept lattice index storage should support the reading/writing and management at the knowledge level.3. Consistent information update of context knowledge in concept lattice indices. In context applications, as the objects are recognized, added and their context are updated, concept lattice should be updated. When concept lattices are updated, the check and update of consistent information of knowledge instances in their concept lattice nodes can avoid checking all objects of the nodes at the later queries. These information can improve the time performance of context scope instance query. Decreasing the time of the process can make the later query of consistent information faster. Therefore, it needs the related algorithms to improve the time performance of check and update of consistent information.As the issues are mentioned above, the thesis proposes the following solutions:1. A concept-lattice-based instance retrieval within context scopes algorithm. The structure of concept lattice for context knowledge retrieval and consistency check is defined. According to the meta ontology of context constraint defined by the thesis, the context constraint relations within the context scope could be analyzed and extracted for determining the consistency information of knowledge within the scope. Through instance aggregation, concept lattice index can be generated. To retrieve instances within context scopes by concept lattices, an instance retrieval algorithm is proposed. The test shows the time performance of intance retrieval by using this algorithm is improved.2. Context knowledge storage schema based on concept lattice. The thesis proposes the context knowledge storage schema based on concept lattice index and analyze its advantage. To keep the advantage of concept lattice retrieval, the lattice index schema is designed according to the original structure of concept lattice. Because concept lattice have object intersections between extents according to its definition, the index schema avoids storing same objects between extents by key pairs. The schema test shows the time performance of extent query is improved by start key-end key.3. The consistency information update algorithms of instances in concept lattices. To decrease the time of the process of check and update consistent information in concept lattices, the thesis proposes the two algorithms as following:1) An optimized algorithm in the process of consistency check and update in concept lattices. Its main functions include:updating lattice schema; finding the concept lattice nodes that one assertion belongs to and updating consistency information; splitting the nodes and creating consistent nodes when the inconsistent situation happens and the generating of the target assertion’s consistent nodes is needed. The algorithm is to improve the execution time performance of updating lattice and checking consistency, such that the concept lattice can provide the new consistency information faster. Firstly, a naive concept lattice consistency update algorithm is proposed, and then an optimized algorithm is proposed further. This thesis defines and uses some optimized factors to decrease the execution time of the algorithm. For a given assertion, the optimized algorithm generates the special nodes of this assertion. When the assertion is to be added and updated in the partial lattices, checking the intents of these nodes avoids the search of the partial lattices that is not to add or update this assertion. When checking and updating the consistency about this assertion, it decreases the search of same objects in extents through the bottom-up search way.As Hadoop/HBase is our main parallel platform. The optimized algorithm is implemented as a Map/Reduce parallel way. Through the test and analysis, compared with the naive algorithm, with objects increasing, the execution time performance is improved obviously.2) A concept lattice optimized splitting attribute algorithm. The method of splitting nodes is by splitting interval-attributes of nodes. However, interval-attribute splitting is still time-consuming. A new parallel split algorithm is proposed. Based on the concept lattice consistency update algorithm, this algorithm is to make the split of interval-attributes faster, when inconsistent cases happen and split is needed. The algorithm computes the split priorities of candidates. It splits by choosing the split candidate with lower split scope which reduces the time cost. In the meanwhile, it reduces the time cost of generating and merging sub lattices by a non-clone parallel way, which avoids the case that memory overflows for the sub lattices generated by the clone way occupy too many memory spaces. The feasibility of split priority is analyzed, and the parallel split theory is defined and proved. By the test about the parallel split, as the part of the concept lattice consistency update algorithm, the optimized algorithm is compared with the naive one. On the current test set, the time performance is improved obviously.Thus, as the researches are mentioned above, the thesis is to make context data organization and management effective, and to improve the query/storage at the semantic level. As Formal Concept Analysis (abbr. FCA) is the core theory, it optimizes CMS partly on the issues above, combined with ontology, NoSQL, etc. Based on these techniques, for more related issues, CMS should be concerned and developed further.