Efficient database searching

• US 10,275,403 B2
• Filed: 10/20/2016
• Issued: 04/30/2019
• Est. Priority Date: 04/17/2013
• Status: Active Grant

• Current Assignee: R2 Solutions LLC (Acacia Research Corporation)
• Original Assignee: Excalibur IP, LLC (Acacia Research Corporation)
• Inventors: James, Rick
• Primary Examiner(s): Stevens, Robert
• Application Number:
  US15/298,477
• Publication Number:
  US 20170039243A1
• Time in Patent Office: 922 Days
• Field of Search: 707736
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/24554 Unary operations; Data partitioning operations
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

Systems and methods are disclosed for efficiently searching a database including a table. The table is partitioned along a first dimension, such as latitude. Indexes in each of the partitions are built along a second dimension, such as longitude. The table may also be clustered according to an index to improve performance. When a processor receives a database query term and a starting location, the processor selects, from the table, a data partition within a first offset to the starting location along the first dimension. The processor selects, from the selected data partition, a first number of first data records related to the query term and within a second offset to the starting location along the second dimension.

Claims

1. A system comprising:

a non-transitory storage medium configured to store a database, the database comprising;

a first data structure configured to store a first data object, the first data object comprising;

a first data object attribute relating the first data object to a first coordinate along a first geographic dimension;

a second data object attribute relating the first data object to a first coordinate in a second geographic dimension; and

a third data object attribute that includes identification information of the first data object; and

a second data structure configured to store a second data object, the second data object comprising;

an object identifier attribute that includes identification information matching the first data object; and

location based information related to at least one of the first coordinate along the first geographic dimension or the first coordinate in the second geographic dimension;

a processor configured to;

receive a query term and a starting geographic location associated with a query, the starting geographic location comprising a second coordinate in the first geographic dimension and a second coordinate in the second geographic dimension;

search a plurality of data objects included in the first data structure for the first data object based on similarity of the first coordinate in the first geographic dimension to the second coordinate in the first geographic dimension;

search a plurality of data objects included in the first data structure for the first data object based on similarity of the first coordinate in the second geographic dimension to the second coordinate in the second geographic dimension; and

select the first data object from the plurality of data objects based on the searches;

search the second data structure using the identification information of the first data object to select the second data object included in the second data structure based on the object identifier attribute that includes identification information matching the first data object; and

receive the location based information for the second data structure.

2. The system of claim 1, wherein the first data object is associated with a partition of the first data structure corresponding to a defined range of coordinate offsets along the first geographic dimension;

and

wherein the first data object further comprises a first primary key that combines the first data object attribute, the second data object attribute, and the third data object attribute.

3. The system of claim 2, wherein the first primary key is structured to store the first data object attribute such that the first data object from the first primary key is read before the second data object attribute and the third data object attribute.

4. The system of claim 1, wherein the first geographic dimension is one of a latitude dimension, a longitude dimension, or a distance from a reference location.

5. The system of claim 4, wherein the first geographic dimension is the longitude dimension.

6. The system of claim 1, wherein the first data structure is configured to store a plurality of data objects partitioned into defined ranges of coordinate offsets along the first geographic dimension, each data object including a unique corresponding first primary key.

7. The system of claim 1, wherein the location based information includes location based services for being displayed on a display screen.

8. A method comprising:

receiving, via a processor, a query term and a starting geographic location associated with a query, the starting geographic location comprising a second coordinate in a first geographic dimension and a second coordinate in a second geographic dimension;

searching, by the processor, a plurality of data objects included in a first data structure for a first data object based on a similarity of the second coordinate in the first geographic dimension to a first coordinate in the first geographic dimension and based on a similarity of the second coordinate in the second geographic dimension to a first coordinate in the second geographic dimension, wherein the first data structure includes;

a first data object attribute corresponding the first data object to the first coordinate along the first geographic dimension;

a second data object attribute corresponding the first data object to the first coordinate in the second geographic dimension; and

a third data object attribute that includes identification information of the first data object;

retrieving, by the processor, the identification information of the first data object from the first data structure based on the searching;

searching, by the processor, a second data structure using the identification information of the first data object to select a second data object included in the second data structure based on an object identifier attribute that includes identification information matching the identification information of the first data object, wherein the second data structure comprises;

the object identifier attribute that includes the identification information matching the first data object; and

location based information related to at least one of the first coordinate along the first geographic dimension or the first coordinate in the second geographic dimension, and

receiving, by the processor, the location based information for the second data structure.

9. The method of claim 8, wherein the first data object is associated with a partition of the first data structure corresponding to a defined range of coordinate offsets along the first geographic dimension;

and

wherein the first data object further comprises a first primary key that combines the first data object attribute, the second data object attribute, and the third data object attribute.

10. The method of claim 9, wherein the first primary key is structured to store the first data object attribute such that the first data object from the first primary key is read before the second data object attribute and the third data object attribute.

11. The method of claim 8, wherein the first geographic dimension is one of a latitude dimension, a longitude dimension, or a distance from a reference location.

12. The method of claim 11, wherein the first geographic dimension is the longitude dimension.

13. The method of claim 8, wherein the first data structure is configured to store a plurality of data objects partitioned into defined ranges of coordinate offsets along the first geographic dimension, each data object including a unique corresponding first primary key.

14. The method of claim 8, wherein the location based information includes location based services for being displayed on a display screen.

15. A computing device comprising:

a network interface in communication with a database, the network interface configured to;

receive, from a mobile device, a request to access a database comprising a first data structure and a second data structure, the request comprising a query term and a starting geographic location of the mobile device; and

a processor configured to;

control the network interface to communicate with the database;

parse a plurality of data objects that are included in the first data structure;

cause a selection of a first data object from the plurality of data objects identified by the starting geographic location, wherein the first data object comprises;

a first data object attribute corresponding the first data object to a first coordinate along a first geographic dimension;

a second data object attribute corresponding the first data object to a first coordinate in a second geographic dimension; and

a third data object attribute that includes identification information of the first data object; and

cause a selection of a second data object included in the second data structure in reference to the identification information of the first data object, wherein the second data object comprises;

an object identifier attribute that includes identification information matching the first data object; and

location based information related to at least one of the first coordinate along the first geographic dimension or the first coordinate in the second geographic dimension; and

receive the location based information.

16. The computing device of claim 15, wherein the first data object is associated with a partition of the first data structure corresponding to a defined range of coordinate offsets along the first geographic dimension, where the starting geographic location is within the partition of the first data structure;

and

wherein the first data object further comprises a first primary key that combines the first data object attribute, the second data object attribute, and the third data object attribute.

17. The computing device of claim 16, wherein the first primary key is structured to store the first data object attribute such that the first data object from the first primary key is read before the second data object attribute and the third data object attribute.

18. The computing device of claim 15, wherein the first geographic dimension is one of a latitude dimension, a longitude dimension, or a distance from a reference location.

19. The computing device of claim 18, wherein the first geographic dimension is the longitude dimension.

20. The computing device of claim 15, wherein the first data structure is configured to store a plurality of data objects partitioned into defined ranges of coordinate offsets along the first geographic dimension, each data object including a unique corresponding first primary key.