Resizable Spatial Index
Publication Date: 2010-Dec-20
The IP.com Prior Art Database
Disclosed is a method of modifying existing algorithms and data structures used for storing spaces such that space modifying operations including shrinking and expanding can be performed in logarithmic time to the number of locations indexed in the space, an enormous improvement of the standard linear time. The modification does not impede on the speed or memory performance of existing algorithms on the standard set of operations such as insertion, removal and searching, and as such can be applied to existing products and solutions with no negative side-effect.
Page 01 of 5
Resizable Spatial Index
It is often desirable to index the locations of items in a given space. However, if the size of the indexed space changes by stretching or shrinking at any arbitrary point then the locations of all indexed items must be updated. An example is a program that highlights sections of text in a book. Each highlight must be stored so that the program can know what characters to highlight. Pages or paragraphs may be inserted into to the book at any point, the character ranges of the highlights after the point the text was inserted must be increased by the length of the text so the program continues to highlight the same text. So if the program was highlighting the character ranges (10 to 15), (15 to 50), (43 to 53), (50 to 55) and then an paragraph of 100 characters was inserted at the 40th character, the highlight ranges would need to be changed to (10 to 15), (15 to 40), (143 to 153), (150 to 155).
Current techniques of spatial indexing such as R-trees, binary sorted trees and interval-trees require O(n) complexity for stretch operation, as each location after the insertion point must be updated. This is far too slow for indexes that may contain millions or billions of items.
Industries that deal with location indexes that would benefit from a solution to this problem include Geographic information systems, Database systems and Gaming.
Current solutions for spatial indexing such as R-trees, binary sorted trees and interval-trees index locations with their absolute positions. However by modifying these solutions so they instead store the locations as a relative position from each other we only need to update a sub-set of locations. If a binary sorted trees is modified such that each node stores its position relative to its parents position, then only one branch of the tree needs to be modified when the space is stretched or shrunk at any point. As only a single branch is updated the operation is O(logn) complexity, a significant improvement.
In the attached image is a binary sorted tree containing the numbers 1, 5, 6, 10, 13, 20, 21. The tree is presented in two forms, the traditional absolute value form, and the relative value form presented in this disclosure. A stretch operation is performed on both trees, stretching at the location 2 with a value of 4, so the resulting trees will contain the values 1, 9, 10, 14, 17, 24, 25. The nodes highlighted in red in the stretched trees are the nodes that were checked for a required update during the operation. As each node in a traditional absolute binary search tree with a value greater than the stretch point needs to be updated, and the stretch point in the tree needs to be found, every node in the tree needs to be checked. However in the relative tree, only the branch of the tree which would contain the stretch point needs to be checked
Page 02 of 5
(This page contains 00 pictures or other non-text object)
Many areas in the IT industry deal with the storage and re...