Font Size: a A A

Research On Keyword Querying Techniques In Spatial Networks

Posted on:2018-08-26Degree:DoctorType:Dissertation
Country:ChinaCandidate:S ZhaoFull Text:PDF
GTID:1318330518493534Subject:Computer Science and Technology
Abstract/Summary:PDF Full Text Request
Location-based service (LBS) is a kind of service that obtains location information of mobile terminal users through the wireless network of the network operators or external positioning system, and provides users with the appropriate services with the support of geographic information system platform. With the rapid development of mobile Internet and the great popularity of positioning-enabled smart devices, LBS has played an important role in people's daily life, and brought great convenience to people's lives. For example, people often use social networking applications to find people nearby and mapping software for route navigation. As an important service in LBS, keyword querying in spatial networks has received extensive attention from academia and industry in recent years. Keyword querying in spatial network is searching for Point of Interest (POI) in spatial networks, which matches the keyword input by users. In order to provide high quality keyword querying service, it is necessary to study the efficient keyword querying method in spatial networks, which can ensure accurate query result and efficient query processing on the premise of meeting users'querying need. With the development of society and the improvement of people's living standards, the users' query requirements are becoming more and more diversified such as the most popular area queries that cover multiple keywords, or queries based on multiple users. However,there is room for improvement in many aspects, such as meeting the users'diverse needs, improving the efficiency of query processing and ensuring the accuracy of the query results and so on. Therefore, in this dissertation,the keyword querying in spatial networks has been studied extensively, in view of complicated querying needs of users in three main aspects, i.e.,popularity-aware collective keyword querying for POI, the querying for group-based collective keyword region, and the querying for group-based keyword route. The main innovative outcomes are as follows:(1) The method of popularity-aware collective keyword querying for POIs in spatial networks is proposed. Firstly, this kind of query is defined as the search for one or more popularity-aware POIs that can both cover the user's required keywords and meet the constraints input by the users, i.e., the query range constraints and the POI range constraints.Secondly, the spatial network data with POIs is modeled as a spatial network graph where each node located in a two-dimensional space represents a POI or an intersection such as a road intersection, each POI is attached with one or more keywords, the rating score associated with each keyword shows popularity, each edge represents a road segment and each edge's weight represents the path length. Thirdly, an exact solution and a heuristic solution on small and large road networks are proposed respectively. To further improve query efficiency, two optimized techniques are proposed. One is the rating score scaling technique which is applied to reduce the search space. The other is the redundant computation reducing technique which is used to avoid unnecessary computation in query processing. Fourthly, the experiments based on two real datasets are carried out. The experimental results show that the query algorithm for large-scale spatial network data can not only return query results with high accuracy, but also its querying efficiency still has good scalability although the data size increases.(2) The method of querying for group-based collective keyword region in spatial networks is proposed. Firstly, this kind of query is defined as the search for a region containing a set of POIs that covers all the query keywords and these POIs are close to the group of users and are close to each other. Secondly, the spatial network data with POIs is modeled as a weighted undirected graph, where each node located in a two-dimensional space represents a POI or an intersection such as road intersection, each edge represents a road segment and each edge's weight represents the path distance cost. Based on the graph model, an efficient index is constructed by using shortest path tree algorithm and distance oracle technique. Thirdly, based on group-based divide-and-conquer technique, an efficient algorithm, which gives a 5-factor approximation to find a feasible region, is proposed. The cost of this region is used to limit the search space efficiently to further propose an exact algorithm, and an approximation algorithm with a 7/15-factor approximation based on dynamic pruning technique. Fourthly, the experiments based on two real datasets are carried out and the experimental results show that the proposed approximation algorithm not only ensures accurate query results,but also greatly improves the query efficiency.(3) The method of querying for group-based collective keyword route in spatial networks is proposed. Firstly, this kind of query is defined as the search for a POI route that covers a set of required keywords sequentially, and the cost of which is minimized. Secondly, two efficient algorithms, which give an (n+3)-factor approximation and an (n+1)-factor approximation respectively, are proposed to find a feasible POI route,where n represents the number of query keywords. The cost of this POI route is further used to limit the search space in other following algorithms efficiently. Thirdly, based on the limited search space,two exact algorithms, and one greedy algorithm are proposed. The first exact algorithm finds the optimal POI route by enumerating all feasible POI routes. To improve the search efficiency, based on dynamic pruning technique, an exact optimization algorithm making use of the split property of the cost function is proposed. Fourthly, the experiments based on two real datasets are carried out. The experimental results show that the algorithms can ensure accurate query result and meet users' real-time querying need.
Keywords/Search Tags:spatial network, keyword query, POI query, region query, route query
PDF Full Text Request
Related items