Representative document selection

A method includes accessing a set of documents and a set of representative documents, determining distances from each document to a nearest representative document, and selecting a subset of documents using an algorithm for choosing initial seed values and the determined distances to the nearest representative document. The method further includes repeating the following for each particular document of the subset of documents: adding the particular document to the set of representative documents to create a new set of representative documents, removing the particular document of documents from the set of documents to create a new set of documents, and calculating a sum of distances from each document of the new set of documents to a nearest document in the new set of representative documents. The particular document of the subset that resulted in the lowest sum of distances is selected as a new representative document.

TECHNICAL FIELD

This disclosure relates in general to searching of data and more particularly to selecting representative documents.

BACKGROUND

People are often tasked with reviewing large collections of documents. For example, a researcher may find a collection of one hundred documents on a topic of interest to the researcher. As another example, a researcher may be provided a collection of one million documents to review and analyze. Reviewing such large collections of documents is generally burdensome and time consuming.

SUMMARY OF THE DISCLOSURE

According to one embodiment, a method includes accessing a set of documents and a set of representative documents, determining distances from each document to a nearest representative document, and selecting a subset of documents using an algorithm for choosing initial seed values and the determined distances to the nearest representative document. The method further includes repeating the following for each particular document of the subset of documents: adding the particular document of the subset to the set of representative documents to create a new set of representative documents, removing the particular document of the subset of documents from the set of documents to create a new set of documents, and calculating a sum of distances from each document of the new set of documents to a nearest document in the new set of representative documents. The particular document of the subset that resulted in the lowest sum of distances is selected as a new representative document.

Technical advantages of certain embodiments may include providing one or more representative documents for an input set of documents. The representative documents provide an accurate view of the depth and breadth of the input set of documents without having to review every document in the input set of documents. Some embodiments may additionally accept input representative documents and a desired amount of additional representative documents to locate for an input set of documents. Embodiments utilize the input representative documents to locate the amount of additional representative documents desired by the user. Other technical advantages will be readily apparent to one skilled in the art from the following figures, descriptions, and claims. Moreover, while specific advantages have been enumerated above, various embodiments may include all, some, or none of the enumerated advantages.

DETAILED DESCRIPTION OF THE DISCLOSURE

A person such as a researcher typically is tasked with reviewing collections of documents in order to gain knowledge about a particular subject. For example, a researcher may obtain a large collection of documents on a subject relevant to a topic the researcher is currently studying. The collection of documents may include, for example, one hundred or even one million documents. In order to understand the breadth and depth covered by the collection of documents, the researcher may desire to read a smaller collection of documents (e.g., ten) that are representative of the overall collection.

The teachings of the disclosure recognize that reviewing collections of documents may be burdensome and inefficient. The following describes systems and methods of selecting and providing one or more representative documents for an input collection of documents. The representative documents may improve the efficiency and accuracy of reviewing a large collection of documents.

FIG. 1illustrates a system100for providing representative documents for an input set of documents, according to certain embodiments. System100includes a person110, client systems120, a computer system130, and a network140. Person110utilizes client systems120to provide an input document set102to computer system130and receive an output representative document set106for input document set102back from computer system130. Network140communicatively couples client systems120and computer system130. In certain embodiments, system100may include more than one network140, or may not include a network140at all.

In general, person110interacts with computer system130in order to receive output representative document set106for an input document set102. Input document set102may be any collection of documents101. Input document set102may include any number of documents101(e.g., ten, one hundred, one million, etc.). As an example for illustrative purposes only, input document set102may be a collection of one hundred documents101that person110wishes to analyze. Person110transmits or otherwise indicates input document set102to computer system130. Computer system130analyzes input document set102and determines one or more representative documents103from input document set102. Computer system130then transmits or otherwise indicates one or more representative documents103to person110as output representative document set106.

In some embodiments, person110transmits or otherwise indicates an input representative document set104to computer system130along with input document set102. Input representative document set104may include one or more representative documents103that person110has identified as being representative of input document set102. For example, as illustrated inFIG. 1, person110indicated two input representative documents103:103aand103b. Computer system130utilizes input representative document set104in order to locate one or more additional representative documents103(i.e., representative documents103c-103nas illustrated inFIG. 1) for input document set102. Computer system130then provides output representative document set106, which may include the input representative documents103along with the additional representative documents103discovered by computer system130.

In some embodiments, person110may provide an indication108of a number of desired representative documents103for input document set102. For example, person110may provide via indication108that he would like to be provided ten representative documents103for input document set102. Computer system130processes input document set102(and any input representative documents103) using the methods described below to output ten representative documents103in output representative document set106.

Client system120may be any electronic device including hardware, software, or embedded logic components or a combination of two or more such components and capable of carrying out the appropriate functionalities implemented or supported by client system120. As an example and not by way of limitation, a client system120may include a computer system such as a desktop computer, notebook or laptop computer, netbook, a tablet computer, e-book reader, GPS device, camera, personal digital assistant (PDA), handheld electronic device, cellular telephone, smartphone, other suitable electronic device, or any suitable combination thereof. This disclosure contemplates any suitable client systems120. A client system120may enable person110to access network140and interact with computer system130.

In particular embodiments, client system120may include a web browser, such as MICROSOFT INTERNET EXPLORER, GOOGLE CHROME, or MOZILLA FIREFOX, and may have one or more add-ons, plug-ins, or other extensions. A user of client system120may enter a Uniform Resource Locator (URL) or other address directing the web browser to a particular server, and the web browser may generate a Hyper Text Transfer Protocol (HTTP) request and communicate the HTTP request to server. The server may accept the HTTP request and communicate to client system120one or more Hyper Text Markup Language (HTML) files responsive to the HTTP request. Client system120may render a webpage based on the HTML files from the server for presentation to person110.

Computer system130may be any suitable computing system in any suitable physical form. As example and not by way of limitation, computer system130may be a virtual machine (VM), an embedded computer system, a system-on-chip (SOC), a single-board computer system (SBC) (e.g., a computer-on-module (COM) or system-on-module (SOM)), a desktop computer system, a laptop or notebook computer system, a mainframe, a mesh of computer systems, a server, an application server, or a combination of two or more of these. Where appropriate, computer system130may include one or more computer systems130; be unitary or distributed; span multiple locations; span multiple machines; or reside in a cloud, which may include one or more cloud components in one or more networks. Where appropriate, one or more computer systems130may perform without substantial spatial or temporal limitation one or more steps of one or more methods described or illustrated herein. As an example and not by way of limitation, one or more computer systems130may perform in real time or in batch mode one or more steps of one or more methods described or illustrated herein. One or more computer systems130may perform at different times or at different locations one or more steps of one or more methods described or illustrated herein, where appropriate. A particular embodiment of computer system130is described in more detail below in reference toFIG. 5.

Network140may refer to any interconnecting system capable of transmitting audio, video, signals, data, messages, or any combination of the preceding. Network115may include all or a portion of a public switched telephone network, a public or private data network, a local area network (LAN), an ad hoc network, a personal area network (PAN), a metropolitan area network (MAN), a wide area network (WAN), a local, regional, or global communication or computer network such as the Internet, an enterprise intranet, or any other suitable communication link, including combinations thereof. One or more portions of one or more of these networks may be wired or wireless. Example wireless networks140may include a wireless PAN (WPAN) (e.g., a BLUETOOTH WPAN), a WI-FI network, a WI-MAX network, a cellular telephone network (e.g., a Global System for Mobile Communications (GSM) network), or other suitable wireless network or a combination of two or more of these.

In operation, computer system130analyzes input document set102in order to determine one or more representative documents103. A representative document103is any document within input document set102that helps provide an accurate view of the breadth and depth of input document set102. Representative documents103are determined according to the algorithms described below in reference toFIGS. 3a-4. For example,FIGS. 3a-3billustrate a method300that may be used to determine one or more representative documents103for a large input document set102, andFIG. 4illustrates a method400that may be used to determine one or more representative documents103for a small input document set102.

FIGS. 2a-2killustrate graphical depictions of documents101, according to certain embodiments.FIG. 2aillustrates seven documents101(e.g.,101a-101g). Each document101is represented as a two dimensional vector and is plotted as a dot on the illustrated graph. In this example, a task may be to select a single representative document103for documents101a-101f. A question may arise as to which document101should be selected as the first representative document:101aor101b? If only one document101is to be selected as a representative document for the collection in the graph, document101bshould be selected as a better representation of the collection than document101a. In this example, document101ais an outlier that does not have much in common with the other documents101in the collection. Document101b, on the other hand, is very similar to most other documents101in the collection and is a good representation of more documents101in the collection than document101a.

After selecting document101bas the first representative document103inFIG. 2a, a task may arise to select the second best representative document103in the collection. For example,FIG. 2billustrates the collection ofFIG. 2aafter selecting document101bas the first representative document103a. Given that document101bwas already selected to be the first representative document103a, a question may arise as to which document to select as the second best representative document103: document101aor101c? In this case, since101bis already a representative document103, and101cis very similar to101b, document101aprovides a deeper understanding of the overall collection more than101cand should be selected as the second representative document103.

FIG. 2cillustrates sixteen documents101from input document set102plotted on a graph. In this example, four selected representative document103are illustrated: representative documents103a-103d. In this example, documents101from input document set102are clustered into four distinct groups. Thus, representative documents103a-103daccurately capture the breadth and depth of documents101in input document set102.

Embodiments of the disclosure utilize various algorithms for determining representative document103. Stated graphically, one way to find representative documents103would be to find the natural clusters of documents101in the collection, and then find the documents101closest to the centroids of those clusters. Two dimensional clusters, particularly well defined clusters like those illustrated inFIGS. 2a-2c, provide a graphically way to visualize finding dots close to centers of clumps of dots (i.e., documents101). Embodiments of the disclosure use some of the components of clustering in algorithms to select representative documents103. In particular, algorithms of certain embodiments utilize two techniques from clustering for finding representative documents103: 1) techniques for evaluating the quality of a solution; and 2) techniques for selecting higher quality candidate documents. These two techniques are described in more detail below.

First, certain embodiments evaluate the quality of a solution. To find the best solution, an objective measure of the quality of a candidate solution is used. For example, minimizing the distance from each document101to the nearest cluster centroid may be used. In certain embodiments, this may involve minimizing the standard deviation from all documents101to the nearest representative document103. Stated in other words, the measure that is being minimized is the document candidate.

Second, certain embodiments select higher quality candidate documents101. When selecting a candidate document101as a representative document103for small input document sets102, some embodiments compare all documents101in the set102to each other to find the best one to select (e.g., method400below). However, this may quickly become too expensive (e.g., take too much time or computing resources). Once there are too many documents101to compare to each other, certain embodiments utilize a k-means++ probabilistic seed selection algorithm to select candidate documents101(e.g., method300below). In general, several probable candidate documents101are identified, and their affect on solution quality is evaluated so the best candidate document101may be selected as the next representative document103to add to output representative document set106.

The k-means++ probabilistic seed selection algorithm makes the odds of a document101being picked as a candidate document proportional to that document's distance from the nearest representative document103. If a particular document101is already one of the representative documents103, the probability of it being selected as the next representative document103is zero. While some embodiment may manually exclude representative documents103from candidate selection, the math behind candidate selection will automatically exclude the representative documents103. This method of candidate selection makes it likely that the next candidate will be selected from a large cluster of documents101that is the furthest away from all of the current representative documents103.

FIG. 2dillustrates probabilistic seed selection and standard deviation quality assessment being used together to pick representative documents103from input document set102. In this example, four documents101have been randomly selected: documents101a-101d. Since no representative documents103have been selected yet, the candidates were selected completely at random. Next, each candidate is tested to see what the Euclidean distance standard deviation would be if the candidate was selected as the first representative document103. For example,FIG. 2eillustrates the candidate with the best score (e.g., document101d). That candidate becomes the first representative document103aselected.

FIG. 2fillustrates the probability of selecting candidates from each cluster of documents. As discussed above, the probability of any particular document101being selected as a candidate is proportional to its distance from the nearest representative document103. In the illustrated example ofFIG. 2f, documents101are clustered into four clusters: clusters210a-210d. The probabilities that documents101in clusters210a-210dwill be selected by the k-means++ probabilistic seed selection algorithm are as follows.Group210a(low probability): While there are many documents101in group210a, all are very close to the representative document103a. So the overall probability that any one of these candidates is picked as a candidate is low.Group210b(medium probability): Group210bis very far away from representative document103a, but only has one document in the group. So group210bonly has a medium probability of being a candidate.Group210c(medium probability): Group210cis not as far away from representative document103aas Group210b, but it has contains a few documents. This gives it roughly the same odds of contributing a candidate as Group210b.Group210d(high probability): Group210dcontains several documents that are just as far away from representative document103aas the document101in Group210b. By virtue of containing many distant documents101from representative document103a, there is a high probability that candidate documents will be selected from Group210d.

When the k-means++ probabilistic seed selection is used to select candidate documents101, each document101is assigned its own probability proportional to its distance from the nearest representative document103a. The probabilistic seed selection tends to find documents101that represent clusters of documents that are most distinct from the current set of representative documents103. Based on the probabilities of each document101, four candidates were randomly selected as illustrated inFIG. 2g. In this example, documents220a-220dwere selected as candidates and may form a subset of documents such as subset345discussed below.

After selecting candidate documents220a-220d, the candidates may be evaluated to select a second representative document103.FIG. 2hillustrates the selection of a second representative document103b. More rounds of probabilistic seed selection and identification of the best representative document out of each set of candidates may be performed to select additional representative documents.FIG. 2iillustrates the selection of additional representative documents103c-103e.

As discussed above, probabilistic seed selection is used in certain embodiments for calculating the probability that each document101should be a candidate. In some embodiments, the distance between documents may refer to the square of the Euclidean distance. Thus the distance from a document101to the nearest representative document103is actually the square of the Euclidean distance between a document and the nearest representative document103. To calculate the probability that each document101should be used as a candidate, certain embodiments first calculate Total, where Total is the sum of the distances from each document101to the nearest representative document103. Equation 1 below illustrates a formula for calculating Total:

Total=∑d∈D⁢minr∈R⁢d-r2(Equation⁢⁢1)
Here, D is the input set of documents101(e.g., input document set102), R is the set of representative documents103already selected from D, d is a vector of a document101in D, and r is a vector of a representative document103in R. Once Total is calculated, the probability for a particular document d in D being selected as a candidate may be calculated by Equation 2 below:

FIGS. 2jand2killustrate the probabilities of candidates being selected from a set of documents.FIG. 2jillustrates four sets of documents: sets230a-230d. After computing Total from Equation 1 above, it may be visualized as a number line as illustrated inFIG. 2k. In this example, each set230occupies some space on a number line proportional to the sum of the probabilities of each document in that set being selected as a candidate. If a random point on the line is selected at random, it is clear how the probability varies for which set230that random number appears in. Each sets230is divided into the real estate that each document101owns on the number line, and a random number may then select a specific document101.

FIGS. 3aand3billustrate an example method300for providing representative documents103for an input document set102. In some embodiments, method300may be used on large collections of documents101. For example, method300may be used to provide one or more representative documents103for an input document set102that contains one hundred or more documents101or over one million documents101. As used herein, a large collection of documents101refers to any number of documents101that may take an undesired amount of time or computing resources to process using other methods such as method400described in more detail below.

In general, method300accesses input from person110and outputs one or more representative documents103. The input from person110may include one or more of input document set102(which includes documents101), input representative document set104(which may include one or more input representative documents103), and an indication108of how many representative documents103are desired as output. Certain embodiments of method300then perform the following general steps to select one or more documents101in input document set102as representative documents103:1. If input representative document set104is empty, initialize the system as if there is only one representative document103that is an equal distance from every document101in the system. Otherwise, for each document101in the full set, calculate and record the minimum distance to a document in the representative document set. (Distance is Euclidean distance squared.)2. Select a predetermined number of candidates using k-means++ probabilistic seed selection. For example, select 256, 1024, or any other appropriate number of candidates.3. Calculate which candidate produces the lowest Total (see Equation 1 above) when added to the current list of representative documents103.4. Add the best candidate from step 3 to the current list of representative documents103.5. Update the minimum distance from each document101to a representative document103to reflect the candidate that was added.6. Repeat steps 2 through 5 until the desired number of additional representative documents have been selected. For example, if person110indicated with indication108that he desired ten representative documents103, repeat steps 2-5 nine more times.

Returning toFIGS. 3aand3bfor more specificity, certain embodiments of method300begin in step310where an input document set “D” is accessed. In some embodiments, D may be input document set102described above. In certain embodiments, D may contain any number of documents “d” (e.g., documents101a-101n). In some embodiments, an input representative document set “R” is also accessed in step310. For example, R may refer to input representative document set104described above and may include input representative documents “r” such as input representative documents103a-103b. In certain embodiments, R may be empty and not contain any input representative documents r.

In step320, a term-document matrix (TDM) is generated from D and R accessed in step310. For example, TDM325as illustrated inFIG. 3amay be generated in step320from D and R. The TDM generated in step320is a matrix where each d is represented by a vector indicating the terms found in that d. While any TDM may be generated by step320, better TDMs will produce better results. Standard techniques like tf-idf or log-entropy weighting for the vectors in the TDM may be utilized in step320to improve results. More details about specific techniques which may be used to produce an improved TDM may be found in U.S. patent application Ser. No. 13/326,284 (“Multi-Concept Latent Semantic Analysis Queries”) which is incorporated herein by reference. Some embodiments may also utilize techniques like fast phrase identification and fast boilerplate removal to create term vocabularies that include high quality phrases, and to produce term vectors focused on real content instead of meaningless boilerplate language. More details about specific techniques to create term vocabularies that include high quality phrases may be found in U.S. patent application Ser. No. 13/326,120 (“System and Method for Identifying Phrases in Text”) which is incorporated herein by reference.

In step330, a distance from each d in D to a closest r in R is calculated and recorded. In some embodiments, the distance refers to the square of a Euclidean distance and the square of the Euclidean distance from each d in D to a closest r in R may be found using Equation 3 below:

In step340, a candidate subset “C” is selected from D. C (e.g., subset345) includes candidates “c” (e.g.,341a-341n), which are documents d selected from D. In some embodiments, any appropriate algorithm for choosing initial seed values may be used to select C. In some embodiments, the algorithm used in step340is the k-means++ probabilistic seed selection according to Equations 4 and 5 below:

Total=∑d∈D⁢minr∈R⁢d-r2(Equation⁢⁢4)PROBABILITY=minr∈R⁢d-r2Total(Equation⁢⁢5)
Here, PROBABILITY is the probability for a particular d in D being selected as a candidate c. PROBABILITY is calculated for each d in D step340by dividing that document's minimum Euclidean distance (calculated in step330) by Total. The sum of the PROBABILITY values for all documents d should be one.

After calculating PROBABILITY for each d in D, candidates c are selected at random using the calculated PROBABILITY scores. To visualize this, consider every document d being laid out on a number line from zero to one, occupying space proportional to its PROBABILITY on the number line (e.g.,FIG. 2k). If a value is picked at random (using a selection method where any point on the number line is equally likely) that is somewhere between 0 and 1, the document that owns the point on the number line is selected as a candidate c. The following is an example algorithm for accomplishing the random selection of candidates c using random values:

Let P(i) be the PROBABILITY that document di is selected

where di is in D.

Let v=a random value between 0 and 1.

The above algorithm selects a single candidate c. However, this algorithm may be run multiple times to select many candidates c (e.g., 256 times). Some embodiments may check to make sure unique candidates are being selected, and if not, continue selecting candidates until the desired number of unique candidates are selected.

Steps350-370are repeated for each c in C. For example, if there are 256 candidates c in C, steps350-370are repeated 256 times. In step350, the first c in C is added to R to produce set “Rc” as illustrated inFIG. 3bas set355. (The second time through steps350-370, the second c in C is added to R to produce set Rc, and so forth.) Rc includes representative documents “rc” (e.g.,356a-356n), which are any representative documents103input by person110in input representative document set104or any representative documents103previously chosen by method300, plus c that was added in step350. Also in step350, the first c in C is removed from D to produce set “Dc” as illustrated inFIG. 3bas set357. (The second time through steps350-370, the second c in C is removed from D to produce Dc, and so forth.) Dc includes documents “dc” (e.g.,358a-358n), which are all of documents101in input document set102minus c that was removed in step350.

In step360, a distance is calculated from every dc in Dc to every rc in Rc. In some embodiments, the distance is the Euclidean distance squared. For each dc in Dc, step360locates the rc that is the minimum Euclidean distance squared according to Equation 6 below:

In step370, TOTALc for each dc in Dc is calculated according to Equation 7 below:

TOTALc=∑d⁢⁢c∈Dc⁢minrc∈Rc⁢d⁢⁢c-rc2(Equation⁢⁢7)
In step380, the c in C that resulted in the lowest TOTALc in step370is selected as a representative document103. The selected c is then moved from D to R.

After step380, certain embodiments may update the distances calculated in step330from each d in D to a closest r in R in order to reflect the new representative document103that was selected in step380. Steps340-380may then be repeated as many times as desired according to how many representative documents103are desired. For example, if ten additional representative documents103are desired, steps340-380may be repeated ten times. After the desired amount of representative documents103are found for input document set102, method300may transmit or otherwise indicate output representative document set106to person110.

FIG. 4illustrates an example method400for providing representative documents103for an input document set102. In some embodiments, method400may be used on small collections of documents101. For example, method400may be used to provide one or more representative documents103for an input document set102that contains one hundred documents101or fewer. As used herein, a small collection of documents101refers to any number of documents101that may be processed using method400in a desired amount of time.

In general, method400accesses input from person110and outputs one or more representative documents103. The input from person110may include one or more of input document set102(which includes documents101) and an indication108of how may representative documents103are desired as output. Certain embodiments of method400then perform the following general steps to select one or more documents101in input document set102as representative documents103:1. Use every document that is not already a representative document as a candidate for the next representative document (first time through this is all of the documents).2. Calculate which candidate produces the lowest Total (see Equation 1 above) when added to the current list of representative documents103.3. Add the best candidate from step 3 to the current list of representative documents103.4. Update the minimum distance from each document101to a representative document103to reflect the candidate that was added.5. Repeat steps 1 through 4 until the desired number of additional representative documents have been selected. For example, if person110indicated with indication108that he desired ten representative documents103, repeat steps 1-4 nine more times.

Returning toFIG. 4for more specificity, certain embodiments of method400begin in step410where an input document set “D” is accessed. In some embodiments, D may be input document set102described above. In certain embodiments, D may contain any number of documents “d” (e.g., documents101a-101n).

In step420, a TDM is generated from D accessed in step410. The TDM generated in step420is a matrix where each d is represented by a vector indicating the terms found in that d. As discussed above, standard techniques like tf-idf or log-entropy weighting for the vectors in the TDM may be utilized in step420to improve results. Some embodiments may also utilize techniques like fast phrase identification and fast boilerplate removal to create term vocabularies that include high quality phrases, and to produce term vectors focused on real content instead of meaningless boilerplate.

Steps430-450are repeated for each d in D. For example, if there are 100 documents d in D, steps430-450are repeated 100 times. In step430, the first d in D is added to R to produce set “Rc” as illustrated inFIG. 4as set435. (The second time through steps430-450, the second d in D is added to R to produce set Rc, and so forth.) Rc includes representative documents “rc” (e.g.,436a-436n), which may be any representative documents103input by person110in input representative document set104or any representative documents103previously chosen by method300, plus d that was added in step430. Also in step430, the first d in D is removed from D to produce set “Dc” as illustrated inFIG. 4as set437. (The second time through steps430-450, the second d in D is removed from D to produce Dc, and so forth.) Dc includes documents “dc” (e.g.,438a-438n), which are all of documents101in input document set102minus d that was removed in step430.

In step440, a distance is calculated from every dc in Dc to every rc in Rc. In some embodiments, the distance is the Euclidean distance squared. For each dc in Dc, step360locates the rc that is the minimum Euclidean distance squared according to Equation 8 below:

In step450, TOTALc for each dc in Dc is calculated according to Equation 9 below:

TOTALc=∑d⁢⁢c∈Dc⁢minrc∈Rc⁢d⁢⁢c-rc2(Equation⁢⁢9)
In step460, the d in D that resulted in the lowest TOTALc in step450is selected as a representative document103. The selected d is then moved from D to R.

After step460, certain embodiments of method400may update the distances from each d in D to a closest r in R in order to reflect the new representative document103that was selected in step450. Steps430-460may then be repeated as many times as desired according to how many representative documents103are desired. For example, if ten additional representative documents103are desired, steps430-460may be repeated ten times. After the desired amount of representative documents103are found for input document set102, method400may transmit or otherwise indicate output representative document set106to person110.

FIG. 5illustrates an example computer system500. Computer system500may be utilized by computer system130ofFIG. 1. In particular embodiments, one or more computer systems500perform one or more steps of one or more methods described or illustrated herein. In particular embodiments, one or more computer systems500provide functionality described or illustrated herein. In particular embodiments, software running on one or more computer systems500performs one or more steps of one or more methods described or illustrated herein or provides functionality described or illustrated herein. Particular embodiments include one or more portions of one or more computer systems500. Herein, reference to a computer system may encompass a computing device, and vice versa, where appropriate. Moreover, reference to a computer system may encompass one or more computer systems, where appropriate.

In particular embodiments, computer system500includes a processor502, memory504, storage506, an input/output (I/O) interface508, a communication interface510, and a bus512. Although this disclosure describes and illustrates a particular computer system having a particular number of particular components in a particular arrangement, this disclosure contemplates any suitable computer system having any suitable number of any suitable components in any suitable arrangement.

In particular embodiments, processor502includes hardware for executing instructions, such as those making up a computer program. As an example and not by way of limitation, to execute instructions, processor502may retrieve (or fetch) the instructions from an internal register, an internal cache, memory504, or storage506; decode and execute them; and then write one or more results to an internal register, an internal cache, memory504, or storage506. In particular embodiments, processor502may include one or more internal caches for data, instructions, or addresses. This disclosure contemplates processor502including any suitable number of any suitable internal caches, where appropriate. As an example and not by way of limitation, processor502may include one or more instruction caches, one or more data caches, and one or more translation lookaside buffers (TLBs). Instructions in the instruction caches may be copies of instructions in memory504or storage506, and the instruction caches may speed up retrieval of those instructions by processor502. Data in the data caches may be copies of data in memory504or storage506for instructions executing at processor502to operate on; the results of previous instructions executed at processor502for access by subsequent instructions executing at processor502or for writing to memory504or storage506; or other suitable data. The data caches may speed up read or write operations by processor502. The TLBs may speed up virtual-address translation for processor502. In particular embodiments, processor502may include one or more internal registers for data, instructions, or addresses. This disclosure contemplates processor502including any suitable number of any suitable internal registers, where appropriate. Where appropriate, processor502may include one or more arithmetic logic units (ALUs); be a multi-core processor; or include one or more processors502. Although this disclosure describes and illustrates a particular processor, this disclosure contemplates any suitable processor.

In particular embodiments, memory504includes main memory for storing instructions for processor502to execute or data for processor502to operate on. As an example and not by way of limitation, computer system500may load instructions from storage506or another source (such as, for example, another computer system500) to memory504. Processor502may then load the instructions from memory504to an internal register or internal cache. To execute the instructions, processor502may retrieve the instructions from the internal register or internal cache and decode them. During or after execution of the instructions, processor502may write one or more results (which may be intermediate or final results) to the internal register or internal cache. Processor502may then write one or more of those results to memory504. In particular embodiments, processor502executes only instructions in one or more internal registers or internal caches or in memory504(as opposed to storage506or elsewhere) and operates only on data in one or more internal registers or internal caches or in memory504(as opposed to storage506or elsewhere). One or more memory buses (which may each include an address bus and a data bus) may couple processor502to memory504. Bus512may include one or more memory buses, as described below. In particular embodiments, one or more memory management units (MMUs) reside between processor502and memory504and facilitate accesses to memory504requested by processor502. In particular embodiments, memory504includes random access memory (RAM). This RAM may be volatile memory, where appropriate Where appropriate, this RAM may be dynamic RAM (DRAM) or static RAM (SRAM). Moreover, where appropriate, this RAM may be single-ported or multi-ported RAM. This disclosure contemplates any suitable RAM. Memory504may include one or more memories504, where appropriate. Although this disclosure describes and illustrates particular memory, this disclosure contemplates any suitable memory.

In particular embodiments, storage506includes mass storage for data or instructions. As an example and not by way of limitation, storage506may include a hard disk drive (HDD), a floppy disk drive, flash memory, an optical disc, a magneto-optical disc, magnetic tape, or a Universal Serial Bus (USB) drive or a combination of two or more of these. Storage506may include removable or non-removable (or fixed) media, where appropriate. Storage506may be internal or external to computer system500, where appropriate. In particular embodiments, storage506is non-volatile, solid-state memory. In particular embodiments, storage506includes read-only memory (ROM). Where appropriate, this ROM may be mask-programmed ROM, programmable ROM (PROM), erasable PROM (EPROM), electrically erasable PROM (EEPROM), electrically alterable ROM (EAROM), or flash memory or a combination of two or more of these. This disclosure contemplates mass storage506taking any suitable physical form. Storage506may include one or more storage control units facilitating communication between processor502and storage506, where appropriate. Where appropriate, storage506may include one or more storages506. Although this disclosure describes and illustrates particular storage, this disclosure contemplates any suitable storage.

The components of computer system500may be integrated or separated. In some embodiments, components of computer system500may each be housed within a single chassis. The operations of computer system500may be performed by more, fewer, or other components. Additionally, operations of computer system500may be performed using any suitable logic that may comprise software, hardware, other logic, or any suitable combination of the preceding.