Patent ID: 6868420
Filing Date: 2005-03-15
Classification: G06F,Y10S

Abstract:
1. A method for traversing a bi-tree stored in a memory to locate application specific data stored in the memory and associated with the bi-tree, wherein the bi-tree comprises a spatial partitioning of an N-dimensional space into a hierarchy of cells, wherein each cell, starting from a root cell enclosing the N-dimensional space, is successively and conditionally partitioned into 2 N child cells along N mid-planes of the cell, and wherein each cell has associated characteristics comprising the application specific data and child cells are indexed directly from a parent cell, comprising: specifying a set of locational codes; specifying a cell; testing whether the characteristics of the cell satisfy a termination condition and applying only an arithmetic operation on the set of locational codes to directly index a next cell to be tested while false; and otherwise identifying the cell as a target cell if true; and retrieving the application specific data of the target cell from the memory.