[Python] Implementing Trie (or similar data structure) on spark

I'm working as an intern, I've been tasked with implementing a fast searching algorithm for phone numbers on their spark cluster, using tries (prefix tree), and performing operations such as inner join on several such tries

I managed to create get it working for about 5 million numbers (2 tries, with 2.5 mllion numbers in each) I've been tasked to scale it up to 10-20 million. though if I try to go above that I get Java.outofmemory error

Right Now my approach is this My code, - create a dataframe of phonenumbers from the spark database, - loads 2.5 million numbers into memory (memory of the JVM) in a python list, using collect() - converts that list into trie - clear the list - search the number_to_be_searched in the trie - if found return true - else load next 2.5 million numbers, and repeat step 3 and so on

from collections import defaultdict


class Trie:
# Implement a trie with insert, search.

def __init__(self):
self.root = defaultdict()

def insert(self, word):
current = self.root
for letter in word:
current = current.setdefault(letter, {})
current.setdefault("_end")

def search(self, word):
current = self.root
for letter in word:
if letter not in current:
return False
current = current[letter]
if "_end" in current:
return True
return False

# these are the inner join and merge functions

def ijoin_util(root1, root2, str):

for k in root1:
if k == '_end':
ijoin_util.join.append(str)
return
found = root2.get(k)
if found != None:
ijoin_util(root1[k], found, str + k)


def inner_join(root1, root2):
str = ""
ijoin_util.join = []
ijoin_util(root1.root, root2.root, str)
return ijoin_util.join


def merge_util(root1, root2):
for k in root1:
found = root2.get(k)
if found != None:
merge_util(root1[k], found)
else:
root2.update({k: root1[k]})
return root2

def merge(root1, root2):
merge_util(root1.root, root2.root)



I know this is a really bad implementation for the problem, and I want to know if I can implement this in a way where I dont have to store the trie in the memory, (I mean like if I store it as RDD of nested maps), or any other approach which might help me scale it further

Continue reading...