Go native library for fast point tracking and K-Nearest queries

Overview

Geo Index

Geo Index library

Overview

Splits the earth surface in a grid. At each cell we can store data, such as list of points, count of points, etc. It can do KNearest and Range queries. For more detailed description check https://sudo.hailoapp.com/services/2015/02/18/geoindex/ .

Demo

http://go-geoindex.appspot.com/static/nearest.html - Click to select the nearest points.

http://go-geoindex.appspot.com/static/cluster.html - A map with 100K points around the world. Zoom in and out to cluster.

API

    type Driver struct {
        lat float64
        lon float64
        id string
        canAcceptJobs bool
    }

    // Implement Point interface
    func (d *Driver) Lat() float64 { return d.lat }
    func (d *Driver) Lon() float64 { return d.lon }
    func (d *Driver) Id() string { return d.id }

    // create points index with resolution (cell size) 0.5 km
    index := NewPointsIndex(Km(0.5))

    // Adds a point in the index, if a point with the same id exists it's removed and the new one is added
    index.Add(&Driver{"id1", lat, lng, true})
    index.Add(&Driver{"id2", lat, lng, false})

    // Removes a point from the index by id
    index.Remove("id1")

    // get the k-nearest points to a point, within some distance
    points := index.KNearest(&GeoPoint{id, lat, lng}, 5, Km(5), func(p Point) bool {
        return p.(* Driver).canAcceptJobs
    })

    // get the points within a range on the map
    points := index.Range(topLeftPoint, bottomRightPoint)

Index types

There are several index types

    NewPointsIndex(Km(0.5)) // Creates index that maintains points
    NewExpiringPointsIndex(Km(0.5), Minutes(5)) // Creates index that expires the points after some interval
    NewCountIndex(Km(0.5)) // Creates index that maintains counts of the points in each cell
    NewExpiringCountIndex(Km(0.5), Minutes(15)) // Creates index that maintains expiring count
    NewClusteringIndex() // index that clusters the points at different zoom levels, so we can create maps
    NewExpiringClusteringIndex(Minutes(15)) // index that clusters and expires the points at different zoom levels
                                            // so we can create real time maps of customer request, etc in the driver app

Performance Benchmarks

BenchmarkClusterIndexAdd                    500000          5395 ns/op
BenchmarkClusterIndexStreetRange            100000         22207 ns/op
BenchmarkClusterIndexCityRange              100000         16389 ns/op
BenchmarkClusterIndexEuropeRange            50000          36559 ns/op

BenchmarkExpiringClusterIndexAdd            300000          7124 ns/op
BenchmarkExpiringClusterIndexStreetRange    50000          27030 ns/op
BenchmarkExpiringClusterIndexCityRange      100000         22185 ns/op
BenchmarkExpiringClusterIndexEuropeRange    30000          52080 ns/op

BenchmarkCountIndexAdd                      1000000         1670 ns/op
BenchmarkCountIndexCityRange                100000         20325 ns/op

BenchmarkExpiringCountIndexAdd              500000          2808 ns/op
BenchmarkExpiringCountIndexRange            50000          35791 ns/op

BenchmarkPointIndexRange                    100000         15945 ns/op
BenchmarkPointIndexAdd                      1000000         2416 ns/op
BenchmarkPointIndexKNearest                 100000         13788 ns/op

BenchmarkExpiringPointIndexAdd              500000          4324 ns/op
BenchmarkExpiringPointIndexKNearest         100000         15638 ns/op
BenchmarkExpiringPointIndexRange            100000         20386 ns/op
You might also like...
Fast ring-buffer deque (double-ended queue)

deque Fast ring-buffer deque (double-ended queue) implementation. For a pictorial description, see the Deque diagram Installation $ go get github.com/

Fast in-memory key:value store/cache with TTL

MCache library go-mcache - this is a fast key:value storage. Its major advantage is that, being essentially a thread-safe . map[string]interface{} wit

A fast little LRU cache for Go

tinylru A fast little LRU cache. Getting Started Installing To start using tinylru, install Go and run go get: $ go get -u github.com/tidwall/tinylru

Fast Raft framework using the Redis protocol for Go
Fast Raft framework using the Redis protocol for Go

This project has been archived. Please check out Uhaha for a fitter, happier, more productive Raft framework. Finn is a fast and simple framework for

Fast golang queue using ring-buffer

Queue A fast Golang queue using a ring-buffer, based on the version suggested by Dariusz Górecki. Using this instead of other, simpler, queue implemen

go/golang: fast bit set Bloom filter

package implements a fast bloom filter with real 'bitset' and JSONMarshal/JSONUnmarshal to store/reload the Bloom filter.

Implementation of Boyer-Moore fast string search algorithm in Go

boyermoore Implementation of Boyer-Moore fast string search algorithm in Go

A fast (5x) string keyed read-only map for Go - particularly good for keys using a small set of nearby runes.

faststringmap faststringmap is a fast read-only string keyed map for Go (golang). For our use case it is approximately 5 times faster than using Go's

A fast, threadsafe skip list in Go
A fast, threadsafe skip list in Go

fast-skiplist Purpose As the basic building block of an in-memory data structure store, I needed an implementation of skip lists in Go. It needed to b

Comments
  • [Question] Is this package concurrency-safe?

    [Question] Is this package concurrency-safe?

    Hello, I was taking a look at the source code and noticed that the index maps do not have mutex locks. Maps in Go are not atomic and will crash the program if read from and written to concurrently.

    Perhaps there is something I am missing? Otherwise, I might later add a PR. Just wanted to make sure I wasn't missing something first.

    opened by umpc 2
  • Improved performance + added Clone

    Improved performance + added Clone

    Changed the underlying geoindex to not store the value being indexed and just store the ID instead, this reduces some of the memory overhead. This means that the Set interface has changed.

    Also added is a Clone method to each index.

    opened by dancannon 0
  • Fixing typo and return values in README example.

    Fixing typo and return values in README example.

    The example in the README.md file had a copy and past error with lat being used in the Driver Lon method. Also the Lat(), Lon(), and Id() methods were all missing return types.

    opened by pmaseberg 0
  • Incorrect use of assert.Equal (Minor)

    Incorrect use of assert.Equal (Minor)

    I think the use of assert.Equal in points-index_test.go might be incorrect. There are several instances where the final argument is true. I think it should either be removed or changed to a string according to the docs: https://godoc.org/github.com/stretchr/testify/assert#Equal

    I don't think true is currently causing trouble because all of the asserts pass. However, if the asserts where to fail, a panic results instead of a printout of the failure.

    Actual:

    --- FAIL: TestKNearest (0.00s)
    panic: interface conversion: interface is bool, not string [recovered]
        panic: interface conversion: interface is bool, not string
    

    Desired:

    --- FAIL: TestKNearest (0.00s)
            Error Trace:    points-index_test.go:46
        Error:      Not equal: []geoindex.Point{(*geoindex.GeoPoint)(0x8213dba40), (*geoindex.GeoPoint)(0x8213dbf00), (*geoindex.GeoPoint)(0x821410760), (*geoindex.GeoPoint)(0x8213dbba0), (*geoindex.GeoPoint)(0x821410d40)} (expected)
                        != []geoindex.Point{(*geoindex.GeoPoint)(0x61cbc0), (*geoindex.GeoPoint)(0x61cbe0), (*geoindex.GeoPoint)(0x61cb40), (*geoindex.GeoPoint)(0x61cb60), (*geoindex.GeoPoint)(0x61cc20)} (actual)
    
                Diff:
                --- Expected
                +++ Actual
                @@ -1,7 +1,7 @@
                -([]geoindex.Point) (len=5 cap=16) {
                - (*geoindex.GeoPoint)(0x8213dba40)(48 51.508359 -0.124803),
                - (*geoindex.GeoPoint)(0x8213dbf00)(86 51.507312 -0.122367),
                - (*geoindex.GeoPoint)(0x821410760)(153 51.511291 -0.128242),
                - (*geoindex.GeoPoint)(0x8213dbba0)(59 51.512760 -0.124507),
                - (*geoindex.GeoPoint)(0x821410d40)(200 51.509860 -0.133700)
                +([]geoindex.Point) (len=5 cap=5) {
                + (*geoindex.GeoPoint)(0x61cbc0)(48 51.508359 -0.124803),
                + (*geoindex.GeoPoint)(0x61cbe0)(86 51.507312 -0.122367),
                + (*geoindex.GeoPoint)(0x61cb40)(153 51.511291 -0.128242),
                + (*geoindex.GeoPoint)(0x61cb60)(59 51.512760 -0.124507),
                + (*geoindex.GeoPoint)(0x61cc20)(299 51.501402 -0.125002)
                 }
    

    Very minor but I noticed it while making some local tweaks so I figured I would mention it.

    Thanks for creating this package! Looks really good and I'm excited to test it out.

    opened by escholtz 0
Owner
Hailo Network IP Ltd
Hailo Network IP Ltd
Structscanner is a simple library to make going from database queries to structs easier

structscanner is a simple library to make going from database queries to structs easier, while retaining the flexibility of joins and mapping using struct tags.

Folktale 4 Aug 15, 2022
:pushpin: State of the art point location and neighbour finding algorithms for region quadtrees, in Go

Region quadtrees in Go Region quadtrees and efficient neighbour finding techniques in Go Go-rquad proposes various implementations of region quadtrees

Aurélien Rainone 120 Jun 22, 2022
Cache Slow Database Queries

Cache Slow Database Queries This package is used to cache the results of slow database queries in memory or Redis. It can be used to cache any form of

null 116 Sep 10, 2022
A package for Go that can be used for range queries on large number of intervals

go-stree go-stree is a package for Go that can be used to process a large number of intervals. The main purpose of this module is to solve the followi

Thomas Oberndörfer 39 May 14, 2022
Go library for encoding native Go structures into generic map values.

wstructs origin: github.com/things-go/structs Go library for encoding native Go structures into generic map values. Installation Use go get. go ge

null 0 Jan 10, 2022
Package set is a small wrapper around the official reflect package that facilitates loose type conversion and assignment into native Go types.

Package set is a small wrapper around the official reflect package that facilitates loose type conversion and assignment into native Go types. Read th

null 38 Sep 4, 2022
dagger is a fast, concurrency safe, mutable, in-memory directed graph library with zero dependencies

dagger is a blazing fast, concurrency safe, mutable, in-memory directed graph implementation with zero dependencies

Coleman Word 263 Sep 1, 2022
Data structure and relevant algorithms for extremely fast prefix/fuzzy string searching.

Trie Data structure and relevant algorithms for extremely fast prefix/fuzzy string searching. Usage Create a Trie with: t := trie.New() Add Keys with:

Derek Parker 605 Sep 23, 2022
Fast and easy-to-use skip list for Go.

Skip List in Golang Skip list is an ordered map. See wikipedia page skip list to learn algorithm details about this data structure. Highlights in this

Huan Du 297 Sep 23, 2022
Go implementation of SipHash-2-4, a fast short-input PRF created by Jean-Philippe Aumasson and Daniel J. Bernstein.

SipHash (Go) Go implementation of SipHash-2-4, a fast short-input PRF created by Jean-Philippe Aumasson and Daniel J. Bernstein (http://131002.net/sip

Dmitry Chestnykh 244 Sep 7, 2022