Input string matching for domain names

A plurality of input string n-grams may be generated by accessing an input string and generating a Universal character set transformation format (UTF) encoded input string from the input string. The UTF encoded input string may be parsed via an n-gram parser to generate a plurality of input string n-grams, where a length of each of the input string n-grams is larger than a lower bound and smaller than an upper bound. The generated plurality of input string n-grams may be provided to determine matches between the input string and a domain.

BACKGROUND

The Internet enables a user of a client computer system to identify and communicate with millions of other computer systems located around the world. A client computer system can identify each of these other computer systems using a unique numeric identifier for that computer called an “IP address.” When a communication is sent from a client computer system to a destination computer system, the client computer system typically specifies the IP address of the destination computer system in order to facilitate the muting of the communication to the destination computer system. For example, when a request for a World Wide Web page (“Web page”) is sent from a client computer system to a Web server computer system (“Web server”) from which that Web page can be obtained, the client computer system typically includes the IP address of the Web server.

In order to make the identification of destination computer systems more mnemonic, a Domain Name System (DNS) has been developed that translates a unique alphanumeric name for a destination computer system into the IP address for that computer. The alphanumeric name is called a “domain name.” For example, the domain name for a hypothetical computer system operated by Example Corporation may be “comp23.example.com”. Using domain names, a user attempting to communicate with this computer system could specify a destination of “comp23.example.com” rather than the particular IP address of the computer system (e.g., 198.81.209.25). Domain names may include character sets such as upper and lowercase letters a-z and digits 0-9. Internationalized Domain Names (IDN) are domain names that include characters used in the local representation of languages that are not written with the twenty-six letters of the basic Latin alphabet “a-z”. An IDN can contain Latin letters with diacritical marks, as required by many European languages, or may include characters from non-Latin scripts such as Arabic or Chinese. Many languages also use other types of digits than the European “0-9”. The basic Latin alphabet together with the European-Arabic digits are, for the purpose of domain names, termed “ASCII characters” (ASCII=American Standard Code for Information Interchange). These are also included in the broader range of “Unicode characters” that provides the basis for IDNs.

DETAILED DESCRIPTION

With the introduction and increasing use of internationalized domain names (IDNs), registrants may encounter new challenges when registering a domain name. For example, in scripts that are new to the Internet Naming space, but used by a large population of users (i.e., Chinese, Cyrillic, Hangul, Arabic, etc.), a user may generate a domain name request utilizing one or more graphemes that, although they may visually appear to be the same, are not exactly the same as the one or more graphemes in a registered domain name. This may result in a request for a non-existent domain (NXD). NXD data, including the domain name request, may be stored in a storage for analysis.

DNS Registry operators are interested in Identifying domain names that match keywords for multiple reasons, Including NXD monitoring, drop catch notification, trademark monitoring and searching IDNs. While there are existing matching algorithms to conduct natural language searches, the existing matching algorithms may be deficient when conducting multilingual keyword matching with domain names across natural languages.

As discussed herein, a multilingual keyword matching service may be performed with domain names across natural languages. The multilingual, or language-independent, keyword matching service may assist in identifying variants of domain names across natural languages. Given Universal character set transformation format encoded keywords, for example, 8-bit (UTF8)-encoded keywords, in any language, the keyword matching service may return a plurality of highly relevant domain names across multiple TLDs matching a set of input keywords. The keywords can comprise keywords in a single natural language, or can include a mix of different natural languages.

The keyword matching service can operate synchronously or asynchronously, and can be tuned to provide responses at varying degrees of verbosity. The keyword matching algorithm may generally be implemented as a substring search. The keyword matching may incorporate a controlled vocabulary including a stopword list.

The processes discussed herein may utilize an in-memory n-gram index for fast lookups. This system features an indexing process that balances the need for a high degree of precision and recall across multiple languages while at the same time keeping index size to a manageable level. The process may include creating an inverted n-gram index, or a plurality of n-grams, given a set of domain names where n equals a range from a lower bound to an upper bound. These bounds are configurable on a per-language basis, and may be tuned to best meet the precision and recall goals of a given language. For example, in languages with a large number of more expressive characters (such as some Asian languages), the system may have a smaller lower bound than with most Latin-based languages. By comparing the n-grams created from the keywords with n-grams created from the domains, domains that match the keywords may be identified.

As discussed herein, an input string may be accessed where the input string includes a keyword to be compared to one or more domains. A UTF-encoded input string may be generated from the input string. The UTF-encoded input string may be parsed via an n-gram parser to generate a plurality, for example, a list, of input string n-grams. A domain to be compared may be accessed and a UTF-encoded domain string may be generated from the accessed domain. The UTF-encoded domain string may be parsed to generate a plurality of domain string n-grams from the UTF-encoded domain string. The plurality of input string n-grams may be compared to the plurality of domain string n-grams. When one or more n-grams in the plurality of input string n-grams match one or more n-grams in the plurality of domain string n-grams, this may indicate that the input string matches the domain.

According to some examples, a relevance score may be generated for each of the identified matches. The relevance score may be calculated based on the number of input string n-grams that match the domain string n-grams in order to provide an indication of the degree of relevance of the match. A higher relevance score may indicate that a match of the domain is closer to the input string where a lower relevance score may indicate that a match of the domain is not as close to the input string.

As further discussed herein, a plurality of input string n-grams may be generated by accessing an input string and generating a UTF-encoded input string from the input string. The UTF-encoded input string may be parsed via an n-gram parser. A plurality of input string n-grams may be generated, where a length of each of the input string n-grams is based on a lower bound and upper bound. The generated plurality of Input string n-grams may be provided to determine matches between the plurality of input string n-grams with plurality of n-grams generated from domains.

According to some examples, a domain name input stream may be received where the domain name input stream includes a plurality of domain names. For each domain name in the domain name input stream, a UTF-encoded domain string may be generated and parsed to generate a plurality of domain string n-grams from the UTF-encoded domain string. A plurality of input string n-grams generated from a UTF-encoded input string may be accessed. The plurality of n-grams from the UTF-encoded input string may be compared to the plurality of n-grams of each of the UTF-encoded domain strings. Matches between the input string and domain names may be identified based on the comparison of the input string n-grams and the domain string n-grams. An alert may be generated including the matches of the input string and the domain names.

The matches of the input string and the domain names may indicate variants of the domain names. By determining variants of a domain name, a registrant of a domain name may have the opportunity to register variants of a domain name. This may ensure that other users access the intended registered domain, even if the domain name a user is trying to access includes one or more graphemes that are different from the graphemes in the registered domain name.

While the examples discussed herein are made with respect to UTF-8 encoding, it may be appreciated that other UTF encoding may be utilized, for example, UTF-16, UTF-32, or any other encoding that supports UTF.

FIG. 1depicts an example system environment implementing features consistent with one or more examples discussed herein. It may be appreciated that additional elements may be included in system environment100and some of the elements may be removed and/or modified without departing from the spirit and scope of this disclosure.

As shown inFIG. 1, system environment100may include apparatus or input string matching device102including Input string matcher103for determining whether one or more input strings match one or more domains. Device102may be communicably Inked to apparatus or device104through network106. Device104may be implemented as a client computing device, an administrative computing device, etc. Domain name variants generated at device102may be provided to device104through network106.

Device102may be implemented as a server, a mainframe computer, any combination of these components, or any other appropriate computing device or resource service, for example, a cloud, etc. Device102may be standalone, or may be part of a subsystem, which may, in turn, be part of a larger system. It may be appreciated that, while device102may be described as including various components, one or more of the components may be located at other devices (not shown) within system environment100.

Client device104may be implemented as any computing device, for example, a desktop computer, laptop computer, portable computing device, etc. Client device104may enable communication with device102, enable providing Input strings for matching, and receive indications of matches of input strings with domains, among other things as described herein.

Additionally, each of devices102and104includes the necessary hardware and/or software needed to communicate with the network106via a wired and/or a wireless connection. Device102and104may be embodied by a server computing device, desktop/laptop/handheld computers, wireless communication devices, personal digital assistants or any other similar devices having the necessary processing and communication capabilities. In an embodiment, the network106may comprise a public communication network such as the Internet or World Wide Web and/or a private communication network such as a local area network (LAN), wide area network (WAN), etc.

One or both of devices102and104, which may comprise one or more suitable computing devices, implement the functionality as discussed herein.

As discussed herein, devices102and104include one or more processors in communication with one or more storage devices. The processor(s) may comprise a microprocessor, microcontroller, digital signal processor, co-processor or other similar devices known to those having ordinary skill in the art. In addition, the storage device(s) as discussed herein may comprise a combination of non-transitory, volatile or nonvolatile memory such as random access memory (RAM) or read only memory (ROM). Such storage devices may be embodied using any currently known media such as magnetic or optical storage media including removable media such as floppy disks, compact discs, etc. One or more storage devices has stored thereon instructions that may be executed by the one or more processors, such that the processor(s) implement the functionality described herein. In addition, or alternatively, some or all of the software-implemented functionality of the processor(s) may be implemented using firmware and/or hardware devices such as application specific Integrated circuits (ASICs), programmable logic arrays, state machines, etc.

FIG. 2depicts an example configuration of input string matching device102depicted inFIG. 1. Input string matching device200may identify matches between input strings and domains. As shown inFIG. 2, device200may include n-gram parser202, exact match comparator204, fuzzy match comparator206, relevance score calculator208, network interface application210, processor212, IDN processor214, and alert generator216. As indicated by the dashed lines inFIG. 2, at least exact match generator204, fuzzy match generator206, IDN processor214, and relevance score calculator208may be optionally provided.

N-gram parser202may be utilized by one or more of the exact match comparator204and the fuzzy match comparator206to generate a plurality of n-grams for a given input. N-gram parser202may generate a plurality of n-grams for Unicode strings. The n-gram parser202may utilize a lower and upper bound for n, for example, based on a particular Unicode range Including a first character of the string. According to some examples, the Unicode range may be determined based on a specific language. Thus, the system may utilize different lower and upper bounds for different languages.

According to some examples, the entire string may be added to the plurality of n-grams, as an n-gram, when the string length is less than the lower indexing bound or when the string is an exact match with a stop word from a pre-configured stop word list.

According to some examples, the n-gram parser202may add prefixes and/or suffixes of the input strings to the plurality of n-grams. The length of the prefix and/or suffix of an Input string may be equal to, for example, the lowerbound-m, where m is an integer, for example, 1, etc.

According to some examples, n-gram parser202may parse a string to add to the plurality of n-grams using the “-” character as a delimiter, regardless of the value of the lower or upper bound of n. Here, the string of characters, for example, all of the characters, before the “-” and the string of characters, for example, all of the characters, after the “-” may be added to the plurality of n-grams.

According to some examples, the n-gram parser202may add the entire string to the plurality of n-grams regardless of the value of the lower or upper bound of n.

Exact match comparator204may compare n-grams generated from input strings with n-grams generated from domains in order to identify exact matches. According to some examples, the exact match comparator204may compare ASCII and punycode IDNs with input strings, or keywords, comprising Unicode strings of different encoding, including for example UTF-encoded, by comparing n-grams generated therefrom. According to some examples, the exact match comparator204may utilize n-grams of a length that is bounded by a lower bound and an upper bound based on a particular Unicode range. If matches between one or more input string n-grams and domain string n-grams are found, matches between the input string and the domains may be identified. According to some examples, matches between the input string and the domains may be based on a relevance score generated by relevance score calculator208discussed below.

Fuzzy match comparator206may compare n-grams generated from input strings with n-grams from domains in order to identify fuzzy (non-exact) matches. Fuzzy matches may be based on, a comparison between n-grams utilizing, for example, an edit distance calculation, or other suitable calculations. According to some examples, the fuzzy match comparator206may compare ASCII and punycode IDNs to keywords comprising Unicode strings of different encoding, including for example UTF-8, by comparing n-grams generated therefrom. According to some examples, the fuzzy match generator may utilize n-grams of a length that is bounded by a lower bound and an upper bound based on a particular Unicode range. If matches between one or more input string n-grams and domain string n-grams are found, matches between the input string and the domains may be identified. According to some examples, matches between the input string and the domains may be based on a relevance score generated by relevance score calculator208discussed below.

Relevance score calculator208may calculate a relevance score for use by, for example, by the exact match comparator204. The relevance score may be the sum of the number of input string n-grams matched with domain n-grams and a similarity score, for example, a dice coefficient similarity score between the domain n-grams and input string n-grams.

Network interface application210facilitates network communication between device102and device104.

Processor212may execute computer-readable instructions, stored in storage (not shown inFIG. 2), to perform functionality as described herein.

IDN processor214may be used by the n-gram parser202to convert, where needed, input strings of type ASCII, punycode, or Unicode to a normalized UTF-8 form. According to some examples, IDN processor214may strip out any top-level domain suffix.

According to some examples, device200may include data storage (not shown) to store domain information for use within device200. As discussed herein, domain information relating to domains may include non-existent domain (NXD) data, registered domain name information, pending domain names that are to be deleted, or de-registered, registered domain name Information from one or more Top-Level Domains, registered domain name Information from one or more WHOIS databases, registered domain data from Trademark Clearing House Data, etc. NXD data may include domain names that were included in requests generated by users at client devices, where the domain name in the request resulted in a non-existent domain name.

According to some examples, device200may include a storage (not shown), to store input strings for use within device200. As discussed herein, input strings may Include one or more keywords, one or more trademarks, one or more domains, one or more domain names, etc. According to some examples, the storage storing input strings may be the same, or different than the storage storing domain information.

Alert generator216may generate one or more alerts Including information generated by device200. According to some examples, alert generator218may generate an alert including input string n-grams. According to some examples, alert generator216may generate an alert including one or more domains that match one or more input strings. According to some examples, alert generator may generate an alert including one or more domains that match one or more input strings together with a relevance score indicating a relevance of one or more of the domains. The alert generated by alert generator216may be output to an output device (not shown) of device200, may be stored in a local storage, or may be transmitted to a device remote from device200, for example, a client device, an administrative device, a storage device, etc.

FIG. 3depicts an example process300for comparing input strings with domain strings. Process300may be performed, for example, by device200. As shown inFIG. 3, an input string302may be passed to n-gram parser304. The input string may be one or more input strings in a UTF-8 format. N-gram parser304may parse the input string to generate a plurality of input string n-grams. The n-gram parser304may be generate n-grams of a length of n, n being an integer ranging from a preselected lower bound to an upper bound that is equal to the length of the input string. According to some examples, the lower and upper bound for n may be based on a Unicode range of a first character of the input string.

According to some examples, the entire string may be used as an n-gram when the sting length is less than the lower bound or when the string is an exact match with a stop word from a pre-configured stop word list.

According to some examples, the n-gram parser304may add prefixes and/or suffixes of the input string to the plurality of n-grams. The length of the prefix and/or suffix of an input string may be of a length equal to the lowerbound −1.

According to some examples, n-gram parser304may parse the input string to produce n-grams to add to the plurality of n-grams by using the “-” character as a delimiter regardless of the value of the lower or upper bound of n.

According to some examples, the n-gram parser304may add the entire input string to the plurality of n-grams regardless of the value of the lower or upper bound of n.

Domain string306may be passed to n-gram parser308. The domain string may be one or more domain strings in a UTF-8 format. N-gram parser308may parse the domain string to generate a plurality of domain string n-grams. The n-gram parser308may be generate n-grams of a length of n, n being an integer ranging from a lower bound to an upper bound equal to the length of the input string. According to some examples, the lower and upper bound for n may be based on a Unicode range of a first character of the domain string.

According to some examples, the entire string may be added to the plurality of n-grams as an n-gram when the string length is less than the lower indexing bound or when the string is an exact match with a stop word from a pre-configured stop word list.

According to some examples, the n-gram parser308may add prefixes and/or suffixes of the domain string to the plurality of n-grams. The length of the prefix and/or suffix of the domain string may be equal to the lowerbound −1.

According to some examples, n-gram parser308may parse the domain string to produce n-grams to add to the plurality of n-grams using the “-” character as a delimiter regardless of the value of the lower or upper bound of n.

According to some examples, the n-gram parser384may add the entire Input string to the plurality of n-grams regardless of the value of the lower or upper bound of n.

The plurality of input string n-grams and the plurality of domain string n-gram may be passed to match comparator310to identify matches. Match comparator310may utilize exact match comparator204and/or fuzzy match comparator206as discussed with regard toFIG. 2.

Match comparator310outputs matches between the input string and the domain string based on matches between the plurality of input string n-grams and the plurality of domain string n-grams. According to some examples, a match may be determined if one or more input string n-grams matches one or more domain string n-grams.

According to some examples, the matches may be analyzed to calculate a relevance score, via relevance score calculator208. The relevance score may be based on keyword and Input string n-gram matches with domain string n-gram matches. The relevance score may be the sum of the number of input string n-grams matched with domain string n-grams and a similarity score, for example, a dice coefficient similarity score between the domain string n-grams and input string n-grams. The relevance scores may be associated with the respective matches and output. According to some examples, a minimum threshold value for the relevance score may be predefined, where only matches having a score at or above the predefined minimum threshold may be output.

According to some examples, an alert may be generated, for example, by alert generator216, the alert including the matches between the input strings and the domains and may be passed, for example, to an output device, to a remote device, etc. An alert may be generated when one or more matches is found between an input string and a domain string.

FIG. 4depicts an example process400for generating a plurality of n-gram fuzzy matches utilizing edit distance. Process400may be performed, for example, by fuzzy match comparator206. As shown inFIG. 4, an input string402may be passed to n-gram parser404. The input string may be one or more input strings in a UTF-8 format. N-gram parser404may parse the input string to generate a plurality of input string n-grams. The n-gram parser404may be generate n-grams of a length of n, n being an integer ranging from a lower bound to an upper bound equal to the length of the Input string. According to some examples, the lower and upper bound for n may be based on a Unicode range of a first character of the input string.

According to some examples, the entire string may be added to the plurality of n-grams as an n-gram when the string length is less than the lower indexing bound or when the string is an exact match with a stop word from a pre-configured stop word list.

According to some examples, the n-gram parser404may add prefixes and/or suffixes of the input string to the plurality of n-grams. The length of the prefix and/or suffix of the input string may be equal to the lowerbound −1.

According to some examples, n-gram parser404may parse the input string to add to the plurality of n-gram using the “-” character as a delimiter regardless of the value of the lower or upper bound of n.

According to some examples, the n-gram parser404may add the entire input string to the plurality of n-grams regardless of the value of the lower or upper bound of n.

Domain string406may be passed to n-gram parser408. The domain string may be one or more domain strings in a UTF-8 format. N-gram parser408may parse the domain string to generate a plurality of domain string n-grams. The n-gram parser408may be generate n-grams of a length of n, n being an integer, from a lower bound to the length of the input string. According to some examples, the lower and upper bound for n may be based on a Unicode range of a first character of the domain string.

According to some examples, the entire string may be added to the plurality of n-grams as an n-gram when the string length is less than the lower Indexing bound or when the string is an exact match with a stop word from a pre-configured stop word list.

According to some examples, the n-gram parser408may add prefixes and/or suffixes of the domain string to the plurality of n-grams. The length of the prefix and/or suffix may be equal to the lowerbound −1.

According to some examples, n-gram parser408may parse the domain string to add to the plurality of n-grams using the “-” character as a delimiter regardless of the value of the lower or upper bound of n.

According to some examples, the n-gram parser408may add the entire input string to the plurality of n-grams regardless of the value of the lower or upper bound of n.

The plurality of n-grams generated by n-gram parser408may be passed to410where the system loops through each domain string n-gram. Each domain n-gram may be passed to412where the system loops through each input string n-gram. Each domain n-gram is compared to each input n-gram and an edit distance is calculated414. A predefined edit distance factor is utilized to determine if the calculated edit distance is greater than or less than a predetermined edit distance factor. This comparison determines the degree of similarity between the two n-grams, where a small edit distance indicates a large degree of similarity and a larger edit distance indicates a smaller degree of similarity. If the edit distance is less than the edit distance factor (414, YES), indicating an acceptable degree of similarity between the domain n-gram and the input n-gram, then the matched domain name is stored416. If the edit distance is greater than the edit distance factor (414, NO), then the domain string is discarded418.

Process400proceeds to process n-grams as described until al of the generated domain n-grams are compared to all of the input string n-grams.

According to some examples, an alert may be generated, for example, by alert generator216, the alert including the stored matched domain names and may be passed, for example, to an output device, to a remote device, etc.

FIG. 5depicts pseudocode for generating a plurality of n-grams in accordance with some examples as discussed herein. The process depicted inFIG. 5may be performed, for example, by n-gram parser202.

As can be seen inFIG. 5, the process utilizes an input string, a stopword list, a lower bound, an upper bound, and an n-gram index (for example, a list or set of n-grams). The input string may be in various forms, for example, UTF format such as UTF-8, etc., ASCII, such as punycode, etc. The lower bound may be a numerical value representing a lower bound of the length of generated n-grams. The upper bound may be a numerical value representing an upper bound of the length of generated n-grams. The upper bound and lower bound may be set by default (e.g., on a per-language or per-Unicode-range basis), may be set via an interface by a user, etc.

As can be seen inFIG. 5, the TLD may be stripped from the input string. If the Input string is punycode, the punycode is converted to UTF format, such as UTF-8.

If the input string is in the stopword list, the entire input string is added to the n-gram index and the process is completed.

If the Input string is not in the stopword list, and if the length of the input string is less than the lower bound, the input string is added to the n-gram index and the process is completed. If the length of the input string is less than or equal to the upper bound, then the upper bound is set as the length of the input string. If the length of the input string is not less than or equal to (i.e., greater than) the upper bound, then the input string is added to the n-gram index. Further n-grams are indexed for the input string from the lower bound to the upper bound. For each n-gram, if the n-gram does not contain a “-”, the n-gram is added to the n-gram index. Further, prefixes and suffixes for the input string are indexed where the length of the prefix of the input string is equal to the lower bound −1, and the length of the suffix is equal to the length of the input string—(lowerbound −1). If the input string Includes a “-”, “-” is used as a delimiter where in the input string is split into multiple strings, for example, all characters before the “-” may be one substring, and all of the characters after the “-” may be another substring. Each of the substrings may be added to the n-gram index if they are not already in the n-gram index. The process is completed.

FIG. 6is a process600for generating a UTF-8 string according to some examples as discussed herein. Process600may be implemented by, for example, IDN processor214. As shown inFIG. 6, input string602is provided. Input string602may be accessed, for example, by device200from a storage, from a client device, via a user interface, via a user interface at device200, etc.

A determination is made whether the input string is an IDN604. For example, it may be determined whether the input string has an “XN” prefix. If the input string has an “XN” prefix, the string may be an IDN domain. If not, then the string is not an IDN domain. If it is determined that the input string is an IDN (604, YES), then the TLD name is stripped from the IDN input string and the punycode for the remainder is decoded to a UTF-8 string606. The UTF-8 string is then output. If the input string Is not an IDN (604, NO), then processing proceeds to610.

At610, a determination is made whether the input string is a domain string. For example, it may be determined if the Input string is a non-IDN, ASCII domain. If the input string is a domain string (610, YES), then the TLD is stripped from the input string and the remainder of the input string is converted to UTF-8612. The UTF-8 string is then output608. If the input string is not a domain string (610, NO), then processing proceeds to612.

At612, the Input string is decoded to UTF-8. The UTF-8 string is then output608.

According to some examples, the UTF-8 string608is utilized as the input string and/or the domain that is input to n-gram parsers as more fully discussed herein.

FIG. 7illustrates a block diagram of a computing apparatus700, such as the device200depicted inFIG. 2, according to an example. In this respect, the computing apparatus700may be used as a platform for executing one or more of the functions described hereinabove.

The computing apparatus700includes one or more processors702, such as the processor(s)212. The processor(s)702may be used to execute some or all of the steps, operations and functions described in the processes, methods and systems depicted inFIGS. 3-6. Commands and data from the processor(s)702are communicated over a communication bus704. The computing apparatus700also includes a main memory706, such as a random access memory (RAM), where the program code for the processor(s)702may be executed during runtime, and a secondary memory708. The secondary memory708may includes, for example, one or more hard disk drives710and/or a removable storage drive712, representing a floppy diskette drive, a magnetic tape drive, a compact disk drive, etc., where a copy of the program code for the methods and processes discussed inFIGS. 3-6may be stored.

The removable storage drive710may read from and/or write to a removable storage unit714in a well-known manner. User input and output devices716may Include a keyboard, a mouse, a display, etc. A display adaptor718may interface with the communication bus704and the display720and may receive display data from the processor(s)702and convert the display data into display commands for the display720. In addition, the processor(s)702may communicate over a network, for Instance, the Internet, LAN, etc., through a network adaptor722.

FIG. 8depicts a system800, in accordance with some examples as discussed herein, wherein a multi-lingual keyword matching service may be used to implement a domain search web service, where a pre-existing set of domains are Indexed and users can enter search terms, as input strings, and receive a set of matching domains. In accordance with some examples, device200may receive a whitespace-separated set of keywords via HTTP or similar protocol from client device802. The keywords may be indexed, or parsed, using an n-gram parser804, thereby producing a keyword index, or a plurality of keyword n-grams. Keyword matching service806matches the plurality of n-grams of the keywords, I.e., the plurality of input string n-grams as discussed above, with a preexisting domain n-gram index808or domain n-gram set, producing one or more matched domains. The matched domains are returned, for example, to a display at a client device, via HTTP, in one of the following formats: HTML, XML, RSS, or JSON. On the backend, the domain n-gram index808is periodically refreshed by running a set of domains812through the n-gram parser810and storing the resulting domain n-grams in the domain n-gram index808.

FIG. 9depicts a system900, in accordance with some examples as discussed herein, wherein a multi-lingual keyword matching service may be implemented as a web service. As shown inFIG. 9, a user interface902may receive keyword(s) and domain(s). A keyword matching service908returns one or more matching domains and the specific keywords they match to the user interface902.

As shown inFIG. 9, a request may be received via HTTP at user interface902including a set of keywords and a set of domains. Both the keywords and the domains are processed via an n-gram parser904and906, respectively, creating both a plurality of keyword n-grams and a plurality of domain n-grams. It may be appreciated that n-gram parser904may be implemented as two n-gram parsers, as shown, as a single n-gram parser, may be implemented within keyword matching service908, etc.

Keyword matching service908matches domains to keywords, as more fully discussed above, and returns results to the user interface as HTML, XML, RSS, or JSON.

FIG. 10depicts a system1000, in accordance with some examples as discussed herein, wherein a multi-lingual keyword matching service is implemented as a batch process/daemon for the purposes of monitoring a domain name input stream (e.g., NXD data, pending delete domains, etc.) given a set of keywords (e.g., brand trademarks, etc.). As shown inFIG. 10, keyword matching service1010runs continuously as a daemon or on a schedule as a chronological job.

Keyword matching service1010receives a plurality of keyword n-grams, generated by the n-gram parser1016from a pre-configured set of keywords1018, and a plurality of domain n-grams, generated by the n-gram parser1014from a domain input stream1012.

Keyword matching service1010determines one or more matching domains and writes the one or more matching domains to a message queue1008. The message queue1008disseminates the one or more matching domains, for example, via SMS message1002, email1004, EPP poll message1006, or other channels of communication (not shown).

The following is an example of an input strings processed by the functionality discussed with regard toFIG. 5.

Lowerbound: 3Upperbound: 15Input string after stripping out TLD: POWERED-BY-VERISIGNUpperbound after accounting for input string size: 15Index ngrams for POWERED-BY-VERISIGN, skipping those that contain a dash.Adding POW to Index.Adding OWE to index.Adding WER to index.Adding ERE to Index.Adding RED to index.Adding VER to Index.Adding ERI to Index.Adding RIS to index.Adding ISI to index.Adding SIG to index.Adding IGN to index.Adding POWE to index.Adding OWER to Index.Adding WERE to index.Adding ERED to index.Adding VERI to index.Adding ERIS to index.Adding RISI to index.Adding ISIG to index.Adding SIGN to index.Adding POWER to index.Adding OWERE to index.Adding WERED to Index.Adding VERIS to index.Adding ERISI to index.Adding RISIG to index.Adding ISIGN to index.Adding POWERE to index.Adding OWERED to index.Adding VERISI to index.Adding ERISIG to index.Adding RISIGN to index.Adding POWERED to index.Adding VERISIG to index.Adding ERISIGN to Index.Adding VERISIGN to index.Add entire string to index if Upperbound is less than the length of the input string:Adding POWERED-BY-VERISIGN to index.Index prefixes and suffixes where lower bound −1Adding PO to index.Adding GN to Index.Split string by ‘-’ and add gram to index only if not already present in IndexAdding BY to Index.

Lowerbound: 3Upperbound: 15Input string after stripping out TLD: ANDUpperbound after accounting for input string size: 3If input string is a stopword or less than the lower bound, then add entire string to index and exit:Adding AND to index.

Lowerbound: 3Upperbound: 15Input string after stripping out TLD: XYUpperbound after accounting for input string size: 2If input string is a stopword or less than the lower bound, then add entire string to index and exit:Adding XY to Index.

Lowerbound: 3Upperbound: 15Input string after stripping out TLD: MYVERISIGNTVUpperbound after accounting for input string size: 12Index ngrams for MYVERISIGNTV, skipping those that contain a dash.Adding MYV to Index.Adding YVE to Index.Adding VER to index.Adding ERI to Index.Adding RIS to index.Adding ISI to index.Adding SIG to Index.Adding IGN to Index.Adding GNT to index.Adding NTV to index.Adding MYVE to index.Adding YVER to index.Adding VERI to Index.Adding ERIS to Index.Adding RISI to index.Adding ISIG to Index.Adding SIGN to index.Adding IGNT to index.Adding GNTV to Index.Adding MYVER to Index.Adding YVERI to index.Adding VERIS to index.Adding ERISI to Index.Adding RISIG to index.Adding ISIGN to Index.Adding SIGNT to index.Adding IGNTV to index.Adding MYVERI to index.Adding YVERIS to index.Adding VERISI to index.Adding ERISIG to Index.Adding RISIGN to Index.Adding ISIGNT to index.Adding SIGNTV to index.Adding MYVERIS to index.Adding YVERISI to index.Adding VERISIG to index.Adding ERISIGN to index.Adding RISIGNT to index.Adding ISIGNTV to Index.Adding MYVERISI to index.Adding YVERISIG to Index.Adding VERISIGN to Index.Adding ERISIGNT to index.Adding RISIGNTV to index.Adding MYVERISIG to index.Adding YVERISIGN to index.Adding VERISIGNT to index.Adding ERISIGNTV to index.Adding MYVERISIGN to index.Adding YVERISIGNT to index.Adding VERISIGNTV to index.Adding MYVERISIGNT to Index.Adding YVERISIGNTV to index.Adding MYVERISIGNTV to index.Index prefixes and suffixes where lower bound −1Adding MY to index.Adding TV to index.Split string by ‘-’ and add gram to Index only if not already present in index:No dashes found

Lowerbound: 3Upperbound): 16Input string after stripping out TLD: SHORT-NAMEUpperbound after accounting for input string size: 10Index ngrams for SHORT-NAME, skipping those that contain a dash.Adding SHO to index.Adding HOR to Index.Adding ORT to index.Adding NAM to index.Adding AME to Index.Adding SHOR to Index.Adding HORT to Index.Adding NAME to index.Adding SHORT to index.Index prefixes and suffixes where lower bound −1Adding SH to index.Adding ME to index.Split string by ‘-’ and add gram to index only if not already present in indexSHORT and NAME have already been added-no need to add a second timeAlways make sure entire string is added to Index regardless of circumstances:Adding SHORT-NAME to index.

Lowerbound: 3Upperbound: 15Input string after stripping out TLD and converting punycode to UTF-8:-Upperbound after accounting for input string size: 8Index ngrams for-, skipping those that contain a dash.Addingto index.Addingto Index.Aidingto index.Addingto index.Addingto index.Adding- to index.Addingto index.Addingto index.Addingto index.Addingto index.Adding- to index.Addingto index.Addingto index.Addingto index.Adding- to index.Addingto index.Addingto index.Adding- to index.Addingto index.Adding- to index.Adding- to index.Index prefixes and suffixes where lower bound −1:Adding∃ to index.Adding- to index.Split string by ‘-’ and add gram to index only if not already present in Index:No dashes found

The following is what the entire inverted n-gram index looks like after the aforementioned examples have been indexed (format [gram]=[domain1][domain2][etc.]:

The following is an example of a Simple Exact Match Search Scenario utilizing the Index created in the six examples set forth above. The process for performing the exact match search is discussed, for example, inFIG. 3:1. Search string: “Verisign Power”2. Parse search string on white space (optionally, you can parse search string as n-grams).3. “Verisign” matches two domains:POWERED-BY-VERISIGN.COMMYVERISIGNTV.TV4. “Power” matches one domain:POWERED-BY-VERISIGN.COM5. Search engine returns the following two results:POWERED-BY-VERISIGN.COM: Relevance score=2.56Two search terms matched+(13/23)=2.56MYVERISIGNTV.TV: Relevance score=1.53One search term matched+(8/15)=1.53

It may be appreciated that other encodings may be used, for example, UTF-16, UTF-32, other encodings that support Unicode, etc.