MapReduce and inverted Thiessen polygon-based large-scale neighbor query method

A Thiessen polygon and nearest neighbor query technology, which is applied in cloud computing and big data fields, can solve the problems of unsatisfactory indexing time consumption, inability to adapt to MapReduce parallel processing, poor scalability, etc., and achieve the effect of improving indexing efficiency

Inactive Publication Date: 2018-03-27
DALIAN UNIV
View PDF2 Cites 3 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

However, because the existing indexing algorithms cannot adapt to the parallel processing of MapReduce, the time consumption of index construction is not ideal, and the scalability is not good.

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
  • MapReduce and inverted Thiessen polygon-based large-scale neighbor query method
  • MapReduce and inverted Thiessen polygon-based large-scale neighbor query method
  • MapReduce and inverted Thiessen polygon-based large-scale neighbor query method

Examples

Experimental program
Comparison scheme
Effect test

Embodiment 1

[0028] Embodiment 1: a kind of large-scale neighbor query method based on MapReduce and inverted Thiessen polygon, wherein: MapReduce is existing programming model, is used for the parallel operation of large-scale data set, and described method comprises the steps:

[0029] S1. Construct a MapReduce-based inverted Voronoi index (Tyson polygon index, Inverted VoronoiIndex, IVI);

[0030] S2. Use the inverted Voronoi index to partition the data sets R and S to obtain VC partitions. The two partitions are because the Voronoi diagram needs to be combined with two partitions when the Voronoi diagram needs to be established later, so it is carried out in this step. Partitioning of the two datasets;

[0031] S3. Use MapReduce-based IVKNN to perform distributed kNN (neighborhood algorithm) query. IVKNN is an inverted Voronoi index using IVI.

[0032] Wherein: the steps of constructing the inverted Voronoi index based on MapReduce are as follows:

[0033] Given two data sets R and S...

Embodiment 2

[0047] Embodiment 2: This embodiment can be implemented as an independent technical solution or as a further illustration of each solution in Embodiment 1. This embodiment provides a large-scale neighbor query method based on MapReduce and inverted Thiessen polygons. This method It is an efficient algorithm based on MapReduce that uses Voronoi diagrams to process kNN queries. It can also solve the future development trend of wireless, networked, and mobile medical call systems. This embodiment also improves on the deficiencies in the prior art, and has good efficiency and scalability. In order to achieve the above object, the execution steps of the technical solution adopted in this embodiment are as follows: Carry out the establishment of the large-scale neighbor query index of MapReduce and inverted Thiessen polygon; MapReduce is a kind of current popular programming frame based on cloud platform, it can Process and generate large data sets, which leverage shared-nothing clu...

Embodiment 3

[0055] Example 3: With the rapid development of social security services today, people's material living standards are improving day by day, and the demand for medical services has become more humane and personalized. At the same time, more and more people need more convenient and perfect medical services.

[0056]With the rapid growth of mobile communication and location-based service-related technologies, technologies such as cloud computing, big data, Internet of Things, mobile computing, and spatial positioning have gradually matured, such as GPS, cameras, and Bluetooth data. This makes the storage and processing of various spatial data or objects face great challenges. Therefore, with the development of informatization, applications such as electronic medical records, nursing call center systems, and large-scale medical databases in the medical service industry are also developing rapidly, playing a greater role in improving work efficiency, improving medical services, an...

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 MapReduce and inverted Thiessen polygon-based large-scale neighbor query method, belongs to the field of cloud computation and big data, and aims at improving index efficiency of existing data query method. The method comprises the following steps of: S1, constructing a MapReduce-based inverted Voronoi index; and S2, partitioning a data set R and a data set S by using theinverted Voronoi index, and carrying out distributed kNN query by using MapReduce-based IVKNN. The method has the effects of improving the algorithm index efficiency and enabling MapReduce to be notinfluenced by space and time.

Description

technical field [0001] The invention belongs to the fields of cloud computing and big data, and relates to a MapReduce index that can effectively improve query efficiency in a distributed environment. Background technique [0002] MapReduce is a popular cloud-based programming framework that can process and generate large data sets, and it utilizes shared-nothing clusters to support data-intensive applications. The specific processing steps are: in the distributed cache system, when a MapReduce task processes a key / value pair, a set of intermediate key / value pairs is generated in the map function, and all intermediate values ​​are merged according to the same intermediate key, Each map is independent of other operations, i.e. all maps can be executed in parallel. A group of "reducers" in MapReduce can perform reduction operations, and the output of Map operations with the same key can be reduced to the same reducer at the same time. However, running a reduction process alo...

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 Applications(China)
IPC IPC(8): G06F17/30
CPCG06F16/2237G06F16/2462G06F16/27
Inventor 季长清汪祖民秦静吴锐
Owner DALIAN 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
Try Eureka
PatSnap group products

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

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap