Distributed Algorithms For Keyword Queries On Road Networks

Road network graph is an edge weighted graph that describes the real road networks. A graph node represents a road junction or a spot of interest (e.g., view spot, famous college), while an edge represents a road segmentation. The edge weight is the length of the road represented by the edge, or the time it takes to travel along the road. With a road network graph, we can offer a location based service similar to Google Local and Yahoo! Maps, which are widely used. A more general road network graph allows a node to be attached with additional text, like "the main gate of Fudan University" can be a piece of the attached text of the node representing the location of the main gate of Fudan University. With such a graph, we can perform keyword queries on road networks, like "find the post offices that are within500meters from the main gate of Fudan University". Those spatial keyword queries enrich the location based services. We formally define the kind of spatial keyword query as spatial group keyword query.In this paper, we aim at designing distributed algorithms for spatial group keyword query. We design distributed index based algorithms to speed up the com-putation. We also theoretically prove the optimality of the index size. Second, we point out that the proposed distributed technique can be extended to handle a more general query class, which we name Q-class. Q-class includes interesting queries such as "find the locations both near to hospital and supermarket","find all the Chinese restaurants that are within500meters from my location". Further-more, we put forward distributed algorithms for a coordinator-based distributed system and a distributed Hadoop MapReduce cluster. In coordinator-based dis-tributed systems, we conduct comprehensive experiments to demonstrate the supe-rior performance of the proposed NPD-index techniques. In a Hadoop distributed cluster, we put forward SI-index and NPD-index based algorithms. We conduct experiments to prove the superiority of the index methods.