Efficient searching techniques
AssigneeArcot Systems, Inc.
InventorsSanguthevar Rajasekaran, Rajendra A. Gopalakrishna
Life of this patent
Estimating the term…
Abstract
The present invention describes techniques for performing searches in an efficient manner while minimizing the memory resources required to perform the searches. According to the techniques of the present invention, the number of comparisons needed to determine if a query element is in included in a set of elements is proportional to the length of the query element and independent of the number of elements in the set of elements.
Claims25
A computer-implemented method of determining if a query element is included in a set of elements comprising one or more elements from a first domain having a character set of “m” characters, wherein “Z” is the maximum possible length of an element in the first domain and “Y” is the length of the longest element in the set of elements such that 1≦Y≦Z, the method comprising:
- building a data structure based upon the set of elements, the data structure comprising a plurality of memory structures headed by a root memory structure, each memory structure in the plurality of memory structures comprising a first memory location and an array of “m” memory locations;
- receiving information identifying the query element;
- and
- using the data structure to determine if the query element is included in the set of elements such that the number of comparisons needed to determine if the query element is included in the set of elements is proportional to a length of the query element and independent of the number of elements in the set of elements.
A system for determining if a query element is included in a set of elements comprising one or more elements from a first domain having a character set of “m” characters, wherein “Z” is the maximum possible length of an element in the first domain and “Y” is the length of the longest element in the set of elements such that 1≦Y≦Z, the system comprising:
- a processor;
- a memory coupled to the processor, the memory configured to store a plurality of code modules executable by the processor, the plurality of code modules comprising:
- a code module for building a data structure based upon the set of elements, the data structure comprising a plurality of memory structures headed by a root memory structure, each memory structure in the plurality of memory structures comprising a first memory location and an array of “m” memory locations;
- a code module for receiving information identifying the query element;
- and
- a code module for using the data structure to determine if the query element is included in the set of elements such that the number of comparisons needed to determine if the query element is included in the set of elements is proportional to a length of the query element and independent of the number of elements in the set of elements.
A computer program product stored on a computer-readable storage medium for determining if a query element is included in a set of elements comprising one or more elements from a first domain having a character set of “m” characters, wherein “Z” is the maximum possible length of an element in the first domain and “Y” is the length of the longest element in the set of elements such that 1≦Y≦Z, the computer program product comprising:
- code for building a data structure based upon the set of elements, the data structure comprising a plurality of memory structures headed by a root memory structure, each memory structure in the plurality of memory structures comprising a first memory location and an array of “m” memory locations;
- code for receiving information identifying the query element;
- and
- code for using the data structure to determine if the query element is included in the set of elements such that the number of comparisons needed to determine if the query element is included in the set of elements is proportional to a length of the query element and independent of the number of elements in the set of elements.
Dependencies are inferred from the claim text.