Data processing: structural design – modeling – simulation – and em – Modeling by mathematical expression
Reexamination Certificate
2005-03-01
2005-03-01
Homere, Jean R. (Department: 2128)
Data processing: structural design, modeling, simulation, and em
Modeling by mathematical expression
C707S793000, C707S793000, C707S793000, C707S793000, C707S793000, C707S793000, C707S793000, C706S045000, C706S055000
Reexamination Certificate
active
06862559
ABSTRACT:
A method for computing a diversity measure H(m) for combinatorial structures involves identifying all M possible substructures having m elements from among the n elements of the combinatorial structure. The number of the substructures that are similar to each such substructure is determined, and the frequency of each distinct substructure is calculated using the number of similar substructures and the total number of substructures M. The method uses the frequency of each distinct substructure to compute an entropy corresponding to m. By the same process described above, and entropy corresponding to m+1 is computed. The entropy corresponding to m+1 is subtracted from the entropy corresponding to m to produce the diversity measure H(m). In the preferred embodiment, similar substructures are determined by being identical or isomorphic. In an alternative embodiment, a distance function is used to compute a distance between two substructures, and only if the distance is less than a predetermined threshold are the two substructures determined to be similar. In the preferred embodiment, the entropy is computed by summing the frequency of each distinct substructure multiplied by the logarithm of the frequency of each distinct substructure. In an alternative embodiment, the entropy is computed by summing the frequency of each distinct substructure by the logarithm of the quotient of the frequency divided by an expected frequency of the distinct substructure. Generalized graphs such as can be used to model the Web are combinatorial structures suitable for use with the methods according to the present invention.
REFERENCES:
patent: 5703792 (1997-12-01), Chapman
patent: 5727051 (1998-03-01), Holender
patent: 5764740 (1998-06-01), Holender
patent: 5872918 (1999-02-01), Malomsoky et al.
patent: 5895470 (1999-04-01), Pirolli et al.
patent: 5966140 (1999-10-01), Popovic et al.
patent: 6044366 (2000-03-01), Graffe et al.
patent: 6198412 (2001-03-01), Goyal
patent: 6285995 (2001-09-01), Abdel-Mottaleb et al.
patent: 6304639 (2001-10-01), Malomsoky et al.
patent: 6334125 (2001-12-01), Johnson et al.
patent: 6397205 (2002-05-01), Juola
patent: 6539376 (2003-03-01), Sundaresan et al.
patent: 6564197 (2003-05-01), Sahami et al.
patent: 6654743 (2003-11-01), Hogg et al.
patent: 20030014379 (2003-01-01), Saias et al.
“A Library for Visualizing Combinatorial Structures”, M. Najork, pp. 164-171, IEEE 1070-2385/94, IEEE 1994.*
“The Combinatorial Structure of Fuzzy Functional Dependencies”, A. C. Sali, pp. 239-243, IEEE 0-7803-3627-5/97, IEEE May 1997.*
“A Combinatorial, Strongly Polynomial-time Algorithm for Minimizing Submodular Functions”, S. Iwata, STOC 2000, ACM 1-58133-184-4/00/5, 1999.*
“Extracting Randomness: How and Why A Survey”, N. Nisan, IEEE 0-8186-7386-9/96, IEEE 1996.*
“On the Average Delay for Routing Subject to Independent Deflections”, B. Hajek, IEEE Trans. on Info. Theory, vol. 39, No. 1, Jan. 1993.*
“Voronoi Diagrams—A Survay of a Fundamental Geometric Data Strucutre”, F. Aurenhammer, ACM Computing Surveys, vol. 23, No. 3, Sep. 1991.*
“SONIA: A Service for Organizing Networked Information Autonomously”, M. Sahami, ACM 0-89791-965-3/98/6, ACM 1998.*
“Analysis and Design of Server Informative WWW-sites” A. M. Zarkesh, CIKM 97', ACM 0-89791-970, ACM 1997.*
“Robust self-assembly using highly designable structures”, T. Hogg, Nanotechnology 10, IOP Publishing, Jan. 1999.*
“Better Than The Best: The Power of Cooperation”, T. Hogg, 1992 Lectures in Complex Systems, pp. 165-184, Addison-Wesle 1993.*
G. Chaitin, “Randomness and Mathematical proof”,Scientific American,232:47-52, May 1975.
S. Pincus, B. H. Singer, “Randomness and degrees of irregularity”,Proc. Natl. Acad. Sci. USA,93:2083-2088, 1996.
T. Hogg, B.A. Huberman, C. Williams “Phase Transitions and the Search Problem”,Artificial Intelligence,81:1-15, 1996.
B.A. Huberman, T. Hogg, “Complexity and Adaptation”,Physica,22D:376-384, 1986.
B.A. Huberman, T. Hogg, “Communities of Practice: Performance and Evoluation”,Computational and Mathematical Organization Theory, 1(1):73-92, 1995.
H. Kautz, B. Selman, S., M. Shah, “The Hidden Web”,AI Magazine,18(2):27-36, Summer 1997.
R.M. May, “Will a Large Complex System be Stable?”,Nature,238:413-414, Aug. 1972.
S. Pincus, R.E. Kalman, “Not All (Possibly) ‘Random’ Sequences are Created Equal”,Proc. Natl. Acad. Sci. USA,94:3513-3518, 1996.
G. Salton, J. Allan, C. Buckley, A. Singhal, Automatic Analysis, Theme Generation, and Summarization of Machine-Readable Texts,Science,264:1421-1426, Jun. 1994.
Fliesler & Meyer LLP
Xerox Corporation
LandOfFree
Methods and apparatuses for measuring diversity in... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatuses for measuring diversity in..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatuses for measuring diversity in... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3367568