<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
 Time series database & similarity searches
Gioia Dominedo
Nicolas Drizard
Kendrick Lo  
Persistence architecture
<img src='img/db_structure.png'>
Persistence demonstration
Initialize file system
Step1:  Initialize database
Step2:  Generate data
Step3:  Insert data
Step4:  Inspect data
Are all the entries there?
Step5:  Does the data match?
Step6:  Did the triggers work?
Step7:  Were the vantage points inserted?
Step8:  Terminate database
Step9:  Reload database
Step10:  ... once more, with feeling!
Are all the entries there?
Step11:  Does the data match?
Step12:  Were the vantage points re-loaded?
Step13:  Does the trigger still work?
Step14:  Terminate database
Step15:  Additional Feature
Step16:  Is there any data?
Step17:  What does it look like?
Step18:  Can we run a vantage point search?
Step19:  How do the stocks compare?
Step20:  Can we run an iSAX tree similarity search?
Step21:  How do the stocks compare?
Step22:  How do the methods compare?
Step23:  Show me another graph!
Step24:  What is an iSAX tree, really?
Step25:  Don't forget to close the server!
<ASSISTANT_TASK:>
Python Code:
# database parameters
ts_length = 100
data_dir = '../db_files'
db_name = 'default'
dir_path = data_dir + '/' + db_name + '/'
# clear file system for testing
if not os.path.exists(dir_path):
    os.makedirs(dir_path)
filelist = [dir_path + f for f in os.listdir(dir_path)]
for f in filelist:
    os.remove(f)
Explanation: Time series database & similarity searches
Gioia Dominedo
Nicolas Drizard
Kendrick Lo  
Persistence architecture
<img src='img/db_structure.png'>
Persistence demonstration
Initialize file system
End of explanation
# load the server
server = subprocess.Popen(['python', '../go_server_persistent.py',
                           '--ts_length', str(ts_length), '--data_dir', data_dir, '--db_name', db_name])
time.sleep(5)  # make sure it loads completely
# load the webserver
webserver = subprocess.Popen(['python', '../go_webserver.py'])
time.sleep(5)  # make sure it loads completely
# initialize the web interface
web_interface = WebInterface()
# check that the database is empty
web_interface.select()
Explanation: Initialize database
End of explanation
# generate sample time series
num_ts = 50
mus = np.random.uniform(low=0.0, high=1.0, size=num_ts)
sigs = np.random.uniform(low=0.05, high=0.4, size=num_ts)
jits = np.random.uniform(low=0.05, high=0.2, size=num_ts)
# initialize dictionaries for time series and their metadata
primary_keys = []
tsdict = {}
metadict = {}
# fill dictionaries with randomly generated entries for database
for i, m, s, j in zip(range(num_ts), mus, sigs, jits):
    meta, tsrs = tsmaker(m, s, j)  # generate data
    pk = "ts-{}".format(i)  # generate primary key
    primary_keys.append(pk) # keep track of all primary keys
    tsdict[pk] = tsrs  # store time series data
    metadict[pk] = meta  # store metadata
    
# to assist with later testing
ts_keys = sorted(tsdict.keys())
    
# randomly choose time series as vantage points
num_vps = 5
vpkeys = list(np.random.choice(ts_keys, size=num_vps, replace=False))
vpdist = ['d_vp_{}'.format(i) for i in vpkeys]
Explanation: Generate data
End of explanation
# add stats trigger
web_interface.add_trigger('stats', 'insert_ts', ['mean', 'std'], None)
# insert the time series
for k in tsdict:
    web_interface.insert_ts(k, tsdict[k])
    
# upsert the metadata
for k in tsdict:
    web_interface.upsert_meta(k, metadict[k])
    
# add the vantage points
for i in range(num_vps):
    web_interface.insert_vp(vpkeys[i])
Explanation: Insert data
End of explanation
# select all database entries; all metadata fields
results = web_interface.select(fields=[])
# we have the right number of database entries
assert len(results) == num_ts
# we have all the right primary keys
assert sorted(results.keys()) == ts_keys
Explanation: Inspect data
Are all the entries there?
End of explanation
# check that all the time series and metadata matches
for k in tsdict:
    results = web_interface.select(fields=['ts'], md={'pk': k})
    assert results[k]['ts'] == tsdict[k]
    results = web_interface.select(fields=[], md={'pk': k})
    for field in metadict[k]:
        assert metadict[k][field] == results[k][field]
Explanation: Does the data match?
End of explanation
# check that the trigger has executed as expected (allowing for rounding errors)
for k in tsdict:
    results = web_interface.select(fields=['mean', 'std'], md={'pk': k})
    assert np.round(results[k]['mean'], 4) == np.round(tsdict[k].mean(), 4)
    assert np.round(results[k]['std'], 4) == np.round(tsdict[k].std(), 4)
Explanation: Did the triggers work?
End of explanation
# check that the vantage points match
print('Vantage points selected:', vpkeys)
print('Vantage points in database:',
      web_interface.select(fields=None, md={'vp': True}, additional={'sort_by': '+pk'}).keys(), '\n')
# check that the vantage point distance fields have been created
results = web_interface.select(fields=vpdist, additional={'sort_by': '+pk', 'limit': 1})
print('Vantage point distance fields:', vpdist)
print('Vantage point distance example:')
print(results)
Explanation: Were the vantage points inserted?
End of explanation
os.kill(server.pid, signal.SIGINT)
time.sleep(5)  # give it time to terminate
os.kill(webserver.pid, signal.SIGINT)
time.sleep(5)  # give it time to terminate
web_interface = None
Explanation: Terminate database
End of explanation
server = subprocess.Popen(['python', '../go_server_persistent.py',
                           '--ts_length', str(ts_length), '--data_dir', data_dir, '--db_name', db_name])
time.sleep(5)  # give it time to load fully
webserver = subprocess.Popen(['python', '../go_webserver.py'])
time.sleep(5)  # give it time to load fully
web_interface = WebInterface()
Explanation: Reload database
End of explanation
# select all database entries; all metadata fields
results = web_interface.select(fields=[])
# we have the right number of database entries
assert len(results) == num_ts
# we have all the right primary keys
assert sorted(results.keys()) == ts_keys
Explanation: ... once more, with feeling!
Are all the entries there?
End of explanation
# check that all the time series and metadata matches
for k in tsdict:
    results = web_interface.select(fields=['ts'], md={'pk': k})
    assert results[k]['ts'] == tsdict[k]
    results = web_interface.select(fields=[], md={'pk': k})
    for field in metadict[k]:
        assert metadict[k][field] == results[k][field]
Explanation: Does the data match?
End of explanation
# check that the vantage points match
print('Vantage points selected:', vpkeys)
print('Vantage points in database:',
      web_interface.select(fields=None, md={'vp': True}, additional={'sort_by': '+pk'}).keys())
Explanation: Were the vantage points re-loaded?
End of explanation
# check that the trigger is still there by loading new data
# create test time series
_, test = tsmaker(np.random.uniform(low=0.0, high=1.0),
                  np.random.uniform(low=0.05, high=0.4),
                  np.random.uniform(low=0.05, high=0.2))
# insert test time series
web_interface.insert_ts('test', test)
# check that mean and standard deviation have been calculated
web_interface.select(fields=['mean', 'std'], md={'pk': 'test'})
Explanation: Does the trigger still work?
End of explanation
# terminate processes before exiting
os.kill(server.pid, signal.SIGINT)
time.sleep(5)  # give it time to terminate
web_interface = None
webserver.terminate()
Explanation: Terminate database
End of explanation
# load the database server
server = subprocess.Popen(['python', '../go_server_persistent.py',
                           '--ts_length', str(num_days), '--data_dir', '../db_files', '--db_name', 'stock_prices'])
time.sleep(5)  # make sure it loads completely
# load the database webserver
webserver = subprocess.Popen(['python', '../go_webserver.py'])
time.sleep(5)  # make sure it loads completely
# initialize the web interface
web_interface = WebInterface()
Explanation: Additional Feature:
iSAX Similarity Searches
Time series T of length n can be converted into a SAX representation
approximates T using a smaller number of segments (e.g. w=4)
each segment is represented by a discrete number
result is a SAX word (i.e. a vector) such as {11, 11, 01, 00}
<img src='img/slide1.png'>
SAX representation can be used as an index
e.g. fixed cardinality of 8, word length of 4
An example T may map to ${6^8, 6^8, 3^8, 0^8}$ 
data for all Ts that can be represented by this SAX word can be stored in the same text file on disk 
(e.g. with name 6.8_6.8_3.8_0.8.txt)
Problem: storage imbalance
Solution: introduce a threshold for the number of time series that can be stored in a single file
If an insertion would cause threshold to be exceeded, split the file
The diagram below illustrates an iSAX index as a tree
root node: represents complete SAX space
terminal node: leaf node containing pointer to file on disk
SAX word as index, contents are the actual time series data
internal node (new): designates split in SAX space
created when number of entries in a terminal node exceeds threshold
<img src='img/slide3.png'>
Observations:
binary splits are along one dimension (sequentially) 
creates two new words of increased cardinality
“new” node splitting policy (iSAX 2.0) purports to provide better balance by determining optimal dimension
checks whether mean value is close to a breakpoint
However:
balancing problems still exist
no justification given for binary splits
note that root is connected to multiple nodes
<img src='img/slide5.png'>
We implemented iSAX tree as a “true” n-ary tree
splits series in a “full” terminal node into up to ‘n’ terminal nodes all located at the same depth in the tree
achieves better balance, faster traversals
Class methods:
insert, delete, preorder (x2), similarity search (find_nbr)
Similarity search is “approximate”
intuition is that two similar time series are often  represented by the same iSAX word
natural clustering
“ties” broken by computing Euclidean distance (but only for neighbors)
adjust for sparser nodes by implementing search for series with common parent
<img src='img/slide7.png'>
Stock market example
Here's one we prepared earlier...
End of explanation
# number of stocks
len(web_interface.select())
Explanation: Is there any data?
End of explanation
# let's look at the first 10 stocks
web_interface.select(fields=['ts'], additional={'sort_by': '+pk', 'limit': 10})
Explanation: What does it look like?
End of explanation
# pick a stock
stock = np.random.choice(stocks_exclude)
print('Stock:', stock)
# run the vantage point similarity search
result = web_interface.vp_similarity_search(TimeSeries(range(num_days), stock_data_exclude[stock]), 1)
stock_match = list(result)[0]
stock_ts = web_interface.select(fields=['ts'], md={'pk': stock_match})[stock_match]['ts']
print('Most similar stock:', stock_match)
Explanation: Can we run a vantage point search?
End of explanation
# visualize similarity
plt.plot(stock_data_exclude[stock], label='Query:' + stock)
plt.plot(stock_ts.values(), label='Result:' + stock_match)
plt.xticks([])
plt.legend(loc='best')
plt.title('Daily Stock Price Similarity')
plt.show()
Explanation: How do the stocks compare?
End of explanation
# pick the stock
stock = np.random.choice(stocks_exclude)
print('Stock:', stock)
# run the isax tree similarity search
result = web_interface.isax_similarity_search(TimeSeries(range(num_days), stock_data_exclude[stock]))
if result == 'ERROR: NO_MATCH':
    print('Could not find a similar stock.')
else:
    stock_match = list(result)[0]
    stock_ts = web_interface.select(fields=['ts'], md={'pk': stock_match})[stock_match]['ts']
    print('Most similar stock:', stock_match)
Explanation: Can we run an iSAX tree similarity search?
End of explanation
# visualize similarity
plt.plot(stock_data_exclude[stock], label='Query:' + stock)
plt.plot(stock_ts.values(), label='Result:' + stock_match)
plt.xticks([])
plt.legend(loc='best')
plt.title('Daily Stock Price Similarity')
plt.show()
Explanation: How do the stocks compare?
End of explanation
# pick the stock
stock = np.random.choice(stocks_exclude)
print('Stock:', stock)
# run the vantage point similarity search
result = web_interface.vp_similarity_search(TimeSeries(range(num_days), stock_data_exclude[stock]), 1)
match_vp = list(result)[0]
ts_vp = web_interface.select(fields=['ts'], md={'pk': match_vp})[match_vp]['ts']
print('VP search result:', match_vp)
# run the isax similarity search
result = web_interface.isax_similarity_search(TimeSeries(range(num_days), stock_data_exclude[stock]))
if result == 'ERROR: NO_MATCH':
    print('iSAX search result: Could not find a similar stock.')
else:
    match_isax = list(result)[0]
    ts_isax = web_interface.select(fields=['ts'], md={'pk': match_isax})[match_isax]['ts']
    print('iSAX search result:', match_isax)
Explanation: How do the methods compare?
End of explanation
# visualize similarity
plt.plot(stock_data_exclude[stock], label='Query:' + stock)
plt.plot(ts_vp.values(), label='Result:' + match_vp)
plt.plot(ts_isax.values(), label='Result:' + match_isax)
plt.xticks([])
plt.legend(loc='best')
plt.title('Daily Stock Price Similarity')
plt.show()
Explanation: Show me another graph!
End of explanation
print(web_interface.isax_tree())
Explanation: What is an iSAX tree, really?
End of explanation
# terminate processes before exiting
os.kill(server.pid, signal.SIGINT)
time.sleep(5)  # give it time to terminate
web_interface = None
webserver.terminate()
Explanation: Don't forget to close the server!
End of explanation
<END_TASK>