This article uses golang Realization redis The ninth part of the series , It mainly introduces how to use GeoHash Search nearby people .

Search for nearby POI It's a very common feature , The technical difficulty is that the geographical location is two-dimensional ( Longitude and latitude ) And our common index ( Whether it's B Trees 、 Red black tree or jump watch ) It's all one-dimensional .GeoHash The essence of the algorithm is to transform two-dimensional longitude and latitude into one-dimensional representation .

The core implementation code of this paper can be found in Godis:lib/geohash Find . You can also download Godis Come and experience for yourself .

Point of interest (Point Of Intererst, POI): In electronic maps, the places we care about are called POI, Like restaurants 、 The supermarket 、 Office buildings .POI Usually contains the name 、 Longitude and latitude 、 Description, etc . While searching for people nearby , You can also call nearby users POI.

GeoHash principle

We know that the range of longitude is [-180,180], The latitude range is [-90,90]. We bisect latitude and longitude , So you can divide the earth's surface into 4 Parts of :

latitude [-90, 0] use 0 Express ,[0, 90] use 1 Express ; longitude [-180, 0] use 0 Express ,[0, 180] use 1 Express . Longitude in the front, latitude in the back , So all four parts have a binary code .

We continue to bisect four small rectangles :

The rectangle divided twice needs to use 4bit To express . The first two bits are the codes of the large rectangle after the first bisection , The last two digits indicate the position of the small rectangle in the large rectangle .

Divide the rectangles further , The more the number of divisions, the smaller the rectangle and the higher the longitude , Finally, we can get the smallest rectangle to represent a point . The code of this small rectangle can replace the coordinates of this point , The side length of a rectangle is GeoHash The error of the .

This segmentation allows us to use Z I'll paint the whole map with curves , This Z The type curve is called Peano Space filling curve . In most cases, the coding of adjacent points in space is also very similar . In a few cases, the coding mutates , The spatial distance of the points that lead to similar coding is very large ( Like the one above 0111 And 1000).

As shown in the figure, except Peano Besides the space filling curve, there are many space filling curves , Among them, it is generally accepted that the effect is better Hilbert Space filling curve . Compare with Peano In terms of curve ,Hilbert There is no big mutation in the curve . But because of Peano Curve implementation is simpler , therefore Geohash The algorithm uses Peano Space filling curve .

Realization GeoHash codec

Read the introduction above , We can quickly write GeoHash The coding process :

// Returns the binary code and the latitude and longitude range of the corresponding rectangle 
func encode0(latitude, longitude float64, bitSize uint) ([]byte, [2][2]float64) {
box := [2][2]float64{ // Geohash The rectangular
{-180, 180}, // longitude
{-90, 90}, // latitude
}
pos := [2]float64{longitude, latitude}
bits := make([]bit, 0)
var precision uint = 0
for precision < bitSize { // Cycle until the accuracy is enough
for direction, val := range pos { // Take turns with latitude and longitude ,p.s. See this cycle ? You can easily put GeoHash Generalized to N Dimensional space
mid := (box[direction][0] + box[direction][1]) / 2 // Calculate the split point
if val < mid {
// the ( weft ) The degree is less than the midpoint , Code filling 0, Let the upper bound of the first bisection be the midpoint of the current interval
box[direction][1] = mid
bits = append(bits, 0)
} else {
// the ( weft ) The degree is greater than the midpoint , Code filling 1, Let the lower bound of the first bisection be the midpoint of the current interval
box[direction][0] = mid
bits = append(bits, 1)
}
bit++
precision++
if precision == bitSize {
break
}
}
}
return []byte(bits), box
}

The code is very simple , Similar to binary search . Unfortunately, like most languages golang The minimum unit for manipulating binary data is byte Instead of bit, So we need to do some extra work to achieve bit code :

// This is the real realization , Please pay attention to the difference from the previous section 
var bits = []uint8{128, 64, 32, 16, 8, 4, 2, 1} func encode0(latitude, longitude float64, bitSize uint) ([]byte, [2][2]float64) {
box := [2][2]float64{
{-180, 180}, // lng
{-90, 90}, // lat
}
pos := [2]float64{longitude, latitude}
hash := &bytes.Buffer{}
bit := 0
var precision uint = 0
code := uint8(0)
for precision < bitSize {
for direction, val := range pos {
mid := (box[direction][0] + box[direction][1]) / 2
if val < mid {
box[direction][1] = mid
// The code defaults to 0, No need to operate
} else {
box[direction][0] = mid
code |= bits[bit]
// Write... By bit or operation 1, For example, in the second byte 3 Bit write 1 should code |= 32
}
bit++
if bit == 8 { // After calculating the encoding of a byte , Write it to buffer
hash.WriteByte(code)
bit = 0
code = 0
}
precision++
if precision == bitSize {
break
}
}
}
// precision May not be able to be 8 to be divisible by , Now the rest of the binary code is written to the end
if code > 0 {
hash.WriteByte(code)
}
return hash.Bytes(), box
}

For convenient transmission GeoHash Defines a text format encoding , It's a binary code Base32 After transformation, we get :

// GeoHash Mapping tables and standards for Base32 The mapping table is a little different 
var enc = base32.NewEncoding("0123456789bcdefghjkmnpqrstuvwxyz").WithPadding(base32.NoPadding)
func ToString(buf []byte) string {
return enc.EncodeToString(buf)
}

After writing the code, you can go to www.geohash.cn Test the result on the computer .

Following the instruction of binary encoding, the decoding process can be completed :

func decode0(hash []byte) [][]float64 {
box := [][]float64{
{-180, 180},
{-90, 90},
}
direction := 0
for i := 0; i < len(hash); i++ {
code := hash[i]
for j := 0; j < len(bits); j++ {
mid := (box[direction][0] + box[direction][1]) / 2
mask := bits[j] // Use the mask to take out the finger to locate
if mask&code > 0 {
// the ( weft ) The degree is greater than mid
box[direction][0] = mid
} else {
// the ( weft ) Degree less than mid
box[direction][1] = mid
}
direction = (direction + 1) % 2
}
}
return box
}

The decoding process can not get accurate results, only the latitude and longitude range of the corresponding rectangle , We usually use the center of the rectangle as the coordinate of the code .

Search the neighborhood

Because the points in the same rectangle have GeoHash The code has the same prefix , So it's very easy to find all of them in a rectangle POI.

In theory, we're using GeoHash To search the neighborhood POI You just need to find a suitable rectangle and find all of them POI that will do , In fact, we have two problems :

  1. As mentioned above GeoHash Value mutation will lead to coding close, two points space distance is very large .
  2. If we're on the edge of the rectangle , So in the next rectangle POI It could be closer .

If we're at the red dot , Although the green dot on the north is not in the same rectangle as us, it is obviously closer .

To solve these problems , In addition to searching for the rectangle where the anchor is located , And search around 8 In one area POI.

There are two steps to do this :

  1. Calculate all POI Of GeoHash value , And use a jump meter or B+ Tree and other data structures that are convenient for range query
  2. Calculation “ Nearby area ” Corresponding GeoHash code , Find out all the... In these areas POI

Building spatial indexes

We will GeoHash The precision of is set to 64 position , So we can put GeoHash Code to uint64 Type deposit SortedSet In the data structure :

func ToInt(buf []byte) uint64 {
if len(buf) < 8 { // use 0 Under filled digits
buf2 := make([]byte, 8)
copy(buf2, buf)
return binary.BigEndian.Uint64(buf2)
}
return binary.BigEndian.Uint64(buf)
}

Because binary codes in the same rectangle have the same prefix, we need to use the low end of the binary code as uint64 The high ( That is to use the large terminal sequence ), So, in the same rectangle uint64 All codes will be in the same number range . such as 0110 Of all the points in the rectangle uint64 The code will be in [0x6000000000000000, 0x7000000000000000) Within the interval , combination SortedSet We can very quickly ( Time complexity O(logN)) Find all the places in 0110 In the area POI.

Use SortedSet The code for indexing can be found in Godis:db/geo.go Find .

Find the neighborhood

We know that the radius of the earth is about 6371km So after the first split, we get four things wide 6371π km North and South High 3186π km The rectangular , This recursion is used to segment 10 After that we can get the leniency 40km Gao Yue 20km The rectangular . in other words 20bit Of GeoHash The error in the east-west direction of the code is 40km, The error in the north-south direction is 20 km.

We are wikipedia It's on the Internet geohash The error range of :

In the table geohash length yes base32 The length of the encoded string ,1 A character can represent 5 position (bit).

We can also use the code to estimate what is required for a given distance geohash length:

func estimatePrecisionByRadius(radiusMeters float64, latitude float64) uint {
if radiusMeters == 0 {
return defaultBitSize - 1
}
var precision uint = 1
for radiusMeters < MercatorMax {
radiusMeters *= 2
precision++
} precision -= 2
if latitude > 66 || latitude < -66 {
precision--
if latitude > 80 || latitude < -80 {
precision--
}
}
if precision < 1 {
precision = 1
}
if precision > 32 {
precision = 32
}
return precision*2 - 1
}

There are two things to note in this code :

  1. Because the earth is spherical, the Mercator projection method is used in mapping (Mercator Projection) The projection area is relatively large near the north and south poles ( On the world map, Greenland, near the north pole, looks very big ), So we need to reduce the precision in high latitudes
  2. The range of longitude is [-180,180] Latitude is in the range of [-90,90], So after dividing longitude and latitude equally for the same number of times, the rectangle we get is always long from east to west and short from north to south . To solve this problem, the precision we return is always odd (precision*2 - 1), In this way, the longitude is divided more than the latitude once, and a rectangle with the same length and width can be obtained .

Next, we calculate the area corresponding to the rectangle uint64 The upper and lower bounds of coding :

func ToRange(scope []byte, precision uint) [2]uint64 {
lower := ToInt(scope)
radius := uint64(1 << (64 - precision))
upper := lower + radius
return [2]uint64{lower, upper}
}

For example, in 0110 The points in the rectangle, their uint64 The code will be in [0110..., 0111...) Within the scope of , Find the right place in the binary code +1 That's all right. .

The next step is to calculate the nine palace grid GeoHash code , We use the method of calculating the longitude and latitude of each rectangle center point and then re coding :

func GetNeighbours(latitude, longitude, radiusMeters float64) [][2]uint64 {
precision := estimatePrecisionByRadius(radiusMeters, latitude) center, box := encode0(latitude, longitude, precision)
height := box[0][1] - box[0][0]
width := box[1][1] - box[1][0]
centerLng := (box[0][1] + box[0][0]) / 2
centerLat := (box[1][1] + box[1][0]) / 2
maxLat := ensureValidLat(centerLat + height)
minLat := ensureValidLat(centerLat - height)
maxLng := ensureValidLng(centerLng + width)
minLng := ensureValidLng(centerLng - width) var result [10][2]uint64
leftUpper, _ := encode0(maxLat, minLng, precision)
result[1] = ToRange(leftUpper, precision)
upper, _ := encode0(maxLat, centerLng, precision)
result[2] = ToRange(upper, precision)
rightUpper, _ := encode0(maxLat, maxLng, precision)
result[3] = ToRange(rightUpper, precision)
left, _ := encode0(centerLat, minLng, precision)
result[4] = ToRange(left, precision)
result[5] = ToRange(center, precision)
right, _ := encode0(centerLat, maxLng, precision)
result[6] = ToRange(right, precision)
leftDown, _ := encode0(minLat, minLng, precision)
result[7] = ToRange(leftDown, precision)
down, _ := encode0(minLat, centerLng, precision)
result[8] = ToRange(down, precision)
rightDown, _ := encode0(minLat, maxLng, precision)
result[9] = ToRange(rightDown, precision) return result[1:]
}

You can also quickly infer the neighborhood by encoding a rectangle 8 A rectangular code , This method is difficult to implement, and can be referred to Redis In the implementation of :

Last in SortedSet Find POI:

func geoRadius0(sortedSet *sortedset.SortedSet, lat float64, lng float64, radius float64) redis.Reply {
areas := geohash.GetNeighbours(lat, lng, radius)
members := make([][]byte, 0)
for _, area := range areas {
lower := &sortedset.ScoreBorder{Value: float64(area[0])}
upper := &sortedset.ScoreBorder{Value: float64(area[1])}
elements := sortedSet.RangeByScore(lower, upper, 0, -1, true)
for _, elem := range elements {
members = append(members, []byte(elem.Member))
}
}
return reply.MakeMultiBulkReply(members)
}

Source portal

OK, Be accomplished .

Golang Realization Redis(9): Use GeoHash Search for more articles about people nearby

  1. Golang Realization Redis(5): Using jump table to realize SortedSet

    This article uses golang Realization redis Part five of the series , We'll show you how to use jump tables to implement ordered sets (SortedSet) Related functions . Jump watch (skiplist) yes Redis in SortedSet data structure ...

  2. Golang Realization Redis(5): Use the jump table to achieve SortedSet

    This article uses golang Realization redis Part five of the series , We'll show you how to use jump tables to implement ordered sets (SortedSet) Related functions . Jump watch (skiplist) yes Redis in SortedSet data structure ...

  3. go The journey of language --golang operation redis、mysql Complete works of

    One .redis brief introduction redis(REmote DIctionary Server) It's a by Salvatore Sanfilippo Write key-value The storage system , It consists of C Language writing . comply with BSD agreement . Support network ...

  4. golang operation Redis &amp; Mysql &amp; RabbitMQ

    golang operation Redis & Mysql & RabbitMQ Reids Install import go get github.com/garyburd/redigo/redis import ...

  5. Golang Realization Redis(4): AOF Persistence and AOF rewrite

    This article uses golang Realization redis The fourth article in the series , How to use golang Realization Append Only File Persistence and AOF File rewriting . This article complete source code in the author GithubHDT ...

  6. Redis How to achieve “ The man near the ” What about this function ?

    Author's brief introduction Wanmi , Hungry, Senior Development Engineer .iOS,Go,Java All dabble in . At present, it mainly focuses on big data development . Like riding . Climbing the mountain . Preface : in the light of “ The man near the ” This is the application scenario of location-based services , Common can be used PG.MySQL and MongoD ...

  7. 【 Gupao College 07】 be based on ElasticSearch Search the neighborhood

    1. Why choose ElasticSearch 1)ElasticSearch advantage : Distributed . In real time .Push replication Fully support Apache Lucene Near real time search for Dealing with multi tenancy ( ...

  8. Redis GEO ,GEOHASH,Spatial_index

    https://matt.sh/redis-geo http://antirez.com/latest/0 http://invece.org/ https://github.com/davidmot ...

  9. Go Language learning notes ( 8、 ... and )golang operation Redis &amp; Mysql &amp; RabbitMQ

    Add Golang Study QQ Learn together, make progress, start a family and work together ^-^ Group number :96933959 Reids Install import go get github.com/garyburd/redigo/redis import ...

  10. [Go] golang Connect redis test

    go-redis Use 1. Download the code to GOPATH The directory specified by the environment variable. For example, mine is the entry directory D:\golang\code\src\github.com\go-redis , perform git clone https ...

Random recommendation

  1. Div+CSS Naming specification

    matters needing attention :1. The naming follows the hump style  2. Try to use Chinese as much as possible  3. Without middle bars and underscores   4. Try not to abbreviate , Unless you can understand the words at a glance head :header   sign :logo   link :friendlink     Content :c ...

  2. HTML、JS、CSS Special characters of

    Maybe it's cold knowledge , It's not known to most people like HTML.JS.CSS The writing of their special characters , I also included it on the Internet, here make once : Arrow class Symbol UNICODE Symbol UNICODE HTML JS CSS HT ...

  3. Blog has moved . Please visit my new chassis www.boyipark.com

    Blog has moved . Please visit my new chassis www.boyipark.com

  4. mysql Master slave synchronization (3)-percona-toolkit Tools ( Data consistency monitoring 、 Delay monitoring ) Use combing

    from :http://www.cnblogs.com/kevingrace/p/6261091.html stay mysql The most common contact at work is mysql replication mysql In terms of replication, there will still be ...

  5. MySQLdb、 flask-MySQLdb 、MySQL-python Installation failed

    I'm learning today flask When , Learn about the database section , Connect mysql To generate table , The running program reported an error :No module named MySQLdb here Need to install Either of the following two pip install flas ...

  6. nmon The results of the performance monitoring page show ——EasyNmon

    First , Look at the final presentation of the result display style : Report interface : 1. Installation package download address :https://github.com/mzky/easyNmon 2. After downloading 2 Compressed files : among ,nmon16g_x86 There are differences in ...

  7. Take it off manually UPX Compressed shell

    The sample program demonstrates Sample program selection win7 Self contained notepad.exe, The program was originally not shelled : Copy notepad.exe A copy of the file , Rename it to notepad - upx.exe, We are right. notepad - ...

  8. EditText Input decimal

    edtValue.setInputType(InputType.TYPE_CLASS_NUMBER | InputType.TYPE_NUMBER_FLAG_DECIMAL);

  9. iOS Development of the ring countdown bar ( Dotted line / Solid line )

    The code is simple , At a glance . This is clockwise , If you want to go counter clockwise ,clockwise Change it to 0, You also need to change the start angle and end angle . Source code address :https://github.com/LfyDragon/CountDown Go straight up ...

  10. ftp The whole set of orders

    FTP The command line format of is : ftp -v -d -i -n -g [ Host name ] , among -v Display all the response information of the remote server : -n Limit ftp Automatic login , I don't use :.n etrc file : -d Use debug mode ...