Full text search using R-trees
View Patent ↗A method and system for full text search (FTS) using a navigation system is disclosed. The FTS system generates vectors for documents that are stored in a database. The vectors are formed by converting data token pairs to binary or hexadecimal strings. The FTS system may generate and store vectors in a multi-dimensional index (e.g., an R-Tree) for each document stored in the database. The FTS system may receive two or more search terms inputted by a user and generate one or more vectors based on the inputted search terms. The FTS system may then use the generated vectors to query the multi-dimensional index.
1. A computer-implemented method for facilitating full-text search, the method comprising:
receiving a plurality of search terms;
generating a query range for each received search term, wherein the query range includes a lower-bound token pair and an upper-bound token pair;
querying a multi-dimensional index using the query range; and
receiving from the multi-dimensional index, based on the querying, a result set that is associated with the plurality of search terms.
2. The method of claim 1 , further comprising:
for each unique combination of two search terms in the plurality of search terms, wherein each unique combination of two search terms comprises a first search term and a second search term, generating (i) the lower-bound token pair by combining a lower-bound search value that corresponds to the first search term and a lower-bound search value that corresponds to the second search term, and (ii) the upper-bound token pair by combining an upper-bound search value that corresponds to the first search term and an upper-bound search value that corresponds to the second search term.
3. The method of claim 1 , further comprising:
for each unique combination of three search terms in the plurality of search terms, wherein each unique combination of three search terms comprises a first search term, a second search term, and a third search term, generating (i) the lower-bound token pair by combining a lower-bound search value that corresponds to the first search term, a lower-bound search value that corresponds to the second search term, and a lower-bound search value that corresponds to the third search term, and (ii) the upper-bound token pair by combining an upper-bound search value that corresponds to the first search term, an upper-bound search value that corresponds to the second search term, and an upper-bound search value that corresponds to the third search term.
4. The method of claim 1 , further comprising:
converting at least one search term from the plurality of search terms into a binary or hexadecimal string;
determining that the string has a length that is less than a threshold number of bytes; and
in response to the determining step, generating a query range that corresponds to the string by:
generating a lower-bound search value by appending at least one zero-byte to the string such that the lower-bound search value has a length equal to the threshold number of bytes, and
generating an upper-bound search value by appending at least one one-byte to the string such that the upper-bound search value has a length equal to the threshold number of bytes.
5. The method of claim 1 , further comprising:
converting at least one search term from the plurality of search terms into a binary or hexadecimal string;
determining that the string has a length that is greater than a threshold number of bytes; and
in response to the determining step, generating a query range that corresponds to the string by:
generating a lower-bound search value by truncating the string such that the lower-bound search value has a length equal to the threshold number of bytes, and
generating an upper-bound search value by truncating the string such that the upper-bound search value has a length equal to the threshold number of bytes.
6. The method of claim 1 , wherein the multi-dimensional index is an R-Tree.
7. The method of claim 1 , wherein at least one of the plurality of search terms is a location value.
8. A computer-implemented method for facilitating full-text search, the method comprising:
organizing data tokens associated with a database entry into a lexicographically-ordered set of data tokens;
generating a token set based on a combination of at least two data tokens from the lexicographically-ordered set of data tokens;
converting the token set into a multi-dimensional vector;
storing the multi-dimensional vector in a multi-dimensional index such that the multi-dimensional vector is associated with the database entry; and
generating a query range from the multi-dimensional vector, wherein the query range includes a lower bound and an upper bound.
9. The method of claim 8 , wherein converting the token set includes converting the data tokens in the token set into binary.
10. The method of claim 8 , wherein converting the token set includes converting the data tokens in the token set into hexadecimal.
11. The method of claim 8 , wherein the token set includes two data tokens and the multi-dimensional vector is a two-dimensional vector associated with a token pair.
12. The method of claim 8 , wherein the token set includes three data tokens and the multi-dimensional vector is a three-dimensional vector associated with a token pair and a location value.
13. The method of claim 8 , wherein the token set includes four data tokens and the multi-dimensional vector is a four-dimensional vector associated with a token pair, a latitude value, and a longitude value.
14. A navigation system comprising:
a processor; and
data storage containing instructions executable by the processor for carrying out destination selection functions, the functions including:
receiving a plurality of search terms;
generating a query range for each received search term, wherein the query range includes a lower-bound token pair and an upper-bound token pair;
querying a multi-dimensional index using the query range; and
receiving from the multi-dimensional index a result set of document identifiers associated with destinations.
15. The navigation system of claim 14 , wherein the document identifiers associated with destinations are point of interest identifiers associated with point of interest records stored in the geographic database.
16. The navigation system of claim 14 , wherein the data storage further contains instructions executable by the processor for carrying out map display functions, the functions including:
receiving the result set of document identifiers;
retrieving the documents associated with the document identifiers from the geographic database; and
displaying a map that identifies locations specified within the documents.
17. The navigation system of claim 16 , wherein the documents are point of interest records in the geographic database and the point of interest records include location data associated with a point of interest.
18. The navigation system of claim 14 , wherein the multi-dimensional index associates the document identifiers with vectors generated using at least two data tokens associated with a document.
19. The navigation system of claim 14 , wherein the multi-dimensional index is an R-Tree.
20. The navigation system of claim 14 , wherein at least one search term of the plurality of search terms is a location value.