SYSTEMS AND METHODS FOR INDEXING AND SEARCHING DATA RECORDS BASED ON DISTANCE METRICS

• US 20070192301A1
• Filed: 02/15/2007
• Published: 08/16/2007
• Est. Priority Date: 02/15/2006
• Status: Abandoned Application

• Current Assignee: Encirq Corporation (Ubiquitous AI Corp.)
• Original Assignee: Encirq Corporation (Ubiquitous AI Corp.)
• Inventors: Posner, David
• Application Number:
  US11/675,435
• Publication Number:
  US 20070192301A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

A computer implemented method for searching a data structure is disclosed. A first node on the data structure is examined. A determination is made as to whether the first node is associated with one or more child nodes. When the first node not associated with one or more child nodes, elements within the first node that are located within a defined distance away from a defined location rendered on the first node are identified. The identified elements are stored in a data set. The nodal radius cut-off value is updated if the value is less than a difference of one half a radius of the first node and a distance from the defined location to the center point of the first node. The first node is labeled to indicate that the node has been examined.

Claims

1. A computer implemented method for searching a data structure, comprising:

examining a first node on the data structure;

determining whether the first node is associated with one or more child nodes;

when the first node is not associated with one or more child nodes, identifying elements within the first node that are located within a defined distance away from a defined location rendered on the first node;

storing the identified elements in a data set;

updating a nodal radius cut-off value if the nodal radius cut-off value is less than a difference of one half a radius of the first node and a distance from the defined location to the center point of the first node; and

labeling the first node to indicate that the node has been examined.

2. The computer implemented method for searching a data structure, as recited in claim 1, further including,

when the first node is associated with one or more child nodes, determining a distance from a center point to a defined location for each of the child nodes;

sorting each of the child nodes into sequential order from shortest to longest distance;

identifying elements within the first node that are located within a defined distance away from the defined location;

storing the identified elements in a data set;

sequentially examining each of the child nodes that have not previously been examined and have areas that contain the defined location;

identify elements within each of the child nodes that are located within the defined distance away from the defined location;

storing the identified elements in the data set; and

labeling the first node and the examined child nodes to indicate that they have been examined.

3. The computer implemented method for searching a data structure, as recited in claim 1, wherein, the data structure is a proximity tree.

4. The computer implemented method for searching a data structure, as recited in claim 3, wherein the proximity tree is a finite directed acyclic graph (DAG).

5. The computer implemented method for searching a data structure, as recited in claim 1, wherein each of the child nodes associated with the first node has a center point that lies within a distance that is one half of the radius of the first node away from a center point of the first node.

6. The computer implemented method for searching a data structure, as recited in claim 1, wherein each element corresponds to a geographic location.

7. The computer implemented method for searching a data structure, as recited in claim 6, wherein the geographic location is a commercial entity.

8. The computer implemented method for searching a data structure, as recited in claim 1, wherein the search is conducted relative to the defined location.

10. The computer implemented method for inserting database records into a data structure, as recited in claim 3, further including:

when the first node is associated with one or more child nodes, identifying child nodes associated with the first node;

determining which of the identified child nodes have been split;

terminating the association of each of the split child nodes with the first node gathering elements stored within the terminated split child nodes;

examining each of the remaining child nodes associated with the first node to determine if a defined location lies within a circular area defined around each of the remaining child nodes; and

inserting the gathered elements into each of the remaining child nodes with circular areas that hold the defined location.

13. The computer implemented method for inserting database records into a data structure, as recited in claim 10, wherein each of the child nodes associated with the first node has a center point that lies within a distance that is one half of the first radius of the first node away from a center point of the first node.

16. The computer implemented method for inserting database records into a data structure, as recited in claim 10, wherein identical elements may be indexed into more than one child node.

9. A computer implemented method for inserting database records into a data structure, comprising:

determining whether a first node in the data structure is associated with one or more child nodes;

when the first node is not associated with one or more child nodes, inserting elements into the first node, wherein each element represents a geographic location; and

determining whether the number of elements in the first node exceeds a set number, wherein, if the number of elements in the first node does exceed the set number, replacing the first node with a set of nodes, wherein radii of the set of nodes measures one half a first radius of the first node, and redistributing the elements between each node of the set of nodes.

11. The computer implemented method for inserting database records into a data structure, as recited in claim 9, wherein, the data structure is a proximity tree.

12. The computer implemented method for inserting database records into a data structure, as recited in claim 11, wherein the proximity tree is a finite directed acyclic graph (DAG).

14. The computer implemented method for inserting database records into a data structure, as recited in claim 9, wherein each element corresponds to a geographic location.

15. The computer implemented method for inserting database records into a data structure, as recited in claim 14, wherein the geographic location is a commercial entity.

17. A data tree structure for storing a dataset to be indexed and searched based on distance criteria, comprising:

a root node defined by a root node center point and a root node radius, the root node configured to store elements that comprise the dataset; and

a first sub-node associated with the root node, the first sub-node defined by a first sub-node center point and a first sub-node radius, wherein the first sub-node center point lies within one half the root node radius away from the root node center point and is configured to store a portion of the elements that comprise the dataset.

18. The data tree structure for storing a dataset to be indexed and searched based on distance criteria, as recited in claim 17, wherein each element corresponds to a unique geographical location.

19. The data tree structure for storing a dataset to be indexed and searched based on distance criteria, as recited in claim 18, wherein the unique geographic location is a commercial entity.

20. The data tree structure for storing a dataset to be indexed and searched based on distance criteria, as recited in claim 17, wherein every path from the root node to the first sub-node has the same length.

21. The data tree structure for storing a dataset to be indexed and searched based on distance criteria, as recited in claim 17, wherein the first sub-node is configured to be associated with one or more child nodes.

22. The data tree structure for storing a dataset to be indexed and searched based on distance criteria, as recited in claim 17, wherein, the data structure is a proximity tree.

23. The data tree structure for storing a dataset to be indexed and searched based on distance criteria, as recited in claim 22, wherein the proximity tree is a finite directed acyclic graph (DAG).