Method and system for visualizing documents

Method and system for visualizing documents. N-dimensional compact representations are obtained for a set of documents. A plurality of documents are then retrieved with the corresponding N-dimensional compact representations. Each of the retrieved documents is associated with at least one concept. Each of the retrieved documents is projected to a point on a K-dimensional map based on its N-dimensional compact representation so that projected document points in the K-dimensional map maintain the relative distances among the retrieved documents in the N-dimensional space. Regions in the K-dimensional map associated with a concept are identified. A label is generated for each concept in each identified region. Then generated labels are rendered on the K-dimensional map in a corresponding region identified.

BACKGROUND

1. Technical Field

The disclosure relates generally to a method and system for visualization.

2. Discussion of Technical Background

An information search and retrieval system locates relevant documents stored in a media and renders the documents in a result set in response to a query. The query may come from a user input, and the retrieved documents may be rendered in a ranked order to the user based on relevance, time, or other criteria. To help a user to quickly identify main concepts within the result set, various visualization techniques have been implemented to display retrieved documents in a two-dimensional space.

Due to the computational complexity and limited effectiveness of projecting documents from a high dimensional term space to a two-dimensional space, an intermediate procedure has been applied to reduce the number of dimensions involved in the projection process. Document classification has been applied to classify retrieved documents into predefined classes, the number of which is smaller than the number of terms in the documents. The classes are projected to a two-dimensional map, and the documents are then placed with regard to classes on the two-dimensional map. Document clustering provides another way to reduce the dimensionality by grouping retrieved documents into clusters. The cluster centers are projected to a two-dimensional map and documents are placed with regard to the cluster centers on the two-dimensional map. The rendered map in both document classification and document clustering identifies main concepts, by class and cluster labels respectively.

However, there are some drawbacks in both techniques of document classification and document clustering. First, the semantic relatedness between documents is not clearly represented on the two-dimensional map, so that documents close to each other are not necessarily more related than those placed apart. Second, the choice of cluster or class in which to classify a particular document may appear arbitrary when the document includes multiple topics represented by different clusters/classes and/or when multiple clusters/classes describe similar topics. Third, the placement of a label representing main concepts does not take into account the global distribution of concepts across classes/clusters on the two-dimensional map. So the concepts that occur in documents scattered in multiple classes/clusters are likely under-represented, i.e., not significant enough to be selected as labels.

Accordingly, there exists a need for a document visualization technique to overcome the above drawbacks.

SUMMARY

The present disclosure describes methods, system, and programming for visualizing documents.

In one exemplary embodiment, a method, implemented on at least one machine having at least one processor, storage, and a communication platform connected to a network for visualizing documents, is provided. N-dimensional compact representations are obtained for a set of documents. A plurality of documents are then retrieved with the corresponding N-dimensional compact representations. Each of the retrieved documents is associated with at least one concept. Each of the retrieved documents is projected to a point on a K-dimensional map based on its N-dimensional compact representation so that projected document points in the K-dimensional map maintain the relative distances among the retrieved documents in the N-dimensional space. Each region associated with a concept is identified in the K-dimensional map. A label is generated for each concept in each region identified. Then one or more of the generated labels are rendered on the K-dimensional map in corresponding regions identified.

In another exemplary embodiment, a method, implemented on at least one machine having at least one processor, storage, and a communication platform connected to a network for document retrieval and visualization, is provided. A query is received from a user via the communication platform. A plurality of documents are then retrieved based on the query. Each of the retrieved documents is represented by an N-dimensional compact representation and associated with at least one concept. Each of the retrieved documents is projected to a point on a K-dimensional map based on its N-dimensional compact representation so that projected document points in the K-dimensional map maintain the relative distances among the retrieved documents in the N-dimensional space. Each region associated with a concept is identified in the K-dimensional map. A label is generated for each concept in each region identified. Then a rendition of the K-dimensional map is transmitted, as a response to the query via the communication platform, with the plurality of documents projected therein and having one or more of the generated labels rendered in corresponding regions identified on the map.

In still another exemplary embodiment, a method, implemented on at least one machine having at least one processor, storage, and a communication platform connected to a network for document retrieval and visualization, is provided. A first query is received from a user via the communication platform. A plurality of documents are then retrieved based on the first query. Each of the retrieved documents is represented by an N-dimensional compact representation and associated with at least one concept. Each of the retrieved documents is projected to a point on a K-dimensional map based on its N-dimensional compact representation so that projected document points in the K-dimensional map maintain the relative distances among the retrieved documents in the N-dimensional space. Each region associated with a concept is identified in the K-dimensional map. A rendition of the K-dimensional map is transmitted, as a response to the first query, with the plurality of documents projected therein and each label generated for a concept and rendered in a corresponding region identified. Then a second query is automatically generated based on an interaction of the user with the K-dimensional map. At least one new document is retrieved, based on the second query. Each of the at least one new document is represented by an N-dimensional compact representation, and associated with at least one concept. Each of the at least one new document is projected to a newly projected document point on the K-dimensional map based on its N-dimensional compact representation so that the projected document points and the at least one newly projected document point maintain the relative distances in the N-dimensional space. Each region associated with a concept is identified in the K-dimensional map. A new label is generated for each concept in each region identified. One or more of the new labels are rendered in the K-dimensional map to generate an updated K-dimensional map. A rendition of the updated K-dimensional map is transmitted, as a response to the interaction of the user with the K-dimensional map.

In yet another exemplary embodiment, a method, implemented on at least one machine having at least one processor, storage, and a communication platform connected to a network for visualizing documents, is provided. N-dimensional compact representations are obtained for a set of documents. A plurality of documents are then retrieved with the corresponding N-dimensional compact representations. Each of the retrieved documents is associated with at least one concept. Each point or subspace associated with a concept is identified in the N-dimensional space. Each of the retrieved documents and points or subspaces associated with concepts, is projected to a point or a region on a K-dimensional map based on its N-dimensional representation so that projected document points and points or subspaces associated with concepts in the K-dimensional map maintain the relative distances among the retrieved documents and points or subspaces associated with concepts in the N-dimensional space. A label is generated for each concept in each region projected from an identified subspace. Then one or more of the generated labels are rendered on the K-dimensional map in corresponding regions.

DETAILED DESCRIPTION

Reference will now be made in detail to the embodiments of the present disclosure, examples of which are illustrated in the accompanying drawings. While the present disclosure will be described in conjunction with the embodiments, it will be understood that they are not intended to limit the present disclosure to these embodiments. On the contrary, the present disclosure is intended to cover alternatives, modifications, and equivalents, which may be included within the spirit and scope of the present disclosure as defined by the appended claims.

In addition, in the following detailed description of embodiments of the present disclosure, numerous specific details are set forth in order to provide a thorough understanding of the present disclosure. However, it will be recognized by one of ordinary skill in the art that the present disclosure may be practiced without these specific details. In other instances, well-known methods, procedures, components, and circuits have not been described in detail as not to unnecessarily obscure aspects of the embodiments of the present disclosure.

Various embodiments in accordance with the present disclosure provide a method and a system for semantic information search and retrieval. More specifically, the method and system in various embodiments of the present disclosure relate to visualization of concepts contained in one or more documents. The documents may be in a result set in response to a user input query. User queries may be in the form of one or more keywords, one or more paragraphs of descriptive text, or one or more full text documents. User queries may also be in the form of document meta information, which includes but is not limited to the author, the affiliation, the ownership, the time of creation, etc.

The method and system in various embodiments of the present disclosure are described for helping users visually analyze a set of documents and find documents with the concepts of interest within a plurality of documents. The set of documents may be any large or small corpus of documents with text content, such as legal collections, archives of technical journals, corporate or personal archive of documents, Internet forum posts, or all text documents on the World Wide Web (Internet). The method and system in various embodiments of the present disclosure allows a user to perform a search for a plurality of documents retrieved from a set of documents based on the search, and to visualize the concepts covered in the retrieved documents. The retrieved documents may be rendered on a K-dimensional semantic map. The distance between any pair of documents on the map represents semantic relatedness of the documents, such that similar or related documents are close to one another on the map. Various regions on the map are labeled with concepts contained in documents in the underlying regions. The method and system in various embodiments of the present disclosure also allows a user to visualize the main concepts covered by a set of documents without entering a query, to browse and navigate to a subset of documents covering specific concepts of interest, and to perform iterative search, exploration, and analysis.

In accordance with various embodiments of the present disclosure, a dimension reduction technique is applied to each document to create one or more semantic compact codes that retain the meaning of the document and have much lower dimensionality than the term space. The compact representations of the documents are applied in a projecting process, during which documents that are more semantically related to each other are placed closer on the rendered K-dimensional map than those that are less related. Concepts are placed on the K-dimensional map based on the global distribution of documents containing the concepts.

Additional novel features will be set forth in part in the description which follows, and in part will become apparent to those skilled in the art upon examination of the following and the accompanying drawings or may be learned by production or operation of the examples.

FIG. 1illustrates one exemplary embodiment of a system100for visualizing documents, in accordance with one embodiment of the present disclosure. The system100may include a document abstraction unit102, a document representation database103, a document retrieving unit104, a document mapping unit106, and a document visualization unit108, in accordance with one embodiment of the present disclosure. The document abstraction unit102may be configured to receive a set of documents101and generate and archive an N-dimensional compact representation and a set of relevant concepts for each document in the document representation database103. The document representation database103may be operatively coupled to the document abstraction unit102and the document retrieving unit104. The document retrieving unit104may be configured to retrieve certain documents and the corresponding N-dimensional compact representations and relevant concepts, from the document representation database103. The document mapping unit106may be operatively coupled to the document retrieving unit104and configured to project each of the retrieved documents to a point on a K-dimensional map based on its N-dimensional compact representation, and identify each region in the map where a density of projected document points associated with a concept is larger than a predetermined threshold. In some exemplary embodiments, the projected document points in the K-dimensional map maintain the relative distances among the retrieved documents in the N-dimensional space. In some exemplary embodiments, N is larger than K, and K is one of two and three. The document visualization unit108may be operatively coupled to the document retrieving unit104and the document mapping unit106, and configured to render a map visualizing the retrieved documents and their associated concepts in each identified region.

In some exemplary embodiments, a display device120may be operatively coupled to the system100. In an exemplary embodiment, a display device120may be operatively coupled to the document visualization unit108of the system100, and configured to display the rendered map from the document visualization unit108.

FIG. 2illustrates an exemplary embodiment of the document abstraction unit102and the document representation database103shown inFIG. 1, in accordance with one embodiment of the present disclosure. In this exemplary embodiment, the document abstraction unit102includes a term extracting unit202, a feature-based representation creating unit204, and a compact representation creating unit206. In this exemplary embodiment, the document representation database103includes a feature-based representation database212and a compact representation database214. In this exemplary embodiment, the term extracting unit202is configured to extract a plurality of terms from each of the set of documents101received by the document abstraction unit102. In this exemplary embodiment, the feature-based representation creating unit204is operatively coupled to the term extracting unit202and the feature-based representation database212, and configured to generate a feature-based representation for each of the set of documents101based on the extracted terms. The generated feature-based representations may be stored in the feature-based representation database212. In this exemplary embodiment, the compact representation creating unit206is operatively coupled to the feature-based representation creating unit204and the compact representation database214, and configured to generate, for each of the set of documents101, an N-dimensional compact representation based on the feature-based representation of the document. The generated compact representations may be stored in the compact representation database214. In this exemplary embodiment, the set of documents101is archived along with their respective feature-based representations and N-dimensional compact representations in the document representation database103.

In some exemplary embodiments, a feature-based representation of a document may represent the document's features including, but not limited to, words, phrases, concepts, topics, or locations. In some exemplary embodiments, the feature-based representation is sparse and has a high dimensionality. There may be many possible features, and each document may only have meaningful (non-zero) values for a small number of the many possible features. The feature-based representation may be generated by splitting document text into words or tokens, converting words into word stems, and computing the relative information content of a word or phrase.

In some exemplary embodiments, the N-dimensional compact representation, generated based on the feature-based representation of a document, is denser and has a lower dimensionality than the feature-based representation. In some exemplary embodiments, all elements of the N-dimensional compact representation have meaningful values. Various dimensionality reduction methods can be used to compute the compact representation. Both the feature-based representation and the compact representation of a document are stored in a way to facilitate retrieval.

FIG. 3illustrates an exemplary embodiment of the document retrieving unit104shown inFIG. 1, in accordance with one embodiment of the present disclosure. In this exemplary embodiment, the document retrieving unit104includes a document ranking unit302and a document selecting unit304. The document ranking unit302in this exemplary embodiment is operatively coupled to the document representation database103and configured to determine a metric for each archived document based on some criterion stored in the document retrieving unit104, and archive the metric for each document as metadata with respect to the document in the document representation database103. The document selecting unit304in this exemplary embodiment is operatively coupled to the document representation database103and the document ranking unit302, and configured to retrieve certain documents and their corresponding N-dimensional compact representations based on the metric from the document representation database103. In this exemplary embodiment, the document retrieving unit104is configured to output the retrieved documents with their corresponding N-dimensional compact representations and concepts309.

In some exemplary embodiments, the retrieved documents may be the complete set of archived documents in the document representation database103, or a subset of archived documents in the document representation database103. The subset may include the latest X number of documents in the database103, or the documents containing the top Y concepts in the database103.

FIG. 4is a block diagram illustrating an exemplary embodiment of the document mapping unit106shown inFIG. 1, in accordance with one embodiment of the present disclosure. In this exemplary embodiment, the document mapping unit106has a document projection unit402, a dense region detection unit404, and a label generating unit406. The document projection unit402in this exemplary embodiment is configured to obtain certain documents, their corresponding N-dimensional compact representations, and concepts309associated with the received documents, and project each of the documents as a point on a K-dimensional map based on its N-dimensional compact representation. The dimensionality K may be determined based on the projection dimension parameters403stored in the document mapping unit106. The projection dimension parameters403may include, e.g., two dimensional, three dimensional, determined based on, e.g., the number of points to be projected on to the map. For example, when the number of documents to be projected on the map is high so that it will be much more crowded in a two dimensional map, a three dimensional map may be used to render all the document points. Such a choice of dimensionality may be determined by an administrator or automatically. Addition information may also be used in determining the dimensionality of the map to be used. For example, some meta information of documents may also be considered in determining the dimensionality. Such meta information may include, but is not limited to, the authors, the affiliations, and the document creation time. The projected document points in the K-dimensional map maintain the relative distances among the retrieved documents in the N-dimensional space, such that documents that are close together in the N-dimensional space are also close together in the K-dimensional map space.

The dense region detection unit404in this exemplary embodiment is operatively coupled to the document projection unit402and configured to identify each region in the K-dimensional map where a density of projected document points associated with a concept is larger than a predetermined threshold. In some exemplary embodiments, each region has one or more concepts each associated with document points in the region that has a density larger than the predetermined threshold. The dense region detection unit404also determines the density based on the dimension of the K-dimensional map. As discussed above, the dimensionality of the K-dimensional map can be two or three or even higher, depending on various considerations such as the number of points or other meta information. Once the dimensionality is known, the density may be determined accordingly. For example, the density in a two dimensional map may be the number of points that share the same concept in a squared area. But in a three dimensional map, the density may be measured based on the umber of points in a unit cube.

The label generating unit406in this exemplary embodiment is operatively coupled to the document projection unit402and the dense region detection unit404, and configured to generate a label for each concept associating with document points whose density is larger than the predetermined threshold in each region identified. In this exemplary embodiment, the document mapping unit106is configured to output the constructed K-dimensional map with labels generated in corresponding identified regions409. In some exemplary embodiments, each generated label corresponds to a word, words, a phrase, or a string of characters.

In some embodiments, the label generating unit406may be configured to render different labels in different styles depending on some criteria. For example, a region having a denser population of document points sharing a particular concept, the label for the shared concept may be deemed as more significant than another label representing a concept shared by fewer documents. In this case, a label representing a more significant concept may be rendered with more outstanding features such as boldfaced, a darker color, or a larger font size. In some embodiments, there may be multiple levels of significance in rendering labels, each of which may be associated with a certain style. For example, underlined may be less significant than boldfaced. Red color may be more significant than blue color, etc. In addition to determine the significance of a concept based on the density of points, it may also be determined based on the size of a region that contains documents points sharing the same concept.

In some exemplary embodiments, some of the projected document points on the K-dimensional map may be made actionable to allow a user to activate information associated with the projected document. In some exemplary embodiments, labels rendered on the K-dimensional map may also be made actionable so that when activated, information related to the concept associated with the label may be rendered. A projected document point or a rendered label can be activated under different conditions. For example, a document may be activated when a user places a cursor near to a projected document point or a rendered label; a user may perform a click when the cursor is near a projected document point or a rendered label; or a cursor is placed in a region in the K-dimensional map that is labeled.

In some exemplary embodiments, a dimensionality reduction algorithm that prioritizes reproduction of local distances is utilized to map the compact representation of each document to a point in a K-dimensional map. In accordance with various exemplary embodiments, the dimensionality reduction algorithm may be any existing technologies such as t-distributed stochastic neighbor embedding (t-SNE), elastic embedding, or locally linear embedding.

FIG. 5is a block diagram illustrating an exemplary embodiment of the document visualization unit108shown inFIG. 1, in accordance with one embodiment of the present disclosure. In this exemplary embodiment, the document visualization unit108has a dimension control unit502, a visual interface generating unit504, and a rendering unit506. The dimension control unit502in this exemplary embodiment is configured to receive the constructed K-dimensional map with corresponding labels, and control the dimension of the map based on certain document information or labels, as well as the projection dimension parameters503stored in the document visualization unit108. The visual interface generating unit504in this exemplary embodiment is operatively coupled to the dimension control unit502, and configured to receive the constructed K-dimensional map with corresponding labels and generate a visual interface based on certain document information or labels. The visual interface generating unit504in this exemplary embodiment generates a visual interface based on the projection dimension parameters503stored in the document visualization unit108. The visual interface in this exemplary embodiment is generated to allow a user to interactively control documents and/or labels corresponding to concepts associated with the documents to be rendered on the K-dimensional map. The rendering unit506in this exemplary embodiment is operatively coupled to the dimension control unit502and the visual interface generating unit504, and configured to render the visualized map. In this exemplary embodiment, the document visualization unit108is configured to output the rendered map visualizing the retrieved documents and their associated concepts in each identified region.

In one exemplary embodiment, document points projected on the K-dimensional map are represented by colored dots, where the color indicates some document meta information, which includes but is not limited to, the document creation time, the author of the document, and the owner of the document. For example, a particular outstanding color may be designated to documents that are from a best seller author, with other document points having a more neutral color.

In some exemplary embodiments, a parameter included in the projection dimension parameters503may be used to represent a single dimension in a K-dimensional map. For example, in a three dimensional map (K=3), a dimension parameter corresponding to feature “year” may be used to denote the Z dimension, i.e., documents are to be projected along the Z dimension based on the year information associated with the documents. This is controlled by the dimension control unit502. The projection dimension parameters503may also include other meta information of documents and attributes of the labels relating to concepts. As discussed above, the meta information includes but is not limited to, the authors, the affiliations, and the document creation time. The attribute of a label relating to a concept includes, but is not limited to, the density of the documents associating with the concept in each unit region, the number of documents associating with the concept in a region corresponding to the label or concept, and the size of the region encompassed by the concept. In some exemplary embodiments, the dimension represented by a single attribute may be made interactive in the K-dimensional map with, e.g., a filter or a slider that can be interactively controlled by the visual interface generating unit504.

In some embodiments, the disclosed teaching may also provide a user the capability of interact with the K-dimensional map by allowing a user to zoom in or out a particular region of the K-dimensional map. The K-dimensional map may be rendered on-the-fly based on the user's interaction. For example, if zoom in is desired, the region being zoomed in may be rendered with an enlarged visual appearance and all points and labels in that region may then be rendered with proportionally appropriate sizes. Similarly, zoom out may also be implemented accordingly. When K is larger than 2, the K-dimensional map may also be manipulated via user interaction. For example, a three dimensional map can be rotated, tilted, flipped, as well as zoom in and out so that a user can visualize a specific 3D region in more detail.

FIG. 6is a block diagram illustrating an exemplary embodiment of another system600for visualizing documents, in accordance with one embodiment of the present disclosure. The system600in this exemplary embodiment includes a document abstraction unit602, a document representation database603, a document matching unit604, a document mapping unit606, a document visualization unit608, a query abstraction unit612, and a query representation database613. The document abstraction unit602in this exemplary embodiment is configured to receive a set of documents601, generate, and archive an N-dimensional compact representation for each document in the document representation database603. The query abstraction unit612is configured to receive a query651, generate, and archive an N-dimensional compact representation for the query651in the query representation database613. The document representation database603in this exemplary embodiment is operatively coupled to the document abstraction unit602and the document matching unit604. The query representation database613in this exemplary embodiment is operatively coupled to the query abstraction unit612and the document matching unit604. The document matching unit604in this exemplary embodiment is configured to retrieve certain documents associated with concepts by matching content of the query651with that of the archived documents. The content includes but is not limited to feature-based representations, compact representations, and other meta information. The document mapping unit606in this exemplary embodiment is operatively coupled to the document matching unit604and configured to project each of the retrieved documents to a point on a K-dimensional map based on its N-dimensional compact representation, and identify each region in the map where a density of projected document points associated with a concept is larger than a predetermined threshold. In some exemplary embodiments, the projected document points in the K-dimensional map maintain the relative distances among the retrieved documents in the N-dimensional space. In some exemplary embodiments, N is larger than K, and K is one of two and three. The document visualization unit608in this exemplary embodiment is operatively coupled to the document mapping unit606, and configured to transmit a map visualizing the queried documents and their associated concepts in each identified region, as a response to the query651.

In some exemplary embodiments, the system600processes a query as below. First, the received query is split into query clauses. Then, each query clause is analyzed by computing a feature-based representation and a compact representation for the query clause. Key features from each query clause are utilized to identify possibly relevant documents in the document database. Each possibly relevant document so identified is assigned a score based on a distance between the feature-based compact representation of a query clause and that of the document. The scores for all query clauses are then combined. In case it is desired to use documents with higher scores as more relevant, the documents with a certain number of highest relevance scores may be deemed as the query result. On the other hand, in case it is desirable to use documents satisfying certain time requirements (e.g., more recent in time), the documents retrieved that have more recent time stamps may be returned as query result.

In some exemplary embodiments, the K-dimensional map generated for the query result in response to a query may further be used for an interactive discovery and analysis process. An interactive interface may be implemented that allows the use of interaction tools such as a mouse, a scroll wheel, a sliding zoom control, or a touch screen with a pinching motion to allow a user to perform certain interactions such as zoom into a specific region of the map. The user may use a mouse to click and drag, or if using a touchscreen device, use a finger to touch and drag, to see different regions at the same level of magnification. In some exemplary embodiments, the user may also control what is present in the map by, e.g., modifying a previous query by adding, emphasizing, or discounting concepts which are represented by labels on the map. In addition, the user may add, emphasize, or discount documents on the map. In another exemplary embodiment, the user interaction with the map may be utilized to trigger automated generation of refined query, as will be detailed below in reference toFIG. 13.

In one exemplary embodiment, documents may be represented by colored points on the K-dimensional map, where the color may indicate the relevance of the document to the user's query. In another exemplary embodiment, the relevance of the document to the user's query can be represented as an additional dimension to the K-dimensional map, which results in a (K+1)-dimensional map, in which the documents are projected in the K-dimensional map but along the additional dimension in accordance with their relevance to the query. In another exemplary embodiment, the user may input, through some user interface, certain criteria as to how document points projected into the K-dimensional map need to be colored. For example, while the system may select documents according to relevance in content, a user may specify that the document projected on to the K-dimensional map are colored according to how recent they are, e.g., red denoting the most recent, and black denoting the least recent, etc.

FIG. 7is a flow chart illustrating an exemplary embodiment of a method for visualizing documents, in accordance with one embodiment of the present disclosure. Beginning at710, a set of documents is received. Proceeding to720, an N-dimensional compact representation for each of the set of documents is generated and archived in, e.g., the document representation database103of the system100. As described above,710and720may be performed by, e.g., the document abstraction unit102of the system100. Moving to730, certain documents associated with concepts are retrieved with their corresponding N-dimensional compact representations. As described above,730may be performed by, e.g., the document retrieving unit104of the system100. Proceeding to740, each of the retrieved documents is projected to a point on a K-dimensional map based on its N-dimensional compact representation. Moving to750, each region associated with a concept is identified in the map. In some exemplary embodiments, each region is identified in the map where a density of projected document points associated with a concept is larger than a predetermined threshold. In some exemplary embodiments, the projected document points in the K-dimensional map maintain the relative distances among the retrieved documents in the N-dimensional space. In some exemplary embodiments, N is larger than K, and K is one of two and three. As described above,710and720may be performed by, e.g., the document mapping unit106of the system100. Moving further to760, a map is rendered to visualize the retrieved documents and their associated concepts in each identified region. As described above,760may be performed by, e.g., the document visualization unit108of the system100.

In one exemplary embodiment, following730, each subspace in the N-dimensional space may be identified where a density of compact representations of documents associated with a concept is larger than a predetermined threshold. Then moving to740, each of the retrieved documents is projected to a point on a K-dimensional map based on its N-dimensional compact representation. In this exemplary embodiment, the projected document points in the K-dimensional map maintain the relative distances among the retrieved documents in the N-dimensional space, and each identified subspace in the N-dimensional space is projected to a region in the K-dimensional map along with the underlying concept and features. Then proceeding to760in this exemplary embodiment, a map is rendered to visualize the retrieved documents and their associated concepts in each region projected from an identified subspace.

FIG. 8is a flow chart illustrating an exemplary process performed by the document abstraction unit102, in accordance with one embodiment of the present disclosure. Beginning at810, a set of documents is received. Proceeding to820, a plurality of terms is extracted from each document. As described above,810and820may be performed by, e.g., the term extracting unit202of the document abstraction unit102. In an exemplary embodiment, a PDF document received at the term extracting unit202may be processed with a PDF-to-text conversion application. Then, a stream of word-stem tokens may be obtained by dividing the text into words, converting words to lowercase word stems, and discarding punctuation.

Moving to830, a feature-based representation for each document is generated based on the extracted terms. As described above,830may be performed by, e.g., the feature-based representation creating unit204of the document abstraction unit102. In one exemplary embodiment, a feature-based representation is created by counting the number of times each unique word stem occurs. The dimensionality of the feature-based representation is the word-stem vocabulary of the entire corpus. In another exemplary embodiment, a feature-based representation is created by counting the number of times each unique word stem occurs, and then multiplying the number by the inverse document frequency, i.e., the reciprocal of the log of fraction of the corpus in which the word stem occurs. In some exemplary embodiments, a language model is trained on the corpus of documents, and the information content of each word stem occurrence is computed based on this language model. The information contents for all occurrences of each unique word stem are summed and normalized to form the feature-based representation of the document. In accordance with various exemplary embodiments, models for constructing a feature-based representation may include features such as n-grams and topics.

Proceeding to840, an N-dimensional compact representation is obtained for each document based on its feature-based representation. As described above,840may be performed by, e.g., the compact representation creating unit206of the document abstraction unit102in connection with the feature-based representation database212. In some exemplary embodiments, the feature-based representation may be based on to create a K-dimensional representation for each document. In other exemplary embodiments, an intermediate compact representation is created from the feature-based representation to be mapped to a K-dimensional representation for each document. According to one exemplary embodiment, a deep belief network is trained on the corpus of documents, using an information-maximizing subset of the corpus vocabulary as input features. The size of the input layer of the deep belief network is chosen according to the tolerance for training time. The size of the code layer determines the dimensionality of the compact representation. According to another exemplary embodiment, the compact representation is created by training a Latent Dirichlet Allocation (LDA) model from the feature-based representations. The compact representation may then be created by computing the conditional probabilities of each topic in the LDA model, given the document feature-based representation.

Moving to850, the set of documents are archived with their respective N-dimensional compact representations. As described above,850may be performed by, e.g., the document mapping unit206of the document abstraction unit102in connection with the compact representation database214.

FIG. 9is a flow chart illustrating an exemplary process performed by the document retrieving unit104, in accordance with one embodiment of the present disclosure. Beginning at910, a metric is determined for each archived document based on some criterion. Proceeding to920, the metric for each document is archived as metadata with respect to the document. As described above,910and920may be performed by, e.g., the document ranking unit302of the document retrieving unit104. Moving to930, certain documents are retrieved with their corresponding N-dimensional compact representations based on the metric. As described above,930may be performed by, e.g., the document selecting unit304of the document retrieving unit104.

FIG. 10is a flow chart illustrating an exemplary process performed by the document mapping unit106, in accordance with one embodiment of the present disclosure. Beginning at1010, certain documents associated with concepts are obtained with their corresponding N-dimensional compact representations. Proceeding to1020, each of the documents is projected to a point on a K-dimensional map based on its N-dimensional compact representation. As described above,1010and1020may be performed by, e.g., the document projection unit402of the document mapping unit106. Moving to1030, each region is identified in the K-dimensional map where a density of projected document points associated with a concept is larger than a predetermined threshold. As described above,1030may be performed by, e.g., the dense region detection unit404of the document mapping unit106. Proceeding to1040, a label is generated for each concept associating with document points whose density is larger than the predetermined threshold in each region identified. Moving to1050, the generated label is placed in the corresponding region identified. As described above,1040and1050may be performed by, e.g., the label generating unit406of the document mapping unit106.

In some exemplary embodiments, the font size and the color of a label for a concept reflect respectively the size of the underlying region and the density of documents associating with the concept in the underlying region, to clearly illustrate the main concepts contained in the result set, how concepts relate to each other, and how documents relate to concepts. In some exemplary embodiments, in each region identified, a label generated for a concept associating with a higher percentage of documents in the region, is rendered with a more outstanding feature. The more outstanding feature may include at least one of a darker color determined based on the density of documents associated with the concept and larger font size determined based on the size of the underlying region.

In some exemplary embodiments, at least one projected document point on the K-dimensional map is actionable to activate a display of information associated with the underlying document. In some exemplary embodiments, at least one rendered label on the K-dimensional map is actionable to activate a display of information related to the concept associated with the label. In some exemplary embodiments, a projected document point and/or a rendered label is activated when at least one of the following: a cursor is near to the projected document point and/or the rendered label; a cursor is clicked near the projected document point and/or the rendered label; and a cursor is in a region in the K-dimensional map that is marked.

In one exemplary embodiment, each label is placed on the map such that the position and size of the label indicate the position and size of the region in which projected document points related to the label are located. In this exemplary embodiment, a user may have high confidence that when selecting a particular document, the document will relate, in a semantic or conceptual sense, to the labels which are nearby. Further, the user in this exemplary embodiment may quickly get a sense of the main topics in the set of documents by observing the larger labels in the visualized map.

In one exemplary embodiment, the top several features from the feature-based representation are stored for each of the retrieved documents. A model is fit to the documents containing each feature to identify the positions and regions in which the feature occurs. For example, the positions in a K-dimensional map of documents containing a feature may be modeled by a Gaussian distribution with random noise. When the model is fit to the data based on, e.g., expectation-maximization, the position and variance of the Gaussian distribution define the region in which the feature occurs.

FIG. 11is a flow chart illustrating an exemplary process performed by the document visualization unit108, in accordance with one embodiment of the present disclosure. Beginning at1110, the constructed K-dimensional map and corresponding labels are received. Proceeding to1120, the K-dimensional map is visualized by either1122or1126, or both. At1122, the dimension of the map is controlled based on certain document information or labels. At1126, a visual interface is generated based on certain document information or labels. As described above,1110and1122may be performed by, e.g., the dimension control unit502of the document visualization unit108. As described above,1110and1126may be performed by, e.g., the visual interface generating unit504of the document visualization unit108. Moving to1130, the visualized map is rendered. As described above,1130may be performed by, e.g., the rendering unit506of the document visualization unit108.

FIG. 12is a flow chart illustrating an exemplary method for visualizing documents obtained via information retrieval, in accordance with one embodiment of the present disclosure. Beginning at1210, a set of documents is received. Proceeding to1220, a feature-based representation and an N-dimensional compact representation for each of the set of documents are generated and archived in, e.g., the document representation database603of the system600. As described above,1210and1220may be performed by, e.g., the document abstraction unit602of the system600. The feature-based representation of each document may be generated based on one or more terms extracted from the document. Independent from1210and1220, a query is received at1230. Proceeding to1240from1230, a feature-based representation and a compact representation for the query are generated and archived in, e.g., the query representation database613of the system600. As described above,1230and1240may be performed by, e.g., the query abstraction unit612of the system600. The feature-based representation of the query may be generated based on one or more terms extracted from the query. Moving to1250from both1220and1240, a plurality of documents associated with concepts is retrieved by matching content of the query with that of the archived documents. The content includes but is not limited to feature-based representations, compact representations, and other meta information. As described above,1250may be performed by, e.g., the document matching unit604of the system600. Proceeding to1260, each of the retrieved documents is projected to a point on a K-dimensional map based on its N-dimensional compact representation. Moving to1270, each region is identified in the map where a density of projected document points associated with a concept is larger than a predetermined threshold. As described above,1260and1270may be performed by, e.g., the document mapping unit606of the system600. Moving further to1280, a map is transmitted to visualize the queried documents and their associated concepts in each identified region, as a response to the query. As described above,1280may be performed by, e.g., the document visualization unit608of the system600. In one exemplary embodiment, a visual interface is generated to allow a user to interactively control documents and/or labels corresponding to concepts associated with the documents to be rendered on the K-dimensional map.

FIG. 13is a flow chart illustrating an exemplary embodiment of still another method for visualizing documents, in accordance with one embodiment of the present disclosure. This embodiment is illustrated inFIG. 12in conjunction withFIG. 13. In this embodiment, after performing all steps inFIG. 12, a second query is automatically generated, at1300, based on user interactions with the K-dimensional map observed. Such user interactions include clicking on a projected document point to, e.g., open the document to take a look, having the cursor near the document point so that some information related to the document is made visible, or clicking or having the cursor near a label associated with a concept to activate the display of certain information associated with the concept. Such interactions reflect, e.g., user's interests, in certain topics. Based on such observed user's interests, the disclosed system is able to further refine the retrieval of information that is more aligned with the user's interests. For example, assume that an initial query is “car” and on the K-dimensional map created by the process shown inFIG. 12there are three concepts rendered with labels “engine”, “seats”, and “automatic doors”. If the user keeps the cursor around the area where label “engine” is displayed or clicks on document points within the region where label “engine” is displayed, this may indicate that the user is actually interested in car engines, rather than car seats or car doors. In this case, after sensing the potential interests of the user in car engines, a refined query may be generated such as “car engine” based on the observed user behavior. Based on such a refined query, a further document retrieval may be performed to identify documents that are in alignment with the detected user's interests.

Moving to1310, at least one new document is retrieved, based on the automatically generated second query. Each new document is represented by an N-dimensional compact representation and associated with some concept(s). In this exemplary embodiment, a concept associated with a new document may be a new concept not currently associating with any existing documents on the K-dimensional map, or may also be a concept that is already associated with some document already projected on the K-dimensional map. Proceeding to1320, each new document is projected as a point on the K-dimensional map based on its N-dimensional compact representation so that all documents represented by existing document points and the newly projected document points in the K-dimensional map maintain the relative distances among the all documents in the N-dimensional space.

Moving to1330, each region in the K-dimensional map is then identified where a density of previously projected document points and the newly projected document points associated with a concept is larger than a predetermined threshold. Once all the documents, including the ones retrieved based on the original query and the documents retrieved based on the second or refined query, are projected on the K-dimensional map, the labels for concepts implied by such documents may need to be adjusted or updated. For example, if a concept is newly found in newly retrieved documents, a new label may need to be rendered to reflect if the density of the documents associated with that concept exceeds a certain threshold. In some situation, although the concept already exists with respect to the previously projected documents, the previous density is too low so that the label representing the concept has not been rendered. Now given some new documents also imply the same concept, the overall density across both the previously retrieved and newly retrieved documents may now exceed the required threshold so that the label representing the concept now needs to be rendered. If a concept is only associated with newly retrieved documents and the density does not exceed a required threshold, then the label representing the new concept needs not be added to the K-dimensional map. Specific conditions for updating the labels may depend on application needs. At1340, the disclosed system adjusts the rendition of labels that need to be rendered on the K-dimensional map. In this way, an updated K-dimensional map is generated. As an alternative embodiment (not shown in figures), the updated K-dimensional map may include only newly retrieved document.

In some exemplary embodiments, when labels for concepts determined based on both previously and newly projected documents are to be rendered, their positions and style in which they are rendered are also determined, in a manner as described above.

Then moving to1350, as a response to the user interaction with the K-dimensional map, a rendition of the updated K-dimensional map is transmitted with the all documents projected therein and with one or more newly generated labels rendered in corresponding regions identified on the updated K-dimensional map.

In this exemplary embodiment, a new query may also be automatically generated or processed each time when the user magnifies or zooms into a specific region of the map. The new query may be generated, in this case, based on the text of the document being magnified. For example, if a user magnifies an area of a document that describes racing car's engine, the automatically generated query may now be “race car engine” rather than “car engine” as shown in the previous example. Such a new query is generated based on the observed behavior of the user without requiring the user to further specifying expressly an additional query.

In some exemplary embodiments, when a user zoom in a particular region in the K-dimensional map, not only the region can be re-rendered proportionally on-the-fly but also a new query can be automatically generated. When new documents are retrieved based on the newly generated query and new labels corresponding to concepts are created, such new documents and new label, if any, will also be projected into the region that has been zoomed in. In projecting such new documents and rendering new labels, the previously existing document points and labels may impact how the new documents/labels are rendered. In addition, the rendered features of the documents points, existing and new, as well as the labels, existing or new, may also need to be adjusted. For example, the previous color of the document points may change when new documents are also being projected. One example is when the documents with most recent publication dates may be marked as red. Now when new documents are projected into the map, there may be new documents that have even more recent dates so that the documents that used to be marked as red may now need to be marked as other colors.

FIG. 14is a block diagram illustrating an exemplary embodiment of still another system1400for visualizing documents, in accordance with one embodiment of the present disclosure. As compared to the system600, the system1400in this exemplary embodiment includes a plurality of document abstraction units1421,1422,1423, a plurality of document representation databases1431,1432,1433, and a plurality of models1411, for visualizing multiple sets of documents1401,1402,1403. For each i from 1 to M, wherein M is larger or equal to 2, the document abstraction unit i is configured to receive a set of documents i, and generate and archive a feature-based representation and compact representations for each of the documents i based on the models1-M, into the document representation database i. In this exemplary embodiment, one model may represent one subject area that are from one or more pluralities of documents. The system1400in this exemplary embodiment further includes a query abstraction unit1424, which is operatively coupled to models1-M1411, for a received query1451. The query abstraction unit1424is configured to receive a query1451, and generate and archive feature-based representations and compact representations for the query1451based on models1-M1411, into the query representation database1434.

The system1400in this exemplary embodiment further includes a document matching unit1404, a document mapping unit1406, and a document visualization unit1408. The document matching unit1404in this exemplary embodiment is configured to retrieve a plurality of documents associated with concepts by matching content of the query1451with that of the archived documents from document representation databases1to M,1431,1432,1433. The document mapping unit1406in this exemplary embodiment is operatively coupled to the document matching unit1404and configured to project each of the retrieved documents to a point on a K-dimensional map based on its N-dimensional compact representations, and identify each region in the map where a density of projected document points associated with a concept is larger than a predetermined threshold. The document visualization unit1408in this exemplary embodiment is operatively coupled to the document mapping unit606, and configured to transmit a map visualizing the queried documents and their associated concepts in each identified region, as a response to the query1451.

FIG. 15is a high level depiction of an exemplary system1500for visualizing documents, in accordance with a first application embodiment of the present disclosure. The exemplary system1500includes users1510, a network1520, a search engine1530, a document database1560, a document visualization system1540, and a matched document representation database1550. The network1520in system1500can be a single network or a combination of different networks. For example, a network1520can be a local area network (LAN), a wide area network (WAN), a public network, a private network, a proprietary network, a Public Telephone Switched Network (PSTN), the Internet, a wireless network, a virtual network, or any combination thereof. Users1510may be of different types such as users connected to the network via desktop connections (1510-d), users connecting to the network via wireless connections such as through a laptop (1510-c), a handheld device (1510-a), or a built-in device in a motor vehicle (1510-b). A user1510may send a query to the search engine1530via the network1520and receive a visualized map as a response from the search engine1530through the network1520. The search engine1530in this exemplary system searches for one or more matched documents stored in the database1550with their document representations, based on the received query and the documents in database1560provided by the document visualization system1540. In this exemplary system1500, the document visualization system1540generates the visualized map based on the matched documents in the database1550, and renders the map to the search engine1530, which forwards the map to the user1510. In this exemplary system1500, the search engine1530is configured to respond to the query of the user1510.

FIG. 16is a high level depiction of an exemplary system1600for visualizing documents, in accordance with a second application embodiment of the present disclosure. The exemplary system1600includes users1610, a network1620, a search engine1630, a document database1660, a document visualization system1640, and a matched document representation database1650. The network1620in system1600can be a single network or a combination of different networks. For example, a network1620can be a local area network (LAN), a wide area network (WAN), a public network, a private network, a proprietary network, a Public Telephone Switched Network (PSTN), the Internet, a wireless network, a virtual network, or any combination thereof. Users1610may be of different types such as users connected to the network via desktop connections (1610-d), users connecting to the network via wireless connections such as through a laptop (1610-c), a handheld device (1610-a), or a built-in device in a motor vehicle (1610-b). A user1610may send a query to the search engine1630via the network1620and receive a visualized map as a response. The search engine1630in this exemplary system searches for one or more matched documents stored in the database1650with their document representations, based on the received query and the documents in database1660provided by the document visualization system1640. In this exemplary system1600, the document visualization system1640generates the visualized map based on the matched documents in the database1650, and renders the map to the user1610. In this exemplary system1600, the document visualization system1640is configured to respond to the query of the user1510.

FIG. 17illustrates an exemplary map1700generated based on a query of “electric car”, in accordance with one embodiment of the present disclosure. As illustrated in the exemplary map1700, each of the displayed document points represents a document related to the query of “electric car”. The document points displayed closer on the map represent documents that are more semantically related to each other, compared to the document points displayed farther away. Labels are rendered in each region in the map where a density of document points associated with a concept is larger than a predetermined threshold. For example, label “electric”1702is rendered with a larger font based on a larger size of the region covering the concepts relating to “electric”, and label “brake”1704is rendered with a smaller font based on a smaller size of the region covering the concepts relating to “brake”.

FIG. 18depicts a general computer architecture on which the present disclosure can be implemented and has a functional block diagram illustration of a computer hardware platform which includes user interface elements. The computer may be a general-purpose computer or a special purpose computer. This computer1800can be used to implement any components of the system for visualizing documents as described herein. Different components of the systems100,600,1400, e.g., as depicted inFIGS. 1, 6 and 14, can all be implemented on one or more computers such as computer1800, via its hardware, software program, firmware, or a combination thereof. Although only one such computer is shown, for convenience, the computer functions relating to dynamic relation and event detection may be implemented in a distributed fashion on a number of similar platforms, to distribute the processing load.

The computer1800, for example, includes COM ports1802connected to and from a network connected thereto to facilitate data communications. The computer1800also includes a central processing unit (CPU)1804, in the form of one or more processors, for executing program instructions. The exemplary computer platform includes an internal communication bus1806, program storage and data storage of different forms, e.g., disk1808, read only memory (ROM)1810, or random access memory (RAM)1812, for various data files to be processed and/or communicated by the computer, as well as possibly program instructions to be executed by the CPU. The computer1800also includes an I/O component1814, supporting input/output flows between the computer and other components therein such as user interface elements1816. The computer1800may also receive programming and data via network communications.

All or portions of the computer-implemented method may at times be communicated through a network such as the Internet or various other telecommunication networks. Such communications, for example, may enable loading of the software from one computer or processor into another. Thus, another type of media that may bear the elements of the computer-implemented method includes optical, electrical, and electromagnetic waves, such as used across physical interfaces between local devices, through wired and optical landline networks and over various air-links. The physical elements that carry such waves, such as wired or wireless links, optical links or the like, also may be considered as media bearing the computer-implemented method. As used herein, unless restricted to tangible “storage” media, terms such as computer or machine “readable medium” refer to any medium that participates in providing instructions to a processor for execution.

Those skilled in the art will recognize that the present disclosure is amenable to a variety of modifications and/or enhancements. For example, although the implementation of various components described above may be embodied in a hardware device, it can also be implemented as a firmware, firmware/software combination, firmware/hardware combination, or a hardware/firmware/software combination.