dgryski / go-simstore Goto Github PK

simhash storage and searching

Go 100.00%

go-simstore's Introduction

go-simstore: store and search through simhashes

This package is an implementation of section 3 of "Detecting Near-Duplicates for Web Crawling" by Manku, Jain, and Sarma,

http://www2007.org/papers/paper215.pdf

simhash is a simple simhashing library.
simstore is the storage and searching logic
simd is a small daemon that wraps simstore and exposes a http /search endpoint

This code is licensed under the MIT license

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

go-simstore's People

Contributors

Stargazers

Watchers

go-simstore's Issues

What is the license for this fine code?

@dgryski Damian: what would be the license?
Cordially
Philippe

Switch to radix sort?

The sorting in the finalize step is very expensive. We can probably do better than quicksort since we know we're sorting integers. Especially if we want to update the tables and call Finalize() again, it would be nice not to hit O(n^2) behaviour (although Go drops to mergesort if the recursion level gets too high, we're still in O(n log n) territory).

What are the four stores that differ in their space? Still feature, or other?

store = simstore.New3Small(sigsEstimate)
store = simstore.New3(sigsEstimate, factory)
store = simstore.New6(sigsEstimate, factory)
vpt = vptree.New(items)

Smaller memory usage

For d-3, we use the 4/4 split causing a blow up of 16x. The paper lays out another layout that has just a 4x blowup, but more fingerprints to search through.

Add compressed tables

Section 3.2 "compression of fingerprints" lays out a scheme for efficiently coding the tables to use less space.

Support bit differences > 3

Maximum hamming distance is currently hard-coded to <=3. It would be nice to have a few other options.

ScanBytesTrigrams slice bounds out of range

I received a panic: runtime error: slice bounds out of range on scanners.go#L46.

This issue is very interesting since, at first glance, that line should get OOB at the end of every string since atEOF is false and len(data) goes less than 3. I'm very curious to hear an explanation. I'm assuming there's a slice behind the data slice that keeps this code from blowing up every time.

Anyway, you can trigger the panic from TestSimHash with the following addition:

h4 := simhashString(strings.Repeat("Now is the winter", 241)) // length = 4097
fmt.Printf("h=%016x\n", h4)

The panic only occurs for me when the string size hits 4096+.

I'm on Go v1.5.1 linux/amd64.

Add brute force search

These turn out not to be too slow because memory is fast.

Determine applicability of multi index hashing

http://www.cs.toronto.edu/~norouzi/research/papers/multi_index_hashing.pdf

http://arxiv.org/abs/1307.2982

Compression code crashes on duplicate signatures

If hamming distance is not 6 or 3,what i will do ? reform store or build a new store?

In my project , the best distance is 12,so i reform the stuct of store6 . I add a function ,codes are below.

func (s *Store6) FindWithX(sig uint64, distance int) table {

	// empty store
	if s.Count == 0 {
		return nil
	}

	var ids []uint64

	// TODO(dgryski): search in parallel

	t := 0

	var p uint64

	for i := 0; i < 6; i++ {
		p = sig
		ids = append(ids, s.unshuffleList(s.rhashes[t].find(p, mask6_9_8, distance), t)...)
		t++
		p = (sig & 0xff80007fffffffff) | (sig & 0x007f800000000000 >> 8) | (sig & 0x00007f8000000000 << 8)
		ids = append(ids, s.unshuffleList(s.rhashes[t].find(p, mask6_9_8, distance), t)...)
		t++
		p = (sig & 0xff807f807fffffff) | (sig & 0x007f800000000000 >> 16) | (sig & 0x0000007f80000000 << 16)
		ids = append(ids, s.unshuffleList(s.rhashes[t].find(p, mask6_9_8, distance), t)...)
		t++
		p = (sig & 0xff807fff807fffff) | (sig & 0x007f800000000000 >> 24) | (sig & 0x000000007f800000 << 24)
		ids = append(ids, s.unshuffleList(s.rhashes[t].find(p, mask6_9_8, distance), t)...)
		t++
		p = (sig & 0xff807fffff807fff) | (sig & 0x007f800000000000 >> 32) | (sig & 0x00000000007f8000 << 32)
		ids = append(ids, s.unshuffleList(s.rhashes[t].find(p, mask6_9_8, distance), t)...)
		t++
		p = (sig & 0xff807fffffff807f) | (sig & 0x007f800000000000 >> 40) | (sig & 0x0000000000007f80 << 40)
		ids = append(ids, s.unshuffleList(s.rhashes[t].find(p, mask6_9_8, distance), t)...)
		t++
		p = (sig & 0xff80ffffffffff80) | (sig & 0x007f000000000000 >> 48) | (sig & 0x000000000000007f << 48)
		ids = append(ids, s.unshuffleList(s.rhashes[t].find(p, mask6_9_7, distance), t)...)
		t++
		sig = (sig << 9) | (sig >> (64 - 9))
	}

	p = sig
	ids = append(ids, s.unshuffleList(s.rhashes[t].find(p, mask6_10_8, distance), t)...)
	t++
	p = (sig & 0xffc0003fffffffff) | (sig & 0x003fc00000000000 >> 8) | (sig & 0x00003fc000000000 << 8)
	ids = append(ids, s.unshuffleList(s.rhashes[t].find(p, mask6_10_8, distance), t)...)
	t++
	p = (sig & 0xffc03fc03fffffff) | (sig & 0x003fc00000000000 >> 16) | (sig & 0x0000003fc0000000 << 16)
	ids = append(ids, s.unshuffleList(s.rhashes[t].find(p, mask6_10_8, distance), t)...)
	t++
	p = (sig & 0xffc03fffc03fffff) | (sig & 0x003fc00000000000 >> 24) | (sig & 0x000000003fc00000 << 24)
	ids = append(ids, s.unshuffleList(s.rhashes[t].find(p, mask6_10_8, distance), t)...)
	t++
	p = (sig & 0xffc03fffffc03fff) | (sig & 0x003fc00000000000 >> 32) | (sig & 0x00000000003fc000 << 32)
	ids = append(ids, s.unshuffleList(s.rhashes[t].find(p, mask6_10_8, distance), t)...)
	t++
	p = (sig & 0xffc07fffffffc07f) | (sig & 0x003f800000000000 >> 40) | (sig & 0x0000000000003f80 << 40)
	ids = append(ids, s.unshuffleList(s.rhashes[t].find(p, mask6_10_7, distance), t)...)
	t++
	p = (sig & 0xffc07fffffffff80) | (sig & 0x003f800000000000 >> 47) | (sig & 0x000000000000007f << 47)
	ids = append(ids, s.unshuffleList(s.rhashes[t].find(p, mask6_10_7, distance), t)...)
	t++
	ids = unique(ids)
	var ts table
	for _, v := range ids {
		ts = append(ts, s.docids.search(v)...)
	}
	return ts
}

But , when i tested the demo ,i found a problem , test's code and result is below.
Test:

func TestAdd6(t *testing.T) {
	s := New6(size, NewU64Slice)
	testRealAdd(t, s, size, queries, 6)
}
func testRealAdd(t *testing.T, s Storage, size, queries, d int) {
	s.Add(1189710714089908775, 111)
	for i := 0; i < 20; i++ {
		s.Add(uint64(rand.Int63()), uint64(i))
	}

	s.Finish()
	table := s.FindWithX(6451357090505977391, 12)
	t.Logf("result %+v", table)
}

Result:

Found NOTHING!,the Hamming distance 1189710714089908775 and 6451357090505977391 is 12.

Add graphite metrics to simd.

The simd service has no introspection. Add metrics.

Switch to interpolation search?

Implementation in trifles/interp. Initial numbers show it about twice as fast and sort.Search(), but that might also just be the lack of function call overhead. On large arrays it should reduce the number of probes to main memory.

Empty simstore causes panic

panic: runtime error: invalid memory address or nil pointer dereference

Test code:

ss := simstore.New6(0, simstore.NewU64Slice)
ss.Finish()

github.com/dgryski/go-simstore/simstore.go:184

ss := simstore.New6(0, simstore.NewU64Slice)
ss.Find(0)

github.com/dgryski/go-simstore/simstore6.go:141

Add on-disk table storage

Only store hash->docid mapping once

At the moment each of the many tables stores both the hashes and the document IDs. If we store the hash->point mappings only once, we can reduce the space requirements even though we have to store an extra lookup table. Probably use the O(1) lookup from the multi-probe consistent hashing paper.

Optimize block decompression

We can speed up block decompression combining it with a find operation. We can exit early once we no longer have any matches for our target signature and also reduce allocations since we don't need to store the decompressed integers.

dgryski / go-simstore Goto Github PK

go-simstore's Introduction

go-simstore's People

Contributors

Stargazers

Watchers

Forkers

go-simstore's Issues

Recommend Projects

Recommend Topics

Recommend Org