hexogen / kdtree

PHP K-D Tree implementation with file system binary index

K-D Tree

PHP multidimensional K-D Tree implementation.

To receive all benefits from K-D Tree, use file system implementation(FSKDTree). FSKDTree stores tree in binary format and uses lazy loading while traversing through nodes. Current approach provides much higher performance compared to deserialization.

Install

Via Composer

$ composer require hexogen/kdtree

Usage

Tree creation

//Item container with 2 dimensional points
$itemList = new ItemList(2);

//Adding 2 - dimension items to the list
$itemList->addItem(new Item(1, [1.2, 4.3]));
$itemList->addItem(new Item(2, [1.3, 3.4]));
$itemList->addItem(new Item(3, [4.5, 1.2]));
$itemList->addItem(new Item(4, [5.2, 3.5]));
$itemList->addItem(new Item(5, [2.1, 3.6]));

//Building tree with given item list
$tree = new KDTree($itemList);

Searching nearest items to the given point

//Creating search engine with custom algorithm (currently Nearest Search)
$searcher = new NearestSearch($tree);

//Retrieving a result ItemInterface[] array with given size (currently 2)
$result = $searcher->search(new Point([1.25, 3.5]), 2);

echo $result[0]->getId(); // 2
echo $result[0]->getNthDimension(0); // 1.3
echo $result[0]->getNthDimension(1); // 3.4

echo $result[1]->getId(); // 1
echo $result[1]->getNthDimension(0); // 1.2
echo $result[1]->getNthDimension(1); // 4.3

Persist tree to a binary file

//Init tree writer
$persister = new FSTreePersister('/path/to/dir');

//Save the tree to /path/to/dir/treeName.bin
$persister->convert($tree, 'treeName.bin');

File system version of the tree

//ItemInterface factory
$itemFactory = new ItemFactory();

//Then init new instance of file system version of the tree
$fsTree = new FSKDTree('/path/to/dir/treeName.bin', $itemFactory);

//Now use fs kdtree to search
$fsSearcher = new NearestSearch($fsTree);

//Retrieving a result ItemInterface[] array with given size (currently 2)
$result = $fsSearcher->search(new Point([1.25, 3.5]), 2);

echo $result[0]->getId(); // 2
echo $result[1]->getId(); // 1

Change log

Please see CHANGELOG for more information on what has changed recently.

Testing

$ composer test

Contributing

Please see CONTRIBUTING and CONDUCT for details.

Security

If you discover any security related issues, please email [email protected] instead of using the issue tracker.

Credits

• Volodymyr Basarab
• All Contributors

License

The MIT License (MIT). Please see License File for more information.

kdtree's Issues

Updating/Avoiding to load the entire tree into RAM

I'm wondering if I could use this implementation to efficiently store OpenAI embedding vectors for my documents. However from what I understand from the documentation, it seems the tree has to be built completely in RAM first, before it can be persisted to the filesystem and then more efficiently be searched. It also seems a already created tree can't be updated/extended.

Would it be feasible to implement updating/extending the tree on disk?

php ^8.1 support

Can you please make a new release with php v8.1 support. Thanks in advance!