Поиск с помощью HDF5

Question

Я пытаюсь выполнить поиск больших данных с ограниченной памятью.

Я использую HDF5 и Python.

Я попробовал линейный поиск грубой силы (используя pytables) и поиск по дереву kd (используя sklearn)

Удивительно, но метод kd-дерева занимает больше времени (может быть, kd-tree будет работать лучше, если мы увеличим размер пакета? Но я не знаю оптимальный размер и он ограничен памятью)

Сейчас я ищу способ ускорить вычисления, я думаю, что файл HDF5 можно настроить для отдельного ПК, также можно ускорить вычисление нормы, возможно, с помощью nymexpr или некоторых приемов Python.

import numpy as np
import time
import tables
import cProfile

from sklearn.neighbors import NearestNeighbors

rows = 10000
cols = 1000
batches = 100
k= 10

#USING HDF5
vec= np.random.rand(1,cols)
data = np.random.rand(rows,cols)
fileName = 'C:\carray1.h5'
shape = (rows*batches, cols)  # predefined size
atom = tables.UInt8Atom()  #?
filters = tables.Filters(complevel=5, complib='zlib') #?

#create
# h5f = tables.open_file(fileName, 'w')
# ca = h5f.create_carray(h5f.root, 'carray', atom, shape, filters=filters)

# for i in range(batches):
    # ca[i*rows:(i+1)*rows]= data[:]+i  # +i to modify data

# h5f.close()

#can be parallel?
def test_bruteforce_knn():
    h5f = tables.open_file(fileName)

    t0= time.time()
    d = np.empty((rows*batches,))
    for i in range(batches):
        d[i*rows:(i+1)*rows] = ((h5f.root.carray[i*rows:(i+1)*rows]-vec)**2).sum(axis=1)
    print (time.time()-t0)
    ndx = d.argsort()
    print ndx[:k]

    h5f.close()

def test_tree_knn():
    h5f = tables.open_file(fileName)

        # it will not work
    # t0= time.time()
    # nbrs = NearestNeighbors(n_neighbors=k, algorithm='ball_tree').fit(h5f.root.carray)
    # distances, indices = nbrs.kneighbors(vec)
    # print (time.time()-t0)

        #need to concatenate distances, indices somehow 
    t0= time.time()
    d = np.empty((rows*batches,))
    for i in range(batches):
        nbrs = NearestNeighbors(n_neighbors=k, algorithm='ball_tree').fit(h5f.root.carray[i*rows:(i+1)*rows])
        distances, indices = nbrs.kneighbors(vec)  # put in dict? 
        #d[i*rows:(i+1)*rows] = 
    print (time.time()-t0)
    #ndx = d.argsort()
    #print ndx[:k]

    h5f.close()

cProfile.run('test_bruteforce_knn()')
cProfile.run('test_tree_knn()')

Answer 1

Если я правильно понимаю, ваши данные имеют 1000 измерений? Если это так, то ожидается, что kd-дерево не будет хорошо, так как оно страдает от проклятия размерности.

Возможно, вы захотите взглянуть на методы поиска Приблизительные ближайшие соседи. Например, посмотрите на Флан.