CS5228-Project/tQuery_prototype.py at master · PsLink/CS5228-Project · GitHub

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
#!/usr/bin/env python

# filter of cTree
# Prototype version

import fileinput
import math


errBound = 20
score = 0
candidate = set([])

def transback(k): #need to reverse back
	ans = []
	order = 1728
	while order >= 1:
		ans.insert(0,k/order)
		k = k % order
		order = order / 12
	return ans

def SDist(x,y):
	ans = 0
	for i in xrange(4):
		ans = ans + abs(x[i] - y[i])
	return ans

def search(k, table, query, iniScore):
	filename = "treeO_"+str(k)+".txt"
	#print "searching",k
	f = open(filename,'r')

	ans = set([])

	i = f.readline()


	while (len(i)>0):
		tmpScore = iniScore

		sig = i.split()

		insID = int(sig[0])
		#print insID

		offs = 0

		for j in sig[1:]:
			tmpScore = tmpScore + SDist(transback(int(j)),query[offs:offs+4])
			offs = offs + 4
			if tmpScore > errBound:
				break

		if tmpScore<=errBound:
			ans.add(insID)

		i = f.readline()

	return ans


def main():
	query = [4,6,4,5,4,4,8,6,4,5,7,5,4,6,9,5,4,3,4,8,7,7,4,4]

	qHead = query[0:4]

	insID = 0
	for i in fileinput.input("tree0.txt"):
		table = i.split()
		#print "------------"
		k = int(table[0])

		score = SDist(transback(int(table[0])),qHead)

		if (score<=errBound):
			# might filter the table with hash filter
			tmpCan = search(k, table[1:],query[4:],score)
			if len(tmpCan) > 0:
				#print tmpCan
				for t in tmpCan:
					candidate.add(t)

		insID = insID+1

	print candidate


if __name__ == '__main__':
	main()