Skip to content
This repository

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
tree: 64602c4313
file 1139 lines (1046 sloc) 40.326 kb
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139
'''
Copyright (c) 2011, Yahoo! Inc.
All rights reserved.

Redistribution and use of this software in source and binary forms,
with or without modification, are permitted provided that the following
conditions are met:

* Redistributions of source code must retain the above
copyright notice, this list of conditions and the
following disclaimer.

* Redistributions in binary form must reproduce the above
copyright notice, this list of conditions and the
following disclaimer in the documentation and/or other
materials provided with the distribution.

* Neither the name of Yahoo! Inc. nor the names of its
contributors may be used to endorse or promote products
derived from this software without specific prior
written permission of Yahoo! Inc.

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
'''

# Python implementation of Andoni's e2LSH. This version is fast because it
# uses Python hashes to implement the buckets. The numerics are handled
# by the numpy routine so this should be close to optimal in speed (although
# there is no control of the hash tables layout in memory.)

# This file implements the following classes
# lsh - the basic projection algorithm (on k-dimensional hash)
# index - a group of L lsh hashes
# TestDataClass - a generic class for handling the raw data
 
# To use
# Call this routine with the -histogram flag to create some random
# test data and to compute the nearest-neighbor distances
# Load the .distance file that is produced into Matlab and compute
# the d_nn and d_any histograms from the first and second columns
# of the .distance data.
# Use these histograms (and their bin positions) as input to the
# Matlab ComputeMPLSHParameters() routine.
# This gives you the optimum LSH parameters. You can use these
# values directly as parameters to this code.
# You can use the -ktest, -ltest and -wtest flags to test the
# parameters.

# Prerequisites: Python version 2.6 (2.5 might work) and NumPy

# By Malcolm Slaney, Yahoo! Research

import random, numpy, pickle, os, operator, traceback, sys, math, time
import itertools # For Multiprobe

#######################################################################
# Note, the data is always a numpy array of size Dx1.
#######################################################################

# This class just implements k-projections into k integers
# (after quantization) and then reducing that integer vector
# into a T1 and T2 hash. Data can either be entered into a
# table, or retrieved.

class lsh:
'''This class implements one k-dimensional projection, the T1/T2 hashing
and stores the results in a table for later retrieval. Input parameters
are the bin width (w, floating point, or float('inf') to get binary LSH),
and the number of projections to compute for one table entry (k, an integer).'''
def __init__(self, w, k):
self.k = k # Number of projections
self.w = w # Bin width
self.projections = None
self.buckets = {}

# This only works for Python >= 2.6
def sizeof(self):
'''Return how much storage is needed for this object. In bytes
'''
return sys.getsizeof(self.buckets) + \
sys.getsizeof(self.projections) + \
sys.getsizeof(self)

# Create the random constants needed for the projections.
# Can't do this until we see some data, so we know the
# diementionality.
def CreateProjections(self, dim):
self.dim = dim
# print "CreateProjections: Creating projection matrix for %dx%d data." % (self.k, self.dim)
self.projections = numpy.random.randn(self.k, self.dim)
self.bias = numpy.random.rand(self.k, 1)
if 0:
print "Dim is", self.dim
print 'Projections:\n', self.projections
# print 'T1 hash:\n', self.t1hash
# print 'T2 hash:\n', self.t2hash
if 0:
# Write out the project data so we can check it's properties.
# Should be Gaussian with mean of zero and variance of 1.
fp = open('Projections.data', 'w')
for i in xrange(0,self.projections.shape[0]):
for j in xrange(0,self.projections.shape[1]):
fp.write('%g ' % self.projections[i,j])
fp.write('\n')

# Compute the t1 and t2 hashes for some data. Doing it this way
# instead of in a loop, as before, is 10x faster. Thanks to Anirban
# for pointing out the flaw. Not sure if the T2 hash is needed since
# our T1 hash is so strong.
debugFP = None
firstTimeCalculateHashes = False # Change to false to turn this off
infinity = float('inf') # Easy way to access this flag
def CalculateHashes(self, data):
'''Multiply the projection data (KxD) by some data (Dx1),
and quantize'''
if self.projections == None:
self.CreateProjections(len(data))
bins = numpy.zeros((self.k,1), 'int')
if lsh.firstTimeCalculateHashes:
print 'data = ', numpy.transpose(data)
print 'bias = ', numpy.transpose(self.bias)
print 'projections = ',
for i in range(0, self.projections.shape[0]):
for j in range(0, self.projections.shape[1]):
print self.projections[i][j],
print
# print 't1Hash = ', self.t1hash
# print 't2Hash = ', self.t2hash
firstTimeCalculateHashes = False
print "Bin values:", self.bias + \
numpy.dot(self.projections, data)/self.w
print "Type of bins:", type(self.bias + \
numpy.dot(self.projections, data)/self.w)
if 0:
if lsh.debugFP == None:
print "Opening Projections file"
lsh.debugFP = open('Projections.data', 'w')
d = self.bias + numpy.dot(self.projections, data)/self.w
for i in xrange(0, len(d)):
lsh.debugFP.write('%g\n' % d[i])
lsh.debugFP.write('\n')
lsh.debugFP.flush()
if self.w == lsh.infinity:
# Binary LSH
bins[:] = (numpy.sign(numpy.dot(self.projections, data))+1)/2.0
else:
bins[:] = numpy.floor(self.bias + numpy.dot(self.projections, data)/self.w)
t1 = self.ListHash(bins)
t2 = self.ListHash(bins[::-1]) # Reverse data for second hash
return t1, t2

# Input: A Nx1 array (of integers)
# Output: A 28 bit hash value.
# From: http://stackoverflow.com/questions/2909106/
# python-whats-a-correct-and-good-way-to-implement-hash/2909572#2909572
def ListHash(self, d):
# return str(d).__hash__() # Good for testing, but not efficient
if d == None or len(d) == 0:
return 0
# d = d.reshape((d.shape[0]*d.shape[1]))
value = d[0, 0] << 7
for i in d[:,0]:
value = (101*value + i)&0xfffffff
return value

# Just a debug version that returns the bins too.
def CalculateHashes2(self, data):
if self.projections == None:
print "CalculateHashes2: data.shape=%s, len(data)=%d" % (str(data.shape), len(data))
self.CreateProjections(len(data))
bins = numpy.zeros((self.k,1), 'int')
parray = numpy.dot(self.projections, data)
bins[:] = numpy.floor(parray/self.w + self.bias)
t1 = self.ListHash(bins)
t2 = self.ListHash(bins[::-1]) # Reverse data for second hash
# print self.projections, data, parray, bins
# sys.exit(1)
return t1, t2, bins, parray

# Return a bunch of hashes, depending on the level of multiprobe
# asked for. Each list entry contains T1, T2. This is a Python
# iterator... so call it in a for loop. Each iteration returns
# a bin ID (t1,t2)
# [Need to store bins in integer array so we don't convert to
# longs prematurely and get the wrong hash!]
def CalculateHashIterator(self, data, multiprobeRadius=0):
if self.projections == None:
self.CreateProjections(len(data))
bins = numpy.zeros((self.k,1), 'int')
directVector = numpy.zeros((self.k,1), 'int')
newProbe = numpy.zeros((self.k,1), 'int')
if self.w == lsh.infinity:
points = numpy.dot(self.projections, data)
bins[:] = (numpy.sign(points)+1)/2.0
directVector[:] = -numpy.sign(bins-0.5)
else:
points = numpy.dot(self.projections, data)/self.w + self.bias
bins[:] = numpy.floor(points)
directVector[:] = numpy.sign(points-numpy.floor(points)-0.5)
t1 = self.ListHash(bins)
t2 = self.ListHash(bins[::-1])
yield (t1,t2)
if multiprobeRadius > 0:
# print "Multiprobe points:", points
# print "Multiprobe bin:", bins
# print "Multiprobe direct:", directVector
dimensions = range(self.k)
deltaVector = numpy.zeros((self.k, 1), 'int') # Preallocate
for r in range(1, multiprobeRadius+1):
# http://docs.python.org/library/itertools.html
for candidates in itertools.combinations(dimensions, r):
deltaVector *= 0 # Start Empty
deltaVector[list(candidates), 0] = 1 # Set some bits
newProbe[:] = bins + deltaVector*directVector # New probe
t1 = self.ListHash(newProbe)
t2 = self.ListHash(newProbe[::-1]) # Reverse data for second hash
# print "Multiprobe probe:",newProbe, t1, t2
yield (t1,t2)

# Put some data into the hash bucket for this LSH projection
def InsertIntoTable(self, id, data):
(t1, t2) = self.CalculateHashes(data)
if t1 not in self.buckets:
self.buckets[t1] = {t2: [id]}
else:
if t2 not in self.buckets[t1]:
self.buckets[t1][t2] = [id]
else:
self.buckets[t1][t2].append(id)

# Find some data in the hash bucket. Return all the ids
# that we find for this T1-T2 pair.
def FindXXObsolete(self, data):
(t1, t2) = self.CalculateHashes(data)
if t1 not in self.buckets:
return []
row = self.buckets[t1]
if t2 not in row:
return []
return row[t2]

#
def Find(self, data, multiprobeRadius=0):
'''Find the points that are close to the query data. Use multiprobe
to also look in nearby buckets.'''
res = []
for (t1,t2) in self.CalculateHashIterator(data, multiprobeRadius):
# print "Find t1:", t1
if t1 not in self.buckets:
continue
row = self.buckets[t1]
if t2 not in row:
continue
res += row[t2]
return res

# Create a dictionary showing all the buckets an ID appears in
def CreateDictionary(self, theDictionary, prefix):
for b in self.buckets: # Over all buckets
w = prefix + str(b)
for c in self.buckets[b]:# Over all T2 hashes
for i in self.buckets[b][c]:#Over ids
if not i in theDictionary:
theDictionary[i] = [w]
else:
theDictionary[i] += w
return theDictionary


# Print some stats for these lsh buckets
def StatsXXX(self):
maxCount = 0; sumCount = 0;
numCount = 0; bucketLens = [];
for b in self.buckets:
for c in self.buckets[b]:
l = len(self.buckets[b][c])
if l > maxCount:
maxCount = l
maxLoc = (b,c)
# print b,c,self.buckets[b][c]
sumCount += l
numCount += 1
bucketLens.append(l)
theValues = sorted(bucketLens)
med = theValues[(len(theValues)+1)/2-1]
print "Bucket Counts:"
print "\tTotal indexed points:", sumCount
print "\tT1 Buckets filled: %d/%d" % (len(self.buckets), 0)
print "\tT2 Buckets used: %d/%d" % (numCount, 0)
print "\tMaximum T2 chain length:", maxCount, "at", maxLoc
print "\tAverage T2 chain length:", float(sumCount)/numCount
print "\tMedian T2 chain length:", med

def HealthStats(self):
'''Count the number of points in each bucket (which is currently
a function of both T1 and T2)'''
maxCount = 0; numCount = 0; totalIndexPoints = 0;
for b in self.buckets:
for c in self.buckets[b]:
l = len(self.buckets[b][c])
if l > maxCount:
maxCount = l
maxLoc = (b,c)
# print b,c,self.buckets[b][c]
totalIndexPoints += l
numCount += 1
T1Buckets = len(self.buckets)
T2Buckets = numCount
T1T2BucketAverage = totalIndexPoints/float(numCount)
T1T2BucketMax = maxCount
return (T1Buckets, T2Buckets, T1T2BucketAverage, T1T2BucketMax)

# Get a list of all IDs that are contained in these hash buckets
def GetAllIndices(self):
theList = []
for b in self.buckets:
for c in self.buckets[b]:
theList += self.buckets[b][c]
return theList

# Put some data into the hash table, see how many collisions we get.
def Test(self, n):
self.buckets = {}
self.projections = None
d = numpy.array([.2,.3])
for i in range(0,n):
self.InsertIntoTable(i, d+i)
for i in range(0,n):
r = self.Find(d+i)
matches = sum(map(lambda x: x==i, r))
if matches == 0:
print "Couldn't find item", i
elif matches == 1:
pass
if len(r) > 1:
print "Found big bin for", i,":", r


# Put together several LSH projections to form an index. The only
# new parameter is the number of groups of projections (one LSH class
# object per group.)
class index:
def __init__(self, w, k, l):
self.k = k;
self.l = l
self.w = w
self.projections = []
self.myIDs = []
for i in range(0,l): # Create all LSH buckets
self.projections.append(lsh(w, k))

# Only works for Python > 2.6
def sizeof(self):
'''Return the sizeof this index in bytes.
'''
return sum(p.sizeof() for p in self.projections) + \
sys.getsizeof(self)

# Replace id we are given with a numerical id. Since we are going
# to use the ID in L tables, it is better to replace it here with
# an integer. We store the original ID in an array, and return it
# to the user when we do a find().
def AddIDToIndex(self, id):
if type(id) == int:
return id # Don't bother if already an int
self.myIDs.append(id)
return len(self.myIDs)-1

def FindID(self, id):
if type(id) != int or id < 0 or id >= len(self.myIDs):
return id
return self.myIDs[id]

# Insert some data into all LSH buckets
def InsertIntoTable(self, id, data):
intID = self.AddIDToIndex(id)
for p in self.projections:
p.InsertIntoTable(intID, data)

def FindXXObsolete(self, data):
'''Find some data in all the LSH buckets. Return a list of
data's id and bucket counts'''
items = [p.Find(data) for p in self.projections]
results = {}
for itemList in items:
for item in itemList:
if item in results: # Much faster without setdefault
results[item] += 1
else:
results[item] = 1
s = sorted(results.items(), key=operator.itemgetter(1), \
reverse=True)
return [(self.FindID(i),c) for (i,c) in s]

def Find(self, queryData, multiprobeR=0):
'''Find some data in all the LSH tables. Use Multiprobe, with
the given radius, to search neighboring buckets. Return a list of
results. Each result is a tuple consisting of the candidate ID
and the number of times it was found in the index.'''
results = {}
for p in self.projections:
ids = p.Find(queryData, multiprobeR)
# print "Got back these IDs from p.Find:", ids
for id in ids:
if id in results:
results[id] += 1
else:
results[id] = 1
s = sorted(results.items(), key=operator.itemgetter(1), \
reverse=True)
return [(self.FindID(i),c) for (i,c) in s]

def FindExact(self, queryData, GetData, multiprobeR=0):
'''Return a list of results sorted by their exact
distance from the query. GetData is a function that
returns the original data given its key. This function returns
a list of results, each result has the candidate ID and distance.'''
s = self.Find(queryData, multiprobeR)
# print "Intermediate results are:", s
d = map(lambda (id,count): (id,((GetData(id)-queryData)**2).sum(), \
count), s)
s = sorted(d, key=operator.itemgetter(1))
return [(self.FindID(i),d) for (i,d,c) in s]

# Put some data into the hash tables.
def Test(self, n):
d = numpy.array([.2,.3])
for i in range(0,n):
self.InsertIntoTable(i, d+i)
for i in range(0,n):
r = self.Find(d+i)
print r

# Print the statistics of each hash table.
def Stats(self):
for i in range(0, len(self.projections)):
p = self.projections[i]
print "Buckets", i,
p.Stats()

# Get al the IDs that are part of this index. Just check one hash
def GetAllIndices(self):
if self.projections and len(self.projections) > 0:
p = self.projections[0]
return p.GetAllIndices()
return None

# Return the buckets (t1 and t2 hashes) associated with a data point
def GetBuckets(self, data):
b = []
for p in self.projections:
( t1, t2, bins, parray) = p.CalculateHashes2(data)
print "Bucket:", t1, t2, bins, parray
b += (t1, t2)
return b

#
def DictionaryPrefix(self, pc):
prefix = 'W'
prefixes = 'abcdefghijklmnopqrstuvwxyz'
while pc > 0: # Create unique ID for theis bucket
prefix += prefixes[pc%len(prefixes)]
pc /= len(prefixes)
return prefix

# Create a list ordered by ID listing which buckets are used for each ID
def CreateDictionary(self):
theDictionary = {}
pi = 0
for p in self.projections:
prefix = self.DictionaryPrefix(pi)
theDictionary = p.CreateDictionary(theDictionary,\
prefix)
pi += 1
return theDictionary

# Find the bucket ids that best correspond to this piece of data.
def FindBuckets(self, data):
theWords = []
pi = 0
for p in self.projections:
prefix = self.DictionaryPrefix(pi)
( t1, t2, bins, parray) = p.CalculateHashes2(data)
word = prefix + str(t1)
theWords += [word]
pi += 1
return theWords

# Save an LSH index to a pickle file.
def SaveIndex(filename, ind):
try:
fp = open(filename, 'w')
pickle.dump(ind, fp)
fp.close()
statinfo = os.stat(filename,)
if statinfo:
print "Wrote out", statinfo.st_size, "bytes to", \
filename
except:
print "Couldn't pickle index to file", filename
traceback.print_exc(file=sys.stderr)

# Read an LSH index from a pickle file.
def LoadIndex(filename):
if type(filename) == str:
try:
fp = open(filename, 'r')
except:
print "Couldn't open %s to read LSH Index" % (filename)
return None
else:
fp = filename
try:
ind = pickle.load(fp)
fp.close()
return ind
except:
print "Couldn't read pickle file", filename
traceback.print_exc(file=sys.stderr)




class TestDataClass:
'''A bunch of routines used to generate data we can use to test
this LSH implementation.'''
def __init__(self):
self.myData = None
self.myIndex = None
self.nearestNeighbors = {} # A dictionary pointing to IDs

def LoadData(self, filename):
'''Load data from a flat file, one line per data point.'''
lineCount = 0
try:
fp = open(filename)
if fp:
for theLine in fp: # Count lines in file
if theLine == '':
break
lineCount += 1
dim = len(theLine.split()) # Allocate the storage array
self.myData = numpy.zeros((dim, lineCount))
fp.seek(0,0) # Go back to beginning of file
lineCount = 0
for theLine in fp: # Now load the data
data = [float(i) for i in theLine.split()]
self.myData[:,lineCount] = data
lineCount += 1
fp.close()
else:
print "Can't open %s to LoadData()" % filename
except:
print "Error loading data from %s in TestDataClass.LoadData()" \
% filename
traceback.print_exc(file=sys.stderr)
print "self.myData has %d lines and is:" % lineCount, self.myData

def SaveData(self, filename):
'''Save this data in a flat file. One line per data point.'''
numDims = self.NumDimensions()
try:
fp = open(filename, 'w')
if fp:
for i in xrange(0, self.NumPoints()):
data = self.RetrieveData(i).reshape(numDims)
fp.write(' '.join([str(d) for d in data]) + '\n')
fp.close()
return
except:
pass
sys.stderr.write("Can't write test data to %s\n" % filename)

def CreateIndex(self, w, k, l):
'''Create an index for the data we have in our database. Inputs are
the LSH parameters: w, k and l.'''
self.myIndex = index(w, k, l)
itemCount = 0
tic = time.clock()
for itemID in self.IterateKeys():
features = self.RetrieveData(itemID)
if features != None:
self.myIndex.InsertIntoTable(itemID, features)
itemCount += 1
print "Finished indexing %d items in %g seconds." % \
(itemCount, time.clock()-tic)
sys.stdout.flush()

def RetrieveData(self, id):
'''Find a point in the array of data.'''
id = int(id) # Key in this base class is an int!
if id < self.myData.shape[1]:
return self.myData[:,id:id+1]
return None

def NumPoints(self):
'''How many data point are in this database?'''
return self.myData.shape[1]

def NumDimensions(self):
'''What is the dimensionality of the data?'''
return self.myData.shape[0]

def GetRandomQuery(self):
'''Pick a random query from the dataset. Return a key.'''
return random.randrange(0,self.NumPoints()) # Pick random query

def FindNearestNeighbors(self, count):
'''Exhaustive search for count nearest-neighbor results.
Save the results in a dictionary.'''
numPoints = self.NumPoints()
self.nearestNeighbors = {}
for i in xrange(0,count):
qid = self.GetRandomQuery() # Pick random query
qData = self.RetrieveData(qid) # Find it's data
nearestDistance2 = None
nearestIndex = None
for id2 in self.IterateKeys():
if qid != id2:
d2 = ((self.RetrieveData(id2)-qData)**2).sum()
if id == -1: # Debugging
print qid, id2, qData, self.RetrieveData(id2), d2
if nearestDistance2 == None or d2 < nearestDistance2:
nearestDistance2 = d2
nearestIndex = id2
self.nearestNeighbors[qid] = \
(nearestIndex, math.sqrt(nearestDistance2))
if qid == -1:
print qid, nearestIndex, math.sqrt(nearestDistance2)
sys.stdout.flush()

def SaveNearestNeighbors(self, filename):
'''Save the nearest neighbor dictionary in a file. Each line
of the file contains the query key, the distance to the nearest
neighbor, and the NN key.'''
if filename.endswith('.gz'):
import gzip
fp = gzip.open(filename, 'w')
else:
fp = open(filename, 'w')
if fp:
for (query,(nn,dist)) in self.nearestNeighbors.items():
fp.write('%s %g %s\n' % (str(query), dist, str(nn)))
fp.close()
else:
print "Can't open %s to write nearest-neighbor data" % filename

def LoadNearestNeighbors(self, filename):
'''Load a file full of nearest neighbor data.'''
self.nearestNeighbors = {}
if filename.endswith('.gz'):
import gzip
fp = gzip.open(filename, 'r')
else:
fp = open(filename, 'r')
if fp:
print "Loading nearest-neighbor data from:", filename
for theLine in fp:
(k,d,nn) = theLine.split()
if type(self.myData) == numpy.ndarray: # Check for array indices
k = int(k)
nn = int(nn)
if k < self.NumPoints() and nn < self.NumPoints():
self.nearestNeighbors[k] = (nn,float(d))
elif k in self.myData and nn in self.myData: # dictionary index
self.nearestNeighbors[k] = (nn,float(d))
fp.close()
print " Loaded %d items into the nearest-neighbor dictionary." % len(self.nearestNeighbors)
else:
print "Can't open %s to read nearest neighbor data." % filename

def IterateKeys(self):
'''Iterate through all possible keys in the dataset.'''
for i in range(self.NumPoints()):
yield i

def FindMedian(self):
numDim = self.NumDimensions()
numPoints = self.NumPoints()
oneColumn = numpy.zeros((numPoints))
medians = numpy.zeros((numDim))
for d in xrange(numDim):
rowNumber = 0
for k in self.IterateKeys():
oneData = self.RetrieveData(k)
oneColumn[rowNumber] = oneData[d]
rowNumber += 1
m = numpy.median(oneColumn, overwrite_input=True)
medians[d] = m
return medians

def ComputeDistanceHistogram(self, fp = sys.stdout):
'''Calculate the nearest-neighbor and any-neighbor distance
histograms needed for the LSH Parameter Optimization. For
a number of random query points, print the distance to the
nearest neighbor, and to any random neighbor. This becomes
the input for the parameter optimization routine. Enhanced
to also print the NN binary projections.'''
numPoints = self.NumPoints()
# medians = self.FindMedian() # Not used now, but useful for binary quantization
print "Pulling %d items from the NearestNeighbors list for ComputeDistanceHistogram" % \
len(self.nearestNeighbors.items())
for (queryKey,(nnKey,nnDist)) in self.nearestNeighbors.items():
randKey = self.GetRandomQuery()

queryData = self.RetrieveData(queryKey)
nnData = self.RetrieveData(nnKey)
randData = self.RetrieveData(randKey)
if len(queryData) == 0 or len(nnData) == 0: # Missing, probably because of subsampling
print "Skipping %s/%s because data is missing." % (queryKey, nnKey)
continue
anyD2 = ((randData-queryData)**2).sum()

projection = numpy.random.randn(1, queryData.shape[0])
# print "projection:", projection.shape
# print "queryData:", queryData.shape
# print "nnData:", nnData.shape
# print "randData:", randData.shape
queryProj = numpy.sign(numpy.dot(projection, queryData))
nnProj = numpy.sign(numpy.dot(projection, nnData))
randProj = numpy.sign(numpy.dot(projection, randData))

# print 'CDH:', queryProj, nnProj, randProj
fp.write('%g %g %d %d\n' % \
(nnDist, math.sqrt(anyD2), \
queryProj==nnProj, queryProj==randProj))
fp.flush()

def ComputePnnPany(self, w, k, l, multiprobe=0):
'''Compute the probability of Pnn and Pany for a given index size.
Create the desired index, populate it with the data, and then measure
the NN and ANY neighbor retrieval rates.
Return
the pnn rate for one 1-dimensional index (l=1),
the pnn rate for an l-dimensional index,
the pany rate for one 1-dimensional index (l=1),
and the pany rate for an l-dimensional index
the CPU time per query (seconds)'''
numPoints = self.NumPoints()
numDims = self.NumDimensions()
self.CreateIndex(w, k, l) # Put data into new index
cnn = 0; cnnFull = 0
cany = 0; canyFull = 0
queryCount = 0 # Probe the index
totalQueryTime = 0
startRecallTestTime = time.clock()
# print "ComputePnnPany: Testing %d nearest neighbors." % len(self.nearestNeighbors.items())
for (queryKey,(nnKey,dist)) in self.nearestNeighbors.items():
queryData = self.RetrieveData(queryKey)
if queryData == None or len(queryData) == 0:
print "Can't find data for key %s" % str(queryKey)
sys.stdout.flush()
continue
startQueryTime = time.clock() # Measure CPU time
matches = self.myIndex.Find(queryData, multiprobe)
totalQueryTime += time.clock() - startQueryTime
for (m,c) in matches:
if nnKey == m: # See if NN was found!!!
cnn += c
cnnFull += 1
if m != queryKey: # Don't count the query
cany += c
canyFull += len(matches)-1 # Total candidates minus 1 for query
queryCount += 1
# Some debugging for k curve.. print individual results
# print "ComputePnnPany Debug:", w, k, l, len(matches), numPoints, cnn, cnnFull, cany, canyFull
recallTestTime = time.clock() - startRecallTestTime
print "Tested %d NN queries in %g seconds." % (queryCount, recallTestTime)
sys.stdout.flush()
if queryCount == 0:
queryCount = 1 # To prevent divide by zero
perQueryTime = totalQueryTime/queryCount
print "CPP:", cnn, cnnFull, cany, canyFull
print "CPP:", cnn/float(queryCount*l), cnnFull/float(queryCount), \
cany/float(queryCount*l*numPoints), canyFull/float(queryCount*numPoints), \
perQueryTime, numDims
return cnn/float(queryCount*l), cnnFull/float(queryCount), \
cany/float(queryCount*l*numPoints), canyFull/float(queryCount*numPoints), \
perQueryTime, numDims

def ComputePnnPanyCurve(self, wList = .291032, multiprobe=0):
if type(wList) == float or type(wList) == int:
wList = [wList*10**((i-10)/10.0) for i in range(0,21)]
for w in wList:
(pnn, pnnFull, pany, panyFull, queryTime, numDims) = self.ComputePnnPany(w, 1, 10, multiprobe)
if w == wList[0]:
print "# w pnn pany queryTime"
print "PnnPany:", w, multiprobe, pnn, pany, queryTime
sys.stdout.flush()

def ComputeKCurve(self, kList, w = .291032, r=0):
'''Compute the number of ANY neighbors as a function of
k. Should go down exponentially.'''
numPoints = self.NumPoints()
l = 10
for k in sorted(list(kList)):
(pnn, pnnFull, pany, panyFull, queryTime, numDims) = self.ComputePnnPany(w, k, l, r)
print w, k, l, r, pnn, pany, pany*numPoints, queryTime
sys.stdout.flush()

def ComputeLCurve(self, lList, w = 2.91032, k=10, r=0):
'''Compute the probability of nearest neighbors as a function
of l.'''
numPoints = self.NumPoints()
firstTime = True
for l in sorted(list(lList)):
(pnn, pnnFull, pany, panyFull, queryTime, numDims) = self.ComputePnnPany(w, k, l, r)
if firstTime:
print "# w k l r pnnFull, panyFull panyFull*N queryTime"
firstTime = False
print w, k, l, r, pnnFull, panyFull, panyFull*numPoints, queryTime
sys.stdout.flush()



class RandomTestData(TestDataClass):
'''Generate uniform random data points between -1 and 1.'''
def CreateData(self, numPoints, dim):
self.myData = (numpy.random.rand(dim, numPoints)-.5)*2.0

class HyperCubeTestData(TestDataClass):
'''Create a hypercube of data. All points are in the corners'''
def CreateData(self, numDim, noise = None):
numPoints = 2**numDim
self.myData = numpy.zeros((numPoints, numDim))
for i in range(0,numPoints):
for b in range(0,numDim):
if (2**b) & i:
self.myData[b, i] = 1.0
if noise != None:
self.myData += (numpy.random.rand(numDim, numPoints)-.5)*noise

class RegularTestData(TestDataClass):
'''Fill the 2-D test array with a regular grid of points between -1 and 1'''
def CreateData(self, numDivs):
self.myData = numpy.zeros(((2*numDivs+1)**2,2))
i = 0
for x in range(-numDivs, numDivs+1):
for y in range(-numDivs, numDivs+1):
self.myData[0, i] = x/float(divs)
self.myData[1, i] = y/float(divs)
i += 1



# Use Dimension Doubling to measure the dimensionality of a random
# set of data. Generate some data (either random Gaussian or a grid)
# Then count the number of points that fall within the given radius of this
# query.
def XXXTestDimensionality2():
binWidth = .5
if True:
numPoints = 100000
myTestData = TestDataClass(numPoints, 3)
else:
myTestData = RegularTestData(100)
numPoints = myTestData.NumPoints
k = 4; l = 2; N = 1000
myTestIndex = index(binWidth, k, l, N)
for i in range(0,numPoints):
myTestIndex.InsertIntoTable(i, myTestData.RetrieveData(i))
rBig = binWidth/8.0
rSmall = rBig/2.0
cBig = 0.0; cSmall = 0.0
for id in random.sample(ind.GetAllIndices(), 2):
qp = FindLSHTestData(id)
cBig += myTestIndex.CountInsideRadius(qp, myTestData.FindData, rBig)
cSmall += myTestIndex.CountInsideRadius(qp, myTestData.FindData, rSmall)
if cBig > cSmall and cSmall > 0:
dim = math.log(cBig/cSmall)/math.log(rBig/rSmall)
else:
dim = 0
print cBig, cSmall, dim
return ind

                   
# Generate some 2-dimensional data, put it into an index and then
# show the points retrieved. This is all done as a function of number
# of projections per bucket, number of buckets to use for each index, and
# the number of LSH bucket (the T1 size). Write out the data so we can
# plot it (in Matlab)
def GraphicalTest(k, l, N):
numPoints = 1000
myTestData = TestDataClass(numPoints, 3)
ind = index(.1, k, l, N)
for i in range(0,numPoints):
ind.InsertIntoTable(i, myTestData.RetrieveData(i))
i = 42
r = ind.Find(data[i,:])
fp = open('lshtestpoints.txt','w')
for i in range(0,numPoints):
if i in r:
c = r[i]
else:
c = 0
fp.write("%g %g %d\n" % (data[i,0], data[i,1], c))
fp.close()
return r



def SimpleTest():
import time
dim = 250
numPoints = 10000
myTestData = RandomTestData()
myTestData.CreateData(numPoints,dim)
myTestIndex = index(w=.4, k=10, l=10, N=numPoints)
startLoad = time.clock()
for id in myTestData.IterateKeys():
data = myTestData.RetrieveData(id)
myTestIndex.InsertIntoTable(id, data)
endLoad = time.clock()
print "Time to load %d points is %gs (%gms per point)" % \
(numPoints, endLoad-startLoad, (endLoad-startLoad)/numPoints*1000.0)

startRecall = time.clock()
resCount = 0
resFound = 0
for id in myTestData.IterateKeys():
query = myTestData.RetrieveData(id)
res = myTestIndex.Find(query)
if not res == None and len(res) > 0:
resFound += 1
if not res == None:
resCount += len(res)
endRecall = time.clock()
print "Time to recall %d points is %gs (%gms per point" % \
(numPoints, endRecall-startRecall, (endRecall-startRecall)/numPoints*1000.0)
print "Found a recall hit all but %d times, average results per query is %g" % \
(numPoints-resFound, resCount/float(numPoints))




def OutputAllProjections(myTestData, myTestIndex, filename):
'''Calculate and output all the projected data for an index.'''
lshProjector = myTestIndex.projections[0]
fp = open(filename, 'w')
for id in myTestData.IterateKeys():
d = myTestData.RetrieveData(id)
(t1, t2, bins, parray) = lshProjector.CalculateHashes2(d)
fp.write('%d %d %g %g\n' % (t1, t2, bins[0][0], parray[0][0]))
fp.close()

# Exact Optimization:
# For 100000 5-d data use: w=2.91032 and get 0.55401 hits per bin and 0.958216 nn.
# K=23.3372 L=2.70766 cost is 2.98756
# Expected statistics for optimal solution:
# Assuming K=23, L=3
# p_nn(w) is 0.958216
# p_any(w) is 0.55401
# Probability of finding NN for L=1: 0.374677
# Probability of finding ANY for L=1: 1.26154e-06
# Probability of finding NN for L=3: 0.75548
# Probability of finding ANY for L=3: 3.78462e-06
# Expected number of hits per query: 0.378462

'''
10-D data:
Mean of Python NN data is 0.601529 and std is 0.0840658.
Scaling all distances by 0.788576 for easier probability calcs.
Simple Approximation:
For 100000 5-d data use: w=4.17052 and get 0.548534 hits per bin and 0.885004 nn.
K=19.172 L=10.4033 cost is 20.8065
Expected statistics: for simple approximation
Assuming K=19, L=10
Probability of finding NN for L=1: 0.0981652
Probability of finding ANY for L=1: 1.10883e-05
Probability of finding NN for L=10: 0.644148
Probability of finding ANY for L=10: 0.000110878
Expected number of hits per query: 11.0878
Exact Optimization:
For 100000 5-d data use: w=4.26786 and get 0.556604 hits per bin and 0.887627 nn.
K=21.4938 L=12.9637 cost is 17.3645
Expected statistics for optimal solution:
Assuming K=21, L=13
p_nn(w) is 0.887627
p_any(w) is 0.556604
Probability of finding NN for L=1: 0.0818157
Probability of finding ANY for L=1: 4.53384e-06
Probability of finding NN for L=13: 0.670323
Probability of finding ANY for L=13: 5.89383e-05
Expected number of hits per query: 5.89383
'''

if __name__ == '__main__':
defaultDims = 10
defaultW = 2.91032
defaultK = 10
defaultL = 1
defaultClosest = 1000
defaultMultiprobeRadius = 0
defaultFileName = 'testData'
cmdName = sys.argv.pop(0)
while len(sys.argv) > 0:
arg = sys.argv.pop(0).lower()
if arg == '-d':
arg = sys.argv.pop(0)
try:
defaultDims = int(arg)
defaultFileName = 'testData%03d' % defaultDims
except:
print "Couldn't parse new value for defaultDims: %s" % arg
print 'New default dimensions for test is', defaultDims
elif arg == '-f':
defaultFileName = sys.argv.pop(0)
print 'New file name is', defaultFileName
elif arg == '-k':
arg = sys.argv.pop(0)
try:
defaultK = int(arg)
except:
print "Couldn't parse new value for defaultK: %s" % arg
print 'New default k for test is', defaultK
elif arg == '-l':
arg = sys.argv.pop(0)
try:
defaultL = int(arg)
except:
print "Couldn't parse new value for defaultL: %s" % arg
print 'New default l for test is', defaultL
elif arg == '-c':
arg = sys.argv.pop(0)
try:
defaultClosest = int(arg)
except:
print "Couldn't parse new value for defaultClosest: %s" % arg
print 'New default number closest for test is', defaultClosest
elif arg == '-w':
arg = sys.argv.pop(0)
try:
defaultW = float(arg)
except:
print "Couldn't parse new value for w: %s" % arg
print 'New default W for test is', defaultW
elif arg == '-r':
arg = sys.argv.pop(0)
try:
defaultMultiprobeRadius = int(arg)
except:
print "Couldn't parse new value for multiprobeRadius: %s" % arg
print 'New default multiprobeRadius for test is', defaultMultiprobeRadius
elif arg == '-create': # Create some uniform random data and find NN
myTestData = RandomTestData()
myTestData.CreateData(100000, defaultDims)
myTestData.SaveData(defaultFileName + '.dat')
print "Finished creating random data. Now computing nearest neighbors..."
myTestData.FindNearestNeighbors(defaultClosest)
myTestData.SaveNearestNeighbors(defaultFileName + '.nn')
elif arg == '-histogram': # Calculate distance histograms
myTestData = TestDataClass()
myTestData.LoadData(defaultFileName + '.dat')
myTestData.LoadNearestNeighbors(defaultFileName + '.nn')
fp = open(defaultFileName + '.distances', 'w')
if fp:
myTestData.ComputeDistanceHistogram(fp)
fp.close()
else:
print "Can't open %s.distances to store NN data" % defaultFileName
elif arg == '-sanity':
myTestData = TestDataClass()
myTestData.LoadData(defaultFileName + '.dat')
print myTestData.RetrieveData(myTestData.GetRandomQuery())
print myTestData.RetrieveData(myTestData.GetRandomQuery())
elif arg == '-b': # Calculate bucket probabilities
random.seed(0)
myTestData = TestDataClass()
myTestData.LoadData(defaultFileName + '.dat')
myTestData.LoadNearestNeighbors(defaultFileName + '.nn')
# ComputePnnPanyCurve(myData, [.291032])
myTestData.ComputePnnPanyCurve(defaultW)
elif arg == '-wtest': # Calculate bucket probabilities as a function of w
random.seed(0)
myTestData = TestDataClass()
myTestData.LoadData(defaultFileName + '.dat')
myTestData.LoadNearestNeighbors(defaultFileName + '.nn')
wList = [defaultW*.5**-i for i in range(-10,10)]
# wList = [defaultW*.5**-i for i in range(-3,3)]
myTestData.ComputePnnPanyCurve(wList, defaultMultiprobeRadius)
elif arg == '-ktest': # Calculate bucket probabilities as a function of k
random.seed(0)
myTestData = TestDataClass()
myTestData.LoadData(defaultFileName + '.dat')
myTestData.LoadNearestNeighbors(defaultFileName + '.nn')
# ComputePnnPanyCurve(myData, [.291032])
kList = [math.floor(math.sqrt(2)**k) for k in range(0,10)]
kList = [1,2,3,4,5,6,8,10,12,14,16,18,20,22,25,30,35,40]
myTestData.ComputeKCurve(kList, defaultW, defaultMultiprobeRadius)
elif arg == '-ltest': # Calculate bucket probabilities as a function of l
random.seed(0)
myTestData = TestDataClass()
myTestData.LoadData(defaultFileName + '.dat')
myTestData.LoadNearestNeighbors(defaultFileName + '.nn')
# ComputePnnPanyCurve(myData, [.291032])
lList = [math.floor(math.sqrt(2)**k) for k in range(0,10)]
lList = [1,2,3,4,5,6,8,10,12,14,16,18,20,22,25,30]
myTestData.ComputeLCurve(lList, w=defaultW,
k=defaultK, r=defaultMultiprobeRadius)
elif arg == '-timing':
# sys.argv.pop(0)
timingModels = []
while len(sys.argv) > 0:
print "Parsing timing argument", sys.argv[0], len(sys.argv)
if sys.argv[0].startswith('-'):
break
try:
(w,k,l,r,rest) = sys.argv[0].strip().split(',', 5)
timingModels.append([float(w), int(k), int(l), int(r)])
except:
print "Couldn't parse %s. Need w,k,l,r" % sys.argv[0]
sys.argv.pop(0)
myTestData = TestDataClass()
myTestData.LoadData(defaultFileName + '.dat')
myTestData.LoadNearestNeighbors(defaultFileName + '.nn')
for (w, k, l, r) in timingModels:
sys.stdout.flush()
(pnnL1, pnn, panyL1, pany, perQueryTime, numDims) = myTestData.ComputePnnPany(w, k, l, r)
print "Timing:", w, k, l, r, myTestData.NumPoints(), pnn, pany, perQueryTime*1000.0, numDims

elif arg == '-test': # Calculate bucket probabilities as a function of l
random.seed(0)
myTestData = TestDataClass()
myTestData.LoadData(defaultFileName + '.dat')
myTestData.LoadNearestNeighbors(defaultFileName + '.nn')
# ComputePnnPanyCurve(myData, [.291032])
myTestData.ComputeLCurve([defaultL], w=defaultW, k=defaultK)
else:
print '%s: Unknown test argument %s' % (cmdName, arg)
Something went wrong with that request. Please try again.