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

Method for querying road network k aggregation nearest neighboring node based on Voronoi graph

A nearest neighbor, query method technology, applied in the field of spatial database, can solve problems such as poor performance

Inactive Publication Date: 2011-11-23
FUDAN UNIV
View PDF4 Cites 28 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

This method performs worse than TA
[0010] The above three methods all have relatively large defects, so it is urgent to propose a method with fast query time response to meet the requirements of users

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
  • Method for querying road network k aggregation nearest neighboring node based on Voronoi graph
  • Method for querying road network k aggregation nearest neighboring node based on Voronoi graph
  • Method for querying road network k aggregation nearest neighboring node based on Voronoi graph

Examples

Experimental program
Comparison scheme
Effect test

specific Embodiment approach

[0051] Figure 4 is a hypothetical NVD where p 1 , p 2 ,…, p 14 is the target node, q 1 , q 2 , q 3 is the query point. Note that the path between vertices in NVC and the path between vertices between NVCs are not drawn in the figure, but the road network distance from the query point to some target nodes is marked with a dotted line. In addition, the common edges between NVCs are not stored in the computer. We draw them in order to see the adjacent relationship between NVCs clearly. In fact, the adjacent relationship between NVCs is in the form of a table stored.

[0052] Now calculate the 2-ANN:

[0053] 1. First find out the 1-NN of the query point through the R tree index, and initialize the priority queue H = {( p 1 , 4), ( p 2 , 4), ( p 3 , 4)}, S 1 = { p 1}, S 2 = { p 2}, S 3 = { p 3};

[0054] 2. Then calculate q 1 The next NN( p 2 ), q 3 The next NN( p 2 ), q 2 The next NN( p 1 ), then update the priority queue H = {( ...

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 belongs to the technical field of a spatial database and in particular relates to a method for querying a road network k aggregation nearest neighboring node (k-ANN) based on a Voronoi graph. The method comprises the following steps of: resolving a first nearest neighboring node (1-NN) of each query point through an R tree index; constructing a priority queue to store the 1-NN of all query points, wherein the weight is the current aggregation distance from each query point to a target node; extending a certain query point according to a certain sequence on the basis of a road network Voronoi graph, updating the aggregation distance of the next NN of the query point, inserting or updating and performing other kinds of operation on the priority queue until the target node at the head of the queue is extended by all the query points, then the target node is a first aggregation nearest neighboring node (1-ANN); and after the 1-ANN is deleted from the queue, acquiring a second aggregation nearest neighboring node (2-ANN) which accords with the conditions for the second time, and acquiring the k-ANN according to the characteristics. The method has excellent performance in the aspect of response time and page views of user query.

Description

technical field [0001] The invention belongs to the technical field of spatial databases, and in particular relates to a solution in the road network k Aggregate nearest neighbor node query method. Background technique [0002] in the road network k nearest neighbor node ( k- NN) query and its variants have attracted more and more attention from researchers. in, k Gather the nearest neighbor nodes ( k- ANN) query can return the front row with the smallest aggregation distance for multiple query points k Therefore, it has high research value and broad application prospects. At present, the main method to solve the query problem is to search the results by gradually expanding the road network according to the A* algorithm, which will lead to a long response time and cannot meet the needs of users. It is to solve this problem that the present invention is concerned. [0003] The field of spatial databases initially focused on Euclidean space, and the research on road ne...

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
Inventor 孙未未朱良荆一楠毛鼎鼎陈楚南陈坤杰
Owner FUDAN UNIV
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