Two-dimensional indexes for quick multiple attribute search in a catalog system
US8219564B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Apr 29, 2008 |
| Grant date | Jul 10, 2012 |
| Priority date | — |
| Expiry date | Nov 4, 2029 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/901
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
Embodiments of the present invention provide mechanisms that overcome limitations of existing indexes by creating two-dimensional (2D) spatial indexes to quickly locate data containers that match two or more predicates. This is accomplished by representing metadata attributes describing a data container as dimensions in a 2D space so that a data container can be expressed as a point or a cell in a 2D space with coordinates being a pair of values of the selected attributes. A space filling curve is used to traverse the 2D space and convert each pair of the 2D coordinates to a single space filling curve value. A 2D spatial index is then created based on the computed space filling curve values so that one value can be associated with one or more points (data containers) in the index. Advantageously, the created spatial index provides for searching and processing fewer metadata entries, thereby decreasing the time typically used to search for data.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.