METHOD AND APPARATUS FOR MULTIDIMENSIONAL DATA STORAGE AND FILE SYSTEM WITH A DYNAMIC ORDERED TREE STRUCTURE

• US 20150154239A1
• Filed: 11/26/2014
• Published: 06/04/2015
• Est. Priority Date: 06/29/2012
• Status: Active Grant

• Current Assignee: Nokia Technologies Oy (Nokia Corporation)
• Original Assignee: Nokia Corporation
• Inventors: BOLDYREV, Sergey, KALRA, Pavandeep
• Granted Patent: US 9,589,006 B2
• Time in Patent Office: Days
• 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 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 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 data objects, searching via the at least one transition index structure to resolve the query.

2. A 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 data objects, the 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. A 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. A method of claim 3, wherein the data store is formed over a plurality of nodes of the network.

5. A method of claim 1, further comprising:

caching, at a storage of the device, the sub-set of the data objects, the 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 user device.

6. A 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 data objects from the data store, the storage of the device, or a combination thereof.

7. A 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 structures.

8. A method of claim 7, wherein the multidimensional tree structure is an R-tree and the 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 data objects, search via the at least one transition index structure to resolve the query.

10. An 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 data objects, the 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. An 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. An apparatus of claim 11, wherein the data store is formed over a plurality of nodes of the network.

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

cache, at a storage of the device, the sub-set of the data objects, the 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 user device.

14. An 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 data objects from the data store, the storage of the device, or a combination thereof.

15. An 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 structures.

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

17. A 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 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 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 data objects, searching via the at least one transition index structure to resolve the query.

18. A 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 data objects, the 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. A 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. A computer-readable storage medium of claim 19, wherein the data store is formed over a plurality of nodes of the network.