Eureka AIR delivers breakthrough ideas for toughest innovation challenges, trusted by R&D personnel around the world.

A kd tree construction method with position priority and minimum circumscribed rectangle

A technology of circumscribed rectangle and construction method, applied in other database retrieval, other database indexing, special data processing applications, etc., can solve the problem of affecting the selection of distance attribute optimization strategy, and unable to effectively use the user's perception of distance.

Active Publication Date: 2021-10-15
EAST CHINA NORMAL UNIV
View PDF4 Cites 0 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

However, the existing related technologies for spatial data object management and indexing do not treat all dimensions (including spatial dimensions and non-spatial dimensions) contained in spatial data objects differently, which may lead to inability to effectively use them when responding to location service queries. The user's preference for the special attribute of distance, which affects the selection of optimization strategies for the distance attribute in the location-based service query processing

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 kd tree construction method with position priority and minimum circumscribed rectangle
  • A kd tree construction method with position priority and minimum circumscribed rectangle
  • A kd tree construction method with position priority and minimum circumscribed rectangle

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0028] The present invention will be described in further detail in conjunction with the following specific examples and accompanying drawings, and the protection content of the present invention is not limited to the following examples. Without departing from the spirit and scope of the inventive concept, changes and advantages conceivable by those skilled in the art are all included in the present invention, and the appended claims are the protection scope.

[0029] The invention overcomes the shortcomings of the traditional KD tree in the location-based service query, adopts the priority selection of the location dimension and the automatic generation of the smallest circumscribed rectangle to transform the construction process of the traditional KD tree.

[0030] The location dimension of the present invention is preferred, such as figure 1 As shown, according to the threshold parameter θ, the respective variances are calculated on the spatial dimensions, that is, longitud...

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 discloses a KD tree construction method with position priority and maintenance of the minimum circumscribed rectangle. The characteristics of the method are: (1) When selecting the division dimension, the spatial dimension, namely longitude and latitude, is given priority. When the objects contained in the divided data set After the number is less than a specified parameter θ, all dimensions are used for subsequent divisions; (2) A minimum circumscribed rectangle, MBR, is maintained on non-leaf nodes to define the data nodes contained in the subtree with the current node as the root node Upper and lower bounds in each dimension. Since the construction process of the location-first LPKD tree of the present invention prioritizes the division of space dimensions, and the non-leaf nodes maintain a minimum circumscribed rectangle MBR, this makes it possible to use the LPKD tree of the present invention to perform location-based personalized service matching (For example, when recommending favorite restaurants or hotels for users), the least relevant POIs can be quickly and effectively pruned, thus providing a strong guarantee for the real-time performance of location-based personalized services.

Description

technical field [0001] The invention belongs to the technical field of spatial data management and multidimensional data query, and relates to a spatial multidimensional data index structure, in particular to a KD tree construction method with position priority and minimum circumscribed rectangle maintenance. Background technique [0002] With the popularization of smart mobile terminals and the rapid development of various wireless communication technologies, location-based services have been widely concerned and applied in more and more fields. Location-based query services are often encountered in daily life, for example, to find the cheapest gas station for users within 5 kilometers, and to find 100 restaurants within 2 kilometers who are most likely to be interested in a new dish developed by the restaurant. customers. Then, the effective organization and management of spatial data objects with location information to quickly respond to user query requests is a problem...

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/901
CPCG06F16/9027
Inventor 张召金澈清戚晓冬
Owner EAST CHINA NORMAL UNIV
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
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