Granted Patent B2

US 9,396,276 · App. 14/871,397 · Granted Jul 19, 2016

Abstract

Claims (69)

1. A method for generating a response to a query by a computer user to search a set of electronic point-of-interest records, wherein each electronic point-of-interest record contains a plurality of tokens, the method comprising:

generating, by a computing device, a geo-search query index based on the set of electronic point-of-interest records in a key-value database, wherein the geo-search query index comprises:

a plurality of key-value pairs, each key-value pair comprising a key and one or more electronic point-of-interest record reference values, each electronic point-of-interest record reference value indicating a corresponding electronic point-of-interest record,

each key comprising at least one expected query randomly generated from the tokens contained in the electronic point-of-interest records corresponding to the electronic point-of-interest record reference values, wherein the tokens of the at least one expected query are ordered by token frequency, and

wherein the one or more electronic point-of-interest record reference values of each key are ordered by decreasing relevance of the corresponding electronic point-of-interest records to the expected query of the key;

parsing, by the computing device, the query into one or more query tokens;

generating, by the computing device, an ordered query from the query tokens, the one or more query tokens ordered by increasing frequency within the set of electronic point-of-interest records;

matching, by the computing device, the ordered query to an expected query in a key-value pair in the geo-search query index; and

providing, by the computing device, the electronic point-of-interest record reference values from the matching key value pair.

2. The method of claim 1 , wherein matching, by the computing device, the ordered query to an expected query in a key-value pair in the geo-search query index further comprises the steps of:

executing a scan function on the geo-search query index, wherein the scan function receives the ordered query as an input, and wherein the scan function outputs a first key in the geo-search query index that follows in lexicographical order the ordered query.

3. The method of claim 1 , wherein matching, by the computing device, the ordered query to an expected query in a key-value pair in the geo-search query index further comprises the steps of:

executing a scan function on the geo-search query index, wherein the scan function receives the ordered query as an input, and wherein the scan function outputs a first key in the geo-search query index that follows in lexicographical order the ordered query;

retrieving a first value associated with the first key in the geo-search query index, wherein the first value comprises a second set of key-value pairs, wherein key-value pairs in the second set of key-value pairs comprise a key comprising an ordered query and a value comprising one or more electronic point-of-interest record references responsive to the query by the computer user; and

providing, by the computing device, the electronic point-of-interest record reference values from the matching key value pair further comprises:

retrieving a second value associated with the ordered query received by the scan function from the second set of key-value pairs.

4. The method of claim 1 , wherein each of the at least one expected query in each key-value pair comprises one or more tokens, the method further comprising generating the at least one expected query using a Monte Carlo simulation for each of a plurality of query lengths, based on frequencies of the tokens in the electronic point-of-interest records corresponding to the electronic point-of-interest record references values in the key-value pair.

5. The method of claim 4 , further comprising combining similar key-value pairs having similar ordered expected queries in the geo-search query index to form query-reference pairs, each query-reference pair comprising the tokens of the similar expected queries as the query, and the electronic point-of-interest record reference values from the similar key-value pairs as the reference in the query-reference pair.

6. An apparatus for generating a response to a query by a computer user to search a set of electronic point-of-interest records, the apparatus comprising:

at least one processor;

a network interface; and

a memory comprising instructions that, when executed, perform the steps of:

generating, by a computing device, a geo-search query index for a set of electronic point-of-interest records in a key-value database, wherein the geo-search query index comprises

a plurality of key-value pairs, each key-value pair comprising a key and one or more electronic point-of-interest record reference values,

each electronic point-of-interest record reference value indicating a corresponding electronic point-of-interest record,

each key comprising at least one expected query randomly generated from the tokens contained in the electronic point-of-interest records corresponding to the electronic point-of-interest record reference values, wherein the tokens of the at least one expected query are ordered by token frequency, and

wherein the one or more electronic point-of-interest record reference values of each key are ordered by decreasing relevance of the corresponding electronic point-of-interest records to the expected query of the key;

parsing, by the computing device, the query into at least one query token;

generating, by the computing device, an ordered query from the query tokens, the query tokens ordered by increasing frequency within the set of electronic point-of-interest records;

matching, by the computing device, the ordered query to an expected query in a key-value pair in the geo-search query index; and

providing, by the computing device, the electronic point-of-interest record reference values from the matching key value pair.

7. The apparatus of claim 6 , wherein the instructions that, when executed, perform the step of matching, by the computing device, the ordered query to an expected query in a key-value pair in the geo-search query index further comprise instructions that, when executed, perform the steps of:

executing a scan function on the geo-search query index, wherein the scan function receives the ordered query as an input, and wherein the scan function outputs a first key in the geo-search query index that follows in lexicographical order the ordered query.

8. The apparatus of claim 6 , wherein matching, by the computing device, the ordered query to an expected query in a key-value pair in the geo-search query index further comprise instructions that, when executed, perform the steps of:

executing a scan function on the geo-search query index, wherein the scan function receives the ordered query as an input, and wherein the scan function outputs a first key in the geo-search query index that follows in lexicographical order the ordered query;

retrieving a first value associated with the first key in the geo-search query index, wherein the first value comprises a second set of key-value pairs, wherein key-value pairs in the second set of key-value pairs comprise a key comprising an ordered query and a value comprising one or more electronic point-of-interest record references responsive to the query by the computer user; and

providing, by the computing device, the electronic point-of-interest record reference values from the matching key value pair further comprises:

retrieving a second value associated with the ordered query received by the scan function from the second set of key-value pairs.

9. The apparatus of claim 6 , wherein each the at least one expected query in each key-value pair comprises one or more tokens, and the instructions that, when executed, generate the expected queries using a Monte Carlo simulation for each of a plurality of query lengths, based on frequencies of the tokens in the electronic point-of-interest records corresponding to the electronic point-of-interest record references values in the key-value pair.

10. The apparatus of claim 9 , wherein the instructions that, when executed, perform the step of combining similar key-value pairs having similar ordered expected queries in the geo-search query index to form query-reference pairs, each query-reference pair comprising the tokens of the similar expected queries as the query, and the electronic point-of-interest record reference values from the similar key-value pairs as the reference in the query-reference pair.

11. A computer-executed method for creating a geo-search query index configured to store electronic point-of-interest record references to a plurality of electronic point-of-interest records, wherein each electronic point-of-interest record contains a plurality of tokens, the method comprising:

for each of the plurality of electronic point-of-interest records in a key-value database:

randomly generating, by the computing device, a first plurality of expected queries for the electronic point-of-interest record by randomly selecting tokens in the electronic point-of-interest record based at least in part on frequencies of the tokens in the electronic point-of-interest record;

determining, by the computing device, relevance of each expected query to the electronic point-of-interest record;

selecting, by the computing device, a second plurality of most relevant expected queries for the electronic point-of-interest record as a subset of the first plurality of expected queries for the electronic point-of-interest record based at least in part on the relevance of the tokens in each expected query to that electronic point-of-interest record and to the plurality of electronic point-of-interest records; and

for each of the expected queries generated from the plurality of electronic point-of-interest records:

ordering, by the computing device, the tokens in the expected query by decreasing relevance to the electronic point-of-interest record to form an ordered expected query;

creating, by the computing device, a plurality of electronic point-of-interest record references to the electronic point-of-interest records that contain the tokens in the ordered expected query;

ordering, by the computing device, the plurality of electronic point-of-interest record references by decreasing relevance of the electronic point-of-interest records to the ordered expected query to form an ordered list of electronic point-of-interest record references;

creating, by the computing device, a key-value pair for the ordered expected query, wherein the key for the key-value pair comprises the ordered expected query and the value for the key-value pair comprises the ordered list of electronic point-of-interest record references; and

storing, by the computing device, the key-value pairs in the geo-search query index.

12. The method of claim 11 , wherein randomly generating, by the computing device, a first plurality of expected queries for the electronic point-of-interest record further comprises:

generating for each of a number of query lengths, a plurality of queries using tokens randomly selected from the electronic point-of-interest record based at least in part on the frequencies of the tokens in the electronic point-of-interest record.

13. The method of claim 11 , wherein randomly generating, by the computing device, a first plurality of expected queries for the electronic point-of-interest record further comprises:

generating the expected queries using a Monte Carlo simulation for each of a plurality of query lengths.

14. The method of claim 11 , wherein storing the key-value pairs in a geo-search query index comprises:

combining similar key-value pairs having similar ordered expected queries to form query-reference pairs, each query-reference pair comprising the tokens of the similar expected queries as the query, and the lists of electronic point-of-interest record references as the references; and

storing the query-reference pairs in the geo-search query index.

15. The method of claim 14 , further comprising:

ordering the query-reference pairs;

partitioning the ordered pairs into a plurality of sequences of the query-reference pairs, each sequence including a last query-reference pair in the sequence;

for each of the sequences, forming a cluster key-value pair from the query-reference pairs of the sequence, wherein the cluster key-value pair comprises the query of the last query-reference pair of the sequence, and the value comprises all of the electronic point-of-interest record references from all of the query-reference pairs in the sequence; and

storing each of the cluster key-value pairs in the geo-search query index.

16. The method of claim 15 , further comprising:

creating a plurality of partitions of the geo-search query index, each partition stored on a separate server; and

storing each key-value pair to one of the plurality of partitions, based on the query of the key.

17. The method of claim 14 , further comprising:

creating a plurality of partitions of the geo-search query index, each partition stored on a separate server; and

storing each query-reference pair to one of the plurality of partitions, based on the query of the query-reference pair.

Assignments (7)