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

• US 8,930,374 B2
• Filed: 06/29/2012
• Issued: 01/06/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
• Primary Examiner(s): Cao, Phuong Thao
• Application Number:
  US13/538,613
• Publication Number:
  US 20140006411A1
• Time in Patent Office: 921 Days
• Field of Search: 707/741, 707/999.102, 707/E17.002, 707/E17.044
• US Class Current: 707/741
• 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:

generating, by a processor, at least one index structure;

associating, by the processor, one or more index objects of the at least one generated index structure with one or more data objects of at least one data store, wherein the one or more data objects are spatially related;

generating, by the processor, at least one transition index structure via projecting a transition of a device into the at least one generated index structure, wherein the transition of the device is projected based, at least in part, on context associated with the device, a user of the device, or a combination thereof, wherein the context includes one or more user trip characteristics in addition to locations, and the at least one transition index structure is generated by the processor in response to one or more changes of the context and without user interaction with the device;

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

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

2. The method of claim 1, wherein the one or more trip characteristics include business, and

the transition of the device excludes user interaction with the device and includes one or more location changes of the device, a user of the device, or a combination thereof.

3. The method of claim 2, 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 at least one data store, and wherein the at least one generated 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.

4. The method of claim 3, wherein the multidimensional tree structure is an R-tree and the index objects comprise map tiles.

5. The method of claim 1, further comprising:

generating one or more state trajectories for the at least one transition index structure based, at least in part, on the sub-set of the one or more data objects, the one or more other data objects, or a combination thereof, wherein the one or more state trajectories include work, leisure, home, business trip, or a combination thereof.

6. The method of claim 5, further comprising:

reducing states of the one or more state trajectories based one or more criteria; and

traversing the reduced one or more state trajectories for resolving the query.

7. The method of claim 6, further comprising:

observing a history of index objects for the at least one generated index structure to determine the at least one transition index structure,

wherein the one or more criteria include resolution.

8. The method of claim 7, further comprising:

extracting at least one pattern of the one or more index objects, at least one sequence of the one or more index objects, or a combination thereof, to determine the at least one transition index structure.

9. The method of claim 1, further comprising:

causing, at least in part, storage of the at least one index structure, the at least one transition index structure, or a combination thereof, to generate a further transition index structure based on a further transition.

10. The method of claim 1, wherein the transition or further transition is triggered by the one or more changes of the context that include a change in a status, a location, a criteria of the user of the device or a service provider for the device, or a combination thereof.

11. 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;

generate at least one index structure;

associate one or more index objects of the at least one generated index structure with one or more data objects of at least one data store, wherein the one or more data objects are spatially related;

generate at least one transition index structure via projecting a transition of a device into the at least one generated index structure, wherein the transition of the device is projected based, at least in part, on context associated with the device, a user of the device, or a combination thereof, wherein the context includes one or more user trip characteristics in addition to locations, and the at least one transition index structure is generated by the at least one processor in response to one or more changes of the context and without user interaction with the device;

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

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

12. The apparatus of claim 11, wherein the transition of the device excludes user interaction with the device and includes one or more location changes of the device, a user of the device, or a combination thereof.

13. The apparatus of claim 12, wherein the at least one generated 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.

14. The apparatus of claim 13, wherein the multidimensional tree structure is an R-tree and the index objects comprise map tiles.

15. The apparatus of claim 11, wherein the apparatus is further caused to:

generate one or more state trajectories for the at least one transition index structure.

16. The apparatus of claim 15, wherein the apparatus is further caused to:

reduce states of the one or more state trajectories for the at least one transition index structure.

17. The apparatus of claim 16, wherein the apparatus is further caused to:

observe a history of index objects for the at least one generated index structure to determine the at least one transition index structure.

18. The apparatus of claim 17, wherein the apparatus is further caused to:

extract at least one pattern of the one or more index objects, at least one sequence of the one or more index objects, or a combination thereof, to determine the at least one transition index structure.

19. The apparatus of claim 11, wherein the apparatus is further caused to:

cause, at least in part, storage of the at least one index structure, the at least one transition index structure, or a combination thereof, to generate a further transition index structure based on a further transition.

20. The apparatus of claim 11, wherein the transition or further transition is triggered by a change in a status, a location, a criteria of a user of the device or a service provider for the device, or a combination thereof.