Method and apparatus for multidimensional data storage and file system with a dynamic ordered tree structure

• US 9,589,006 B2
• Filed: 11/26/2014
• Issued: 03/07/2017
• Est. Priority Date: 06/29/2012
• Status: Expired due to Fees

• Current Assignee: Nokia Technologies Oy (Nokia Corporation)
• Original Assignee: Nokia Technologies Oy (Nokia Corporation)
• Inventors: Boldyrev, Sergey, Kalra, Pavandeep
• Primary Examiner(s): Cao, Phuong Thao
• Application Number:
  US14/555,027
• Publication Number:
  US 20150154239A1
• Time in Patent Office: 832 Days
• Field of Search: 707/741
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2264 Multidimensional index structures
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

An approach is provided to determine one or more dynamic ordered tree structures and transition tree structures (e.g., based on one or more transitions of a device) to facilitate querying and/or accessing data stores. An apparatus and method determines to generate at least one index structure, determines to associate index objects of the generated index structure with one or more data objects of at least one data store, determines to generate at least one transition index structure based on the at least one generated index structure, and determines to associate the transition index structure with index objects corresponding to one or more data objects of at least one data store based on a transition of a device. Also, the method and apparatus determines to generate at least one query, and determines to generate at least one transition index structure where a current index structure to resolve the query is absent.

Claims

1. A method comprising:

in response to one or more changes of context associated with a device, a user of the device, or a combination thereof, generating, by an apparatus, at least one transition index structure via projecting a transition of the device into at least one index structure, wherein the context includes one or more user trip characteristics and locations, and the transition of the device includes the one or more changes of the context;

associating, by the apparatus, the at least one transition index structure with one or more index objects corresponding to a sub-set of spatially related data objects associated with the at least one index structure, one or more other data objects, or a combination thereof and

in response to a query for one or more of the spatially related data objects, searching, by the apparatus, via the at least one transition index structure to resolve the query.

2. The method of claim 1, further comprising:

synchronizing a storage of the device with a data store; and

as part of the synchronizing, receiving, at the device via a network, the sub-set of the spatially related data objects, the spatially related data objects, the one or more other data objects, the at least one index structure, the at least one transition index structure, or a combination thereof.

3. The method of claim 1, wherein the at least one index structure, the at least one transition index structure, or a combination thereof, are generated at the device, and the method further comprising:

synchronizing a storage of the device with a data store; and

as part of the synchronizing, transmitting from the device the at least one index structure, the at least one transition index structure, or a combination thereof, to the data store via a network.

4. The method of claim 3, wherein the data store is formed over a plurality of nodes of the network.

5. The method of claim 1, further comprising:

caching, at a storage of the device, the sub-set of the spatially related data objects, the spatially related data objects, the one or more other data objects, the at least one index structure, the at least one transition index structure, or a combination thereof,

wherein at least one of the generating step, the associating step, and the searching step, is performed at the device.

6. The method of claim 5, wherein each of the one or more index objects includes a pointer for retrieving a corresponding one of the one or more of the spatially related data objects from a data store, the storage of the device, or a combination thereof.

7. The method of claim 1, wherein the at least one index structure and the at least one transition index structure are each a multidimensional tree structure, and the one or more index objects are nodes of the multidimensional tree structure.

8. The method of claim 7, wherein the multidimensional tree structure is an R-tree and the one or more index objects comprise map tiles.

9. An apparatus comprising:

at least one processor; and

at least one memory including computer program code for one or more programs, the at least one memory and the computer program code configured to, with the at least one processor, cause the apparatus to perform at least the following;

in response to one or more changes of context associated with a device, a user of the device, or a combination thereof, generate at least one transition index structure via projecting a transition of the device into at least one index structure, wherein the context includes one or more user trip characteristics and locations, and the transition of the device includes the one or more changes of the context;

associate the at least one transition index structure with one or more index objects corresponding to a sub-set of spatially related data objects associated with the at least one index structure, one or more other data objects, or a combination thereof; and

in response to a query for one or more of the spatially related data objects, search via the at least one transition index structure to resolve the query.

10. The apparatus of claim 9, wherein the apparatus is further caused to:

synchronize a storage of the device with a data store; and

as part of the synchronizing, receive, at the device via a network, the sub-set of the spatially related data objects, the spatially related data objects, the one or more other data objects, the at least one index structure, the at least one transition index structure, or a combination thereof.

11. The apparatus of claim 9, wherein the at least one index structure, the at least one transition index structure, or a combination thereof, are generated at the device, and the method further comprising:

synchronize a storage of the device with a data store; and

as part of the synchronizing, transmit from the device the at least one index structure, the at least one transition index structure, or a combination thereof, to the data store via a network.

12. The apparatus of claim 11, wherein the data store is formed over a plurality of nodes of the network.

13. The apparatus of claim 9, wherein the apparatus is further caused to:

cache, at a storage of the device, the sub-set of the spatially related data objects, the spatially related data objects, the one or more other data objects, the at least one index structure, the at least one transition index structure, or a combination thereof,

wherein at least one of the generating, the associating, and the searching, is performed at the device.

14. The apparatus of claim 13, wherein each of the one or more index objects includes a pointer for retrieving a corresponding one of the one or more of the spatially related data objects from a data store, the storage of the device, or a combination thereof.

15. The apparatus of claim 9, wherein the at least one index structure and the at least one transition index structure are each a multidimensional tree structure, and the one or more index objects are nodes of the multidimensional tree structure.

16. The apparatus of claim 15, wherein the multidimensional tree structure is an R-tree and the one or more index objects comprise map tiles.

17. A non-transitory computer-readable storage medium carrying one or more sequences of one or more instructions which, when executed by one or more processors, cause an apparatus to at least perform the following steps:

in response to one or more changes of context associated with a device, a user of the device, or a combination thereof, generating at least one transition index structure via proj ecting a transition of the device into at least one index structure, wherein the context includes one or more user trip characteristics and locations, and the transition of the device includes the one or more changes of the context;

associating the at least one transition index structure with one or more index objects corresponding to a sub-set of spatially related data objects associated with the at least one index structure, one or more other data objects, or a combination thereof; and

in response to a query for one or more of the spatially related data objects, searching via the at least one transition index structure to resolve the query.

18. The non-transitory computer-readable storage medium of claim 17, wherein the apparatus is caused to further perform:

synchronizing a storage of the device with a data store; and

as part of the synchronizing, receiving, at the device via a network, the sub-set of the spatially related data objects, the spatially related data objects, the one or more other data objects, the at least one index structure, the at least one transition index structure, or a combination thereof.

19. The non-transitory computer-readable storage medium of claim 17, wherein the at least one index structure, the at least one transition index structure, or a combination thereof, are generated at the device, and the apparatus is caused to further perform:

synchronizing a storage of the device with a data store; and

as part of the synchronizing, transmitting from the device the at least one index structure, the at least one transition index structure, or a combination thereof, to the data store via a network.

20. The non-transitory computer-readable storage medium of claim 19, wherein the data store is formed over a plurality of nodes of the network.