A spatial keyword query method and device based on keyword inversion and trie

Abstract

The present invention relates to a spatial keyword query method and device based on keyword inversion and Trie. The method of the present invention includes: a data preprocessing step, encoding all position points in the data set D into a character string with a length of n, using the The string is the sorting object. Sort each row of data in the data set D in lexicographical order and generate a number id. Each row of data is called a record r, and the data set consisting of one or more rows of records r is called a record set R; space key The word index building step is to build an inverted index for the keyword set in the record set R, and then construct a Trie for the string corresponding to the id of any keyword to obtain an index structure combining keyword inversion and Trie; spatial keyword query Step 1: Retrieve the index structure combined with keyword inversion and Trie, obtain the ids that meet the query conditions, obtain the id candidate set after filtering, and verify the candidate set to return the location points that meet the spatial query conditions. The invention can efficiently support keyword query in any spatial range.

Description

technical field [0001] The invention relates to a spatial keyword query method and device based on keyword inversion and Trie, belonging to the fields of spatial keyword query (Spatial Keyword query), location-based service (Location-Based Service, LBS) and the like. Background technique [0002] In recent years, with the popularity of mobile devices such as smartphones and tablet computers, the desktop-based Internet era has turned to the mobile Internet era. At the same time, with the rapid development of positioning technology, such as: GNSS, GPS, 3G / 4G, etc., a large number of location-based services have been generated. These services generate a large amount of text data with location attributes, namely spatial text. How to quickly obtain the required information from these data is the core problem in the field of spatial text query. According to application scenarios, spatial text query can be divided into spatial keyword query and distribution / subscription query. ...

AI Technical Summary

Problems solved by technology

The variant of R-Tree optimizes R-Tree based on the principles of minimum area, minimum overlapping area, minimum perimeter and high storage utilization, but the retrieval efficiency is still restricted by the multi-path query problem of R-Tree.

Images