At+t Corp.

Lucent Technologies Inc.

Raffaele Giancarlo

Adam Louis Buchsbaum

Jeffery Rex Westbrook

Brenda Sue Baker

A system and method of determining a common neighborhood of users sharing a common activity from a plurality of users is provided. The system and method may be used to predict, for a user in the common neighborhood of users, a potential activity from the activities of at least one other user in the common neighborhood of users.

Graph algorithm for common neighborhood analysis

An approximate weighted finite-state automaton can be constructed in place of a weighted finite-state automaton so long as the approximate weighted finite-state automaton maintains a sufficient portion of the original best strings in the weighted finite-state automaton and sufficiently few spurious strings are introduced into the approximate weighted finite-state automaton compared to the weighted finite-state automaton. An approximate weighted finite-state automaton can be created from a non-deterministic weighted finite-state automaton during determinization by discarding the requirement that old states be used in place of new states only when an old state is identical to a new state. Instead, in an approximate weighted finite-state automaton, old states will be used in place of new states when each of the remainders of the new state is sufficiently close to the corresponding remainder of the old state. An error tolerance parameter &tgr; defines whether the remainders of the new state are sufficiently close to the corresponding remainders of the old state. If the remainders of the new state are sufficiently close to the remainders of the old state, a new transition is created from a current state to the old state rather than the new state. Such approximate weighted finite-state automata allow the size of the resulting deterministic finite-state automata to be reduced and can prevent the expansion that would otherwise occur in some deterministic finite-state automata.

Method and apparatus for generating deterministic approximate weighted finite-state automata

An approximate weighted finite-state automaton can be constructed in place of a weighted finite-state automaton so long as the approximate weighted finite-state automaton maintains a sufficient portion of the original best strings in the weighted finite-state automaton and sufficiently few spurious strings are introduced into the approximate weighted finite-state automaton compared to the weighted finite-state automaton. An approximate weighted finite-state automaton can be created from a non-deterministic weighted finite-state automaton during determinization by discarding the requirement that old states be used in place of new states only when an old state is identical to a new state. Instead, in an approximate weighted finite-state automaton, old states will be used in place of new states when each of the remainders of the new state is sufficiently close to the corresponding remainder of the old state. An error tolerance parameter .tau. defines whether the remainders of the new state are sufficiently close to the corresponding remainders of the old state. If the remainders of the new state are sufficiently close to the remainders of the old state, a new transition is created from a current state to the old state rather than the new state. Such approximate weighted finite-state automata allow the size of the resulting deterministic finite-state automata to be reduced and can prevent the expansion that would otherwise occur in some deterministic finite-state automata.

Method and apparatus for generating deterministic approximate weighted

Methods are disclosed for finding maximal matches in data strings and for finding matches in parameterized strings, that is, strings containing symbols from more than one alphabet in which the symbols from one of the alphabet are treated as parameters. In general, such maximal matches are found by creating a suffix tree representing the data string, generating lists for each node in the tree indicating the left contexts of all suffixes associated with that node and reporting matches for pairs of suffixes having different left contexts. One method of finding parameterized matches is to substitute a common symbol for the symbols of the alphabet representing the parameters before creating the suffix tree and then discarding matches found for which the actual parameters are not consistent. Another, preferred, method of finding parameterized matches is to substitute integers for the symbols of the alphabet representing the parameters, such symbols being chosen to create a linked list in the data string for each different symbol in such alphabet. Matches found by the suffix tree are then consistent and no matches need be discarded. Other methods of finding matches are disclosed in which suffix trees are used in conjunction with square matrices to analyze the data strings.

Method of identifying pattern matches in parameterized strings and

Methods are disclosed for finding maximal matches in data strings and for finding matches in parameterized strings, that is, strings containing symbols from more than one alphabet in which the symbols from one of the alphabets are treated as parameters. In general, such maximal matches are found by creating a suffix tree representing the data string, generating lists for each node in the tree indicating the left contexts of all suffixes associated with that node and reporting matches for pairs of suffixes having different left contexts. One method of finding parameterized matches is to substitute a common symbol for the symbols of the alphabet representing the parameters before creating the suffix tree and then discarding matches found for which the actual parameters are not consistent. Another, preferred, method of finding parameterized matches is to substitute integers for the symbols of the alphabet representing the parameters, such symbols being chosen to create a linked list in the data string for each different symbol in such alphabet. Matches found by the suffix tree are then consistent and no matches need be discarded. Other methods of finding matches are disclosed in which suffix trees are used in conjunction with square matrices to analyze the data strings.

Growing community of inventors

New York, NY, United States of America

Raffaele Giancarlo