Average case analysis for efficient spatial data structures

• US 8,417,708 B2
• Filed: 02/09/2009
• Issued: 04/09/2013
• Est. Priority Date: 02/09/2009
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Chidlovskii, Boris
• Primary Examiner(s): Beausoliel, Jr., Robert W.
• Assistant Examiner(s): Khakhar, Nirav K
• Application Number:
  US12/367,638
• Publication Number:
  US 20100205181A1
• Time in Patent Office: 1,520 Days
• Field of Search: 707/743
• US Class Current: 707/743
• CPC Class Codes: G06F 16/29 Geographical information databases

Abstract

A computer performed method models a spatial index having n spatial regions defined in a multidimensional space using a tree-based model representing an infinite number of arrangements of n spatial regions in the multidimensional space allowable by the spatial index using a finite number of tree representations, computes an average retrieval complexity measure for content retrieval using the spatial index based on the tree based model, and provides a spatial index recommendation based on the average retrieval complexity measure. In some embodiments a spatial index selection module selects the spatial index based on average retrieval complexity measures for candidate spatial indices that are functionally dependent upon a number of spatial regions to be defined by the spatial index.

Claims

1. A computer-performed method for recommending a spatial index for a spatial database, the method comprising:

modeling a spatial index type comprising partitioning and region-merging rules for defining n spatial regions in a multidimensional space, the modeling using a tree-based model that represents an infinite number of arrangements of n spatial regions in the multidimensional space allowable by the spatial index type by a finite number of tree representations;

computing an average retrieval complexity measure for content retrieval using the spatial index type based on the tree-based model; and

providing a recommendation of a spatial index type based on the average retrieval complexity measure.

2. The computer-performed method as set forth in claim 1, further comprising repeating the modeling and computing for a plurality of different spatial index types, the providing comprising:

recommending one of the plurality of different spatial index types for indexing the spatial database, the recommending being based on the average retrieval complexity measures computed for the plurality of different spatial index types.

3. The computer-performed method as set forth in claim 1, further comprising:

computing n based on a number of records in the spatial database and a bucket size b of the spatial index.

4. The computer-performed method as set forth in claim 3, wherein the modeling generates an average retrieval complexity formula functionally dependent upon the number of spatial regions and a data distribution, and the computing comprises:

computing the average retrieval complexity measure by evaluating the average retrieval complexity formula with the number of spatial regions set to the computed n.

5. The computer-performed method as set forth in claim 4, further comprising repeating the modeling and computing for a plurality of different spatial index types to generate an average retrieval complexity measure for each of the plurality of different spatial index types, the providing comprising:

recommending one of the plurality of different spatial index types for indexing the spatial database based on the average retrieval complexity measures.

6. The computer-performed method as set forth in claim 1, wherein the spatial index type comprises a nested interpolation-based grid spatial index type.

7. The computer-performed method as set forth in claim 6, wherein the computing an average retrieval complexity measure comprises:

determining an upper bound on the retrieval complexity measure; and

evaluating the upper bound to compute the average retrieval complexity measure.

8. The computer-performed method as set forth in claim 1, wherein the computing an average retrieval complexity measure comprises:

averaging the finite number of tree representations to generate an average tree representation; and

computing the average retrieval complexity measure for the average tree representation.

9. A non-transitory storage medium storing instruction executable by a digital electronic device to perform a method for assessing average retrieval complexity when using a selected spatial index that decomposes a multidimensional space into a selected number of spatial regions, the method comprising:

modeling an infinity of arrangements of the selected number of spatial regions which are allowed by the selected spatial index using a finite number of tree representations; and

computing an average retrieval complexity measure indicative of average retrieval complexity based on the tree-based model.

10. The non-transitory storage medium storing as set forth in claim 9, wherein the computing includes (i) averaging the finite number of tree representations to generate an average tree representation and (ii) computing an average retrieval complexity measure for content retrieval using the average tree representation.

11. The non-transitory storage medium as set forth in claim 9, wherein the storage medium further stores instructions executable by a digital electronic device to (i) invoke the method for assessing average retrieval complexity respective to a plurality of different selected spatial indices to computing average retrieval complexity measures for the different selected spatial indices and (ii) choose one of the different selected spatial indices for use in indexing a spatial database and (iii) associate a retrieval routine to the selected spatial index.

12. The non-transitory storage medium as set forth in claim 11, wherein the storage medium further stores instructions executable by a digital electronic device to (iv) construct a directory that indexes the spatial database using the chosen spatial index.

13. The non-transitory storage medium as set forth in claim 11, wherein the storage medium further stores instructions executable by a digital electronic device to select the number of spatial regions based on a number of records in the spatial database and a bucket size indicative of a maximum number of records allowable in a single spatial region.

14. The non-transitory storage medium as set forth in claim 11, wherein the plurality of different selected spatial indices include at least one spatial index selected from the group consisting of a quadtree index, and octree index, a UB-tree index, an R-tree index, a k-d tree index, and a nested interpolation-based grid (NIBG) index.

15. A spatial information system comprising:

a computer programmed to define;

an indexing module configured to construct a directory indexing records of a spatial database using a spatial index defining spatial regions whose indexing can be represented by nodes of a tree structure, and

a spatial index selection module configured to select a spatial index for use by the directory construction module based on average retrieval complexity measures for candidate spatial indices that are functionally dependent upon a number of spatial regions to be defined by the spatial index.

16. The spatial information system as set forth in claim 15, wherein the spatial index selection module is configured to compute the average retrieval complexity measures for the candidate spatial indices based on functions relating the average retrieval complexity measures for the candidate spatial indices to the number of spatial regions.

17. The spatial information system as set forth in claim 16, wherein the spatial index selection module is configured to compute the average retrieval complexity measure for each candidate spatial index by a method including (i) modeling an infinity of arrangements of the spatial regions allowed by the candidate spatial index using a finite number of tree representations, and (ii) determine the average retrieval complexity measure for the candidate spatial index based on the finite number of tree representations.

18. The spatial information system as set forth in claim 17, wherein the spatial index selection module is configured to perform the determination operation (ii) by averaging the finite number of tree representations to generate an average tree representation and determining the average retrieval complexity measure for the average tree representation.

19. The spatial information system as set forth in claim 15, wherein the spatial index selection module is configured to select a spatial index for use by the directory construction module from a plurality of candidate spatial indices including at least a nested interpolation-based grid spatial index.