Methods and apparatus for maintaining sets of ranges typically using an associative memory and for using these ranges to identify a matching range based on a query point or query range and to maintain sorted elements for use such as in providing priority queue operations
US7558775B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Jun 8, 2002 |
| Grant date | Jul 7, 2009 |
| Priority date | — |
| Expiry date | Feb 14, 2026 |
Classification
- Technology area (CPC H)Electricity
- CPC primaryH04L45/74591
- WIPO fieldDigital communication
- WIPO sectorElectrical engineering
Abstract
Sets of ranges typically are maintained using an associative memory and may be used to identify a matching range based on a query point or query range and to maintain sorted elements for use, such as in providing priority queue operations. In one implementation, ranges are added to a set of ranges by determining a longest common prefix of a starting point and an ending point of the range, extending this longest common prefix by appending a bit to create a particular extended longest common prefix, and then storing it in the set of extended longest common prefixes. The set of extended longest common prefixes is then processed based on the query point or range to identify the matching range. Additionally, one implementation uses bands for identifying ranges, where the band is formed from the starting and ending points to the longest common matching prefix of the these points.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.