Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

A trie-based spatial keyword query method and device

A query method and keyword technology, applied to instruments, unstructured text data retrieval, computing, etc., can solve problems such as retrieval efficiency constraints, and achieve the effect of avoiding multi-path query problems and low storage space overhead

Active Publication Date: 2021-11-23
KUNMING UNIV OF SCI & TECH
View PDF9 Cites 0 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

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.

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • A trie-based spatial keyword query method and device
  • A trie-based spatial keyword query method and device
  • A trie-based spatial keyword query method and device

Examples

Experimental program
Comparison scheme
Effect test

Embodiment 1

[0043] Embodiment 1: as Figure 1-Figure 7 As shown, a Trie-based spatial keyword query method includes: a data preprocessing step, encoding all position points in the data set D into a string geoStr of length n, and lexicographically sorting the data according to the string geoStr suffix ssuf Each row of data in set D is sorted and generated with an ID number, each row of data is called a record r, and a data set consisting of one or more rows of records r is called a record set R; where ssuf refers to the last n-m characters of the string geoStr , m≤n, m represents the number of digits in the prefix part of the string geoStr;

[0044] The step of establishing the spatial keyword index is to construct a Trie for the string prefix spre, and the leaf node of the Trie points to the inverted index constructed according to the keywords in the field. The list elements of the inverted index are keywords and their corresponding id lists, and the space is obtained Keyword index struc...

Embodiment 2

[0106] Embodiment 2: As in embodiment 1, d≤d is given 1 Under the circumstances, the specific implementation process, this embodiment provides d>d 1 Situation, adopt the data in embodiment 1 to be described here as follows: Given query location point (19.596412-99.219501), query distance range 2000 meters, query keywords {historicalSite, garden}, as known by the geohash precision table, need p The corresponding distance error is not less than 2000 and is the minimum value, then the p value should be set to 5, and (19.596412 -99.219501) is encoded into a 5-digit string 9g3rq by the geohash algorithm. The geohash codes of the eight regions around 9g3rq are: 9g3rw, 9g3rx, 9g3rr, 9g3rp, 9g3rn, 9g3rj, 9g3rm, and 9g3rt, and 9g3rq and its surrounding eight regions are used as query domains. Because 2000>610, according to the geohash code retrieval Trie, select the inverted list to be retrieved, and then retrieve the selected inverted list, respectively obtain the id list containing ...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

PUM

No PUM Login to View More

Abstract

The invention relates to a Trie-based spatial keyword query method and device. The method of the invention includes: a data preprocessing step, encoding all position points in a data set D into a string geoStr with a length of n, and according to the string geoStr suffix ssuf Sort each row of data in the data set D in lexicographical order and generate a serial 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; steps for establishing a spatial keyword index , build a Trie for the string prefix spre, and the leaf nodes of the Trie point to the inverted index constructed according to the keywords in the domain. The list elements of the inverted index are keywords and their corresponding id lists, and the spatial keyword index structure is obtained; space The keyword query step is to retrieve the spatial keyword index structure, 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 Trie-based spatial keyword query method and device, and belongs to the field of spatial keyword query (Spatial Keyword query), location-based service (Location-Based Service, LBS) and other fields. Background technique [0002] In recent years, with the popularization of mobile devices and the rapid development of positioning technology, a large number of location-based services have been produced, such as navigation services (Automap, Baidu Map, Tencent Map, etc.) to recommend arrivals for users in real time according to the current traffic status. The optimal route to the destination; social services (such as: Foursquare, Twitter, WeChat, Momo, etc.) allow users to share their geographic location and add corresponding description information for other users’ reference; food and accommodation services (such as: Meituan Waimai, Hungry What, Qunar, Ctrip, etc.) allow users to query nearby points of interest; entertainment serv...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

Application Information

Patent Timeline
no application Login to View More
Patent Type & Authority Patents(China)
IPC IPC(8): G06F16/9537G06F16/31G06F16/335
Inventor 沈兵林贾连印游进国丁家满张晶陈明鲜张崇德唐季林
Owner KUNMING UNIV OF SCI & TECH
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic, Popular Technical Reports.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap|About US| Contact US: help@patsnap.com