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

Mobile object continuous k-nearest neighbor (CKNN) query method based on road based road networks tree (RRN-Tree) in road network

A technology for moving objects and road networks, applied in the field of data query, can solve problems such as low query efficiency, inability to solve complex road network nearest neighbor query problems, and inability to reflect the steering relationship of moving objects, so as to achieve the effect of performance improvement

Inactive Publication Date: 2014-01-29
NORTHEAST FORESTRY UNIVERSITY
View PDF5 Cites 34 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

[0005] The purpose of the present invention is to solve the problem of using an index structure to index road network segments, modeling the road network as a directed / undirected graph, and processing the nearest neighbor query request based on the memory data structure, but when the road network data volume is large , When there are many road sections, the query efficiency drops sharply; moreover, the graph-based modeling method cannot reflect the turning relationship of moving objects at intersections, and cannot solve the nearest neighbor query problem in complex road networks with intersection turning and U-turn constraints , providing a CKNN query method for moving objects in road networks based on RRN-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
  • Mobile object continuous k-nearest neighbor (CKNN) query method based on road based road networks tree (RRN-Tree) in road network
  • Mobile object continuous k-nearest neighbor (CKNN) query method based on road based road networks tree (RRN-Tree) in road network
  • Mobile object continuous k-nearest neighbor (CKNN) query method based on road based road networks tree (RRN-Tree) in road network

Examples

Experimental program
Comparison scheme
Effect test

specific Embodiment approach 1

[0044] Specific implementation mode one: the following combination Figure 1 to Figure 12 Describe this embodiment, the RRN-Tree-based mobile object CKNN query method in the road network described in this embodiment, the implementation steps of this query method are:

[0045] Step 1: First, define road network G, route r, road segment seg, intersection j, moving object o and KNN monitoring area respectively;

[0046] The road network G is a two-tuple G=(R, J), wherein R is a set of routes in the road network, each route includes several road sections, and J is a set of intersections of multiple routes in the road network;

[0047] The route r refers to a complete path that can be named independently in the road network, and is defined as:

[0048] r = ( rid , len , ( jid j , ...

specific Embodiment approach 2

[0068] Specific implementation mode two: the following combination Figure 1 to Figure 12 Describe this embodiment, this embodiment is a further description of Embodiment 1, the specific implementation process of the KNN query initial set calculation described in step 3 described in this embodiment is:

[0069] First, establish a priority queue PQueue to save the adjacent points in the query process. The elements in the priority queue PQueue are sorted according to the distance from the query point from small to large, and the initial value of the priority queue PQueue is empty;

[0070] Establish a queue ResultList for storing query results, the length of the queue ResultList is K, the elements in the queue are arranged in ascending order according to the distance from the query point, and the initial value of the queue ResultList is empty;

[0071] When sending a query request, let q represent the query point, o i Indicates the point of interest to be queried, where i is a ...

specific Embodiment approach 3

[0078] Specific implementation mode three: the following combination Figure 1 to Figure 12 Describe this embodiment. This embodiment is a further description of Embodiment 1. The CKNN query update in Step 3 described in this embodiment is divided into two cases. When the position of the query point object remains unchanged, but the POI object moves When , the KNN monitoring area generated by the query process can reduce the query update cost. The realization process is as follows:

[0079] When the query point object does not move, since the position of the query object remains unchanged, the KNN monitoring area generated by the last query also remains unchanged. Three cases are handled separately:

[0080] 1. When the interest point object k′=k in the KNN monitoring area, it is only necessary to find all the moving objects on the road sections in the KNN monitoring area through RRN-Tree, and use the object set on the road sections in the KNN monitoring area as result;

[...

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 provides a mobile object continuous k-nearest neighbor (CKNN) query method based on a road based road networks tree (RRN-Tree) in a road network and relates to a data query method. The mobile object CKNN query method aims to solve the problem that in the prior art, an index structure is utilized to index the road network, the road network is modeled to a directed / undirected graph, and a nearest neighbor query request is processed based on a memory data structure; however, when the road network has a large data size and multiple rod segments, the query efficiency is decreased rapidly; furthermore, the modeling mode based on the graph cannot reflect the steering relation of a mobile object at the crossing, and the nearest neighbor query of the complex road network with crossing steering and U-shaped turning constraints cannot achieved. According to the mobile object CKNN query method, an RRN-Tree index structure is provided to index the road network and interesting point objects, an adjacency linked list is established for crossed points on paths in the index structure, the connection relations between road segments at the crossing are stored, and therefore, the CKNN query of the road network under complex constrain conditions is completed. The mobile object CKNN query method is used for inquiring CKNN query of the road network.

Description

technical field [0001] The invention relates to a data query method. Background technique [0002] With the development of wireless communication technology and the popularity of portable devices such as mobile phones and PDAs with GPS positioning functions, location-based services (LBS, Location Based Service) have developed rapidly and have been widely used in geographic information systems, emergency services, and car navigation. and travel route planning. Spatial query is closely related to location-based services. Among them, continuous K-nearest neighbor query (CKNN, Continouns K Nearest Neighbors) of mobile objects based on road network is an important type of query request, which can continuously search for a given distance from a query object in a road network environment. The nearest K nearest neighbor targets, for example, in fire command, find the 4 fire trucks closest to the command center. The key to solving such problems lies in: 1) fast real-time calculatio...

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
IPC IPC(8): G06F17/30
CPCG06F16/29G06F16/9537
Inventor 孙海龙王春艳于鸣刘丹
Owner NORTHEAST FORESTRY UNIVERSITY
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