Technology of semantic search of the information in electronic libraries

Information Technology "Key To Text" for
Semantic search and indexing of textual information
- an essential tool for Electronic Publishing
Kreines M. G.
Moscow Center for New Information Technology in Medical Education
Moscow Medical Academy
[email protected]
of the Ministry of Science (N 2.19.2 NCTN-SE, 2D-220/II-94) (RFBR N 00-07-90116, N 97-07-131, N 98-01-00929) Introduction
The electronic editions gives essentially new features to structure and organization for searching information by the reader and the information servicesproviders. Before the computer revolution any edition on a library shelf or under a veilof a dust on a desk, before the reader took it in his hands, meant no more than waswritten in its catalogue card. (Certainly, we here do not speak about the editionssurrounded with light of legends). Only the electronic edition is capable to speak at the top of its voice even in the absence of the reader. The complete dictionary index of the accessible editions, which30 years back was the dream of any visitor of the scientific library, today has becomethe present damnation. Let’s imagine a reader who wants to find verses about love(about the real love). He will receive a vast list of references on 10, 20, 30, … ways oflove, 1001 nights of love, legal, psychological, physiological features of love of sexualminorities, on love to the Fatherland and not love to certain characters. But hesearched another matter! His wishes and ideas aspired to something different. He hassimply formulated a search image, and the results of the search only hide his idea oflove behind a detailed lexical map of the use of the word "love". Fortunately, it ispossible to use the skill of the electronic editions to speak (we shall recollectAhmatova’s verse: «I have learned women to speak, but God, who will force them tostop?») into a channel of intelligent, purposeful dialogue with the prospective reader.
We shall in this paper discuss the technology ensuring such dialogue on the basis ofthe automated computed semantic search and analysis of the textual information.
This dialogue is important not only for the reader, who hungers for the information he wants. It is extremely important for the author or publisher too because of theimportance of the authentical prediction of the ways how to understand how thepublished text is understood by defferent categories of readers.
N.B.! In the Appendix the results of the analysis of the text of the presented paper by the proposed methods are given: a set of key words as they are represented to thereader of the newspaper "Times". The fragments of the text included into the computedsummary are underlined in the text of the paper.
Background
We have developed and used, in practice, the intellectual technologies of semantic search, analysis and indexing of textual information in information resourcesin natural languages accessible with the help of telecommunications or on electroniccarriers of information.
The explosive growth of the information resources available electronically created a necessity for efficient semantic search engines. The traditional methods includingkeyword search and context search are effectively unable to provide a semantic filteringin sufficiently large data arrays - the resulting search output is still beyond the scope ofhuman analysis. Similar problems are present in an alternative approach - a priorisemantic indexing -, as it requires compilation and standardizing thesauruses, whichposes additional difficulties. Inefficient filtering also puts excessive pressure on thenetwork by tightening the traffic.
The efficient analysis and search of textual information requires a profound and sophisticated language and text models and essentially new methods. Such modelsand algorithms were developed by our research team at the Moscow Center of NewInformation Technologies of the Moscow Medical Academy under the grants of theMinistry of Science (N 2.19.2 NCTN-SE, 2D-220/II-94) and Russian Fund for BasicResearch (RFBR N 00-07-90116, N 97-07-131, N 98-01-00929).
Our search technology is based on a new original two-level model of understanding and interpretation of a text. While the second level requires humaninteraction and understanding of language semantics, the first level is the one wherepurely computational approach offers its help. It turns out that based on combinatorial-statistical analysis, it is possible to synthesize the semantic pattern of a given text, i.e.,to generate a generally small subset of words mostly closely bearing the text'ssemantics, without referencing to the semantics of the language the text is written in. Inparticular, the language thesauruses are not used. This phenomenon appears to betrue for many European languages (including, for example, Russian and English). Theengine based on the two languages was implemented on a local network ofworkstations. These procedures have been developed by our team and comprise the core of the intellectual technology we offer. In other words, the technology delivers a sufficientlydetailed semantic (semiotic) pattern -- portrait of a text and can be used for semanticsearch, classification, and annotation, and development of information resources. Whilefeaturing completeness and accuracy of the semantic search and classification, it doesnot require any form of a priori knowledge of the language besides the languagemorphology. This facilitates can be applied to virtually any subject area and anextension to more than one language.
The set of tools we developed includes: -- computational semantic indexing, classification, and annotation as a means of search, analysis, and development of information resources in global communicationnetworks and local repositories, -- a possibility for a user to describe the subject area by giving text samples,-- multi-language support allowing for the text samples in one language and the The technology is oriented to both end-users and information resource providers The offered information technologies of semantic search of the information will present significant interest for various subject domains. Really, our technology ofsemantic search is subject domain independent, as it does not require the thesaurusesand other forms of explanatory dictionaries. Today technology KEYS TO the TEXT allows us to analyze the texts in Russian and English languages under various operational environments (Windows and UNIX)and computing platforms. • The basic structures and steps of the semantic analysis and search of the textual information are considered within the framework of technology KEYS TO the TEXT, • The typical example of results of the analysis and search of the textual information with use of technology KEYS TO the TEXT is given, • The computing characteristics and architecture of our computer technology are The basic structures of the semantic analysis of the text and stages of
search of the textual information by technology KEYS TO the TEXT
The Base for our technology are the algorithms of construction for any text its “semantic" pattern - set of words, semiotocally mostly strongly connected amongthemselves in the concrete analyzed text. (Here and later in the text of the paper weunderline the fragments of the text which were included into the summary as computedby technology KEYS TO the TEXT, see the Appendix). The word "semantic" is notcasually put in inverted commas. When a man makes the analysis and interpretation ofthis set of words, (received as a result of calculations) their intelligence and connectionwith subjects, contents and sense of the analyzed text is obvious. But the computationsreally do not require any semantic information and knowledge of language grammar.
These computations use original metrics to extract semioticaly connected words in thetexts. This metrics (proposed by the author of the paper) needs only combinatorialstatistics of the words in the analyzed text and in some set of the texts, representativefor language in which the analyzed text is written. The choice of reference set of thetexts is equivalent to the formulation of positions of the man, who wants to perceive theconcrete text. It is possible to limit such choice to the reference texts of a certain groupof carriers of language, for example, professional or political. The problem of forming thereference set of the texts can be treated as the implicit forming of a subset of languageadequate to the subject perceiving the text.
The construction of a semantic pattern of the text is based on two basic hypotheses:1. Semiotic characteristics (semiotic connections of words in the text) determine 2. To understand or to get a sense of the concrete text it is necessary to determine a reference set of the text, in which context it is necessary to perceive the concretetext. In essence, it is practically folklore axioms in the linguists, philologists and psychologists societies. It is enough to recollect two classical formulations: Validity of the formulated hypotheses proves to be true by high efficiency of the computing analysis of the texts in technology KEYS TO the TEXT.
Our technology assumes that it is necessary to identify as uniform various forms of each word (for example, one noun in various numbers or a verb in various times,singular or plural number). Such identification enables us to take into account theconcrete grammatical forms of the words for construction of semantic patterns of thetext. For this purpose the knowledge of language is used. In our technology thisprocedure (so-called lemmatization) is based on the specific morphological analysis,which allows with high reliability to recognize various forms of concrete words of thegiven language. Now lemmatization (morphological analysis of the words) is working forRussian and English texts. The construction of a semantic pattern of the text solves a problem of computational semantic indexing of the textual information adaptively to interests of theuser or concrete carrier of the language (professional or political group, individual certainauthor, edition, group of the editions and so on). The result of computational indexing is interesting by itself as the means of automatic creation of secondary information resources - lists of key words, which areadequate from the point of view of the concrete reader display the contents and sense ofthe texts. Simultaneously, the semantic pattern allows allocating in the text mostlyimportant for subjects and contents of the text fragments. That provides automaticgeneration of the abstracts. Semantic patterns are the base for computational semanticclassification of the texts. For this purpose we developed special measure of thesemantic affinity based on the above-mentioned metrics of semiotic connections ofwords in the text. The solution of the problem of computational construction of a semantic pattern of the text has allowed us to develop new approaches to semantic search and retrieval oftextual information. This technology of search and retrieval of information selects just thetexts that by the contents and sense really meets the inquiry. The opportunity hasappeared to use as inquiry the text selected by user. In technology KEYS TO the TEXTthe semantic pattern of the sample text is computed automatically and adaptively in theinterests of the user by the usage of the reference set of the texts, and is treated as aninquiry. The results of search on the inquiry are analyzed and a semantic pattern of eachfound text is computed. Then the comparison of semantic patterns of the text - sampleand found texts - analysis of semantic affinity with the inquiry is carried out. From theresults of the analysis the final set of results is formed. The procedure of search can becarried out by means of full texts databases (if the texts were indexed in suchdatabases) or directly in the file systems by the means of our technology. The results ofthe application of technology KEY TO the TEXT are highly exact and complete. And itrelieves the user from the necessity to solve a very complex problem of describinghis/hers interests with just a few words.
Results of the analysis and search of the textual information with the use of
technology KEYS TO the TEXT (typical example in comparison with MEDLINE)
For an experimental research of quality, accuracy and completeness of semantic indexing and search of the information with use of technology KEYS TO the TEXT thecomparison of results received with the help of our technology and with one of the mostpopular professional medical data base MEDLINE has been carried out. MEDLINEsystem is supported by National medical library of USA, and contains the bibliographicinformation on the scientific publications on medical subjects practically all over theworld. In MEDLINE the following structure of the record is supported: the paper’s title,authors, bibliographic description, abstract in English (if the abstract is present in thepublication), set of key words for the publication generated by a highly professionalexpert -- the employee of the Library within the framework of the special thesaurus. Asystem of this type is needed for experiments on objective estimation of our searchtechnology. And just with MEDLINE we have good reference point for judgement aboutcompleteness of search by technology KEYS TO the TEXT.
The experiments were carried out as follows. A certain fragment of an initial database (1995 - 1999 and 114 magazines) was chosen. As the reference search weused database search by its retrieval means for the different samples. As inquiry weused those indexes, on which the sample has been indexed in the database. It wasnecessary to choose a certain subset from all set of indexes, as our attempt to searchunder the complete list of indexes usually came to an end by detecting only the sampletext itself. The choice of the specified subset did not represent essential difficulties. Theattempt to use more than three indexes words leads to the same situation as withcomplete set of indexes. And it was not hard work for the expert to select three mainindexes from the MEDLINE indexes.
For comparison we carried out a search by means of our technology in the texts exported from a database in a textual format only with the headings and texts of theabstracts (bibliographic descriptions and the index words were excluded). As referencetexts we used the headings and the texts of the abstracts for the whole investigatedperiod, in which the concrete sample had been published.
Let's consider two examples.
A text in a the database MEDLINE: Title: Alcohol-related injury death and alcohol availability in remote Alaska Authors:Landen MG; Beller M; Funk E; Propst M; Middaugh J; Moolenaar Affiliation:Division of Field Epidemiology, Epidemiology Program Office, Centers for Disease Control and Prevention, Atlanta, Ga, USA.
Journal:JAMA ISSN: 0098-7484 Vol: 278 Iss: 21 Page: 1755-1758 Date: Dec 3 1997 Type: JOURNAL ARTICLE Country of Publication: UNITED STATES Language: ENGLISHMajor MeSH:Alcohol Drinking [adverse effects]; Alcohol Drinking [epidemiology]; Alcoholic Beverages [supply and distribution]; Drug and Narcotic Control; Eskimos [statistics and numerical data]; Mortality [trends]; Wounds andInjuries [etiology] Minor MeSH: Accidents [mortality]; Accidents [statistics and numerical data]; Adolescence; Adult; Alaska [epidemiology]; Alcohol Drinking [blood];Alcoholic Beverages [utilization]; Alcoholic Intoxication [epidemiology];Commerce; Comparative Study; Ethanol [blood]; Female; Human; Male; Woundsand Injuries [blood]; Wounds and Injuries [mortality] Registry No: 64-17-5 Substances: Ethanol Jrnl Group: Abridged Index Medicus; Cancer Comments: Comment in: JAMA Dec 3 1997 Vol: 278 Iss: 21 Page: 1781- Abstract: CONTEXT: Injury is a major public health problem in Alaska, and alcohol consumption and injury death are associated. OBJECTIVE: To determinethe association between injury death, particularly alcohol-related injury death,and alcohol availability in remote Alaska. DESIGN, SETTING, ANDPARTICIPANTS: Survey using death certificate data and medical examinerrecords to compare mortality rates for total injury and alcohol-related injury during1990 through 1993 among Alaskans aged 15 years and older who had resided inremote villages of fewer than 1000 persons. MAIN OUTCOME MEASURES:Rate ratios of injury death among residents of wet villages (ie, those without arestrictive alcohol law) as compared with injury death among residents of dryvillages (ie, those with laws that prohibited the sale and importation of alcohol).
RESULTS: Of 302 injury deaths, blood alcohol concentrations (BACs) wereavailable for 200 deaths (66.2 %). Of these, 130 (65.0 %) had a BAC greaterthan or equal to 17 mmol/L (> or =80 mg/dL) and were, therefore, classified asalcohol related. The total injury mortality rate was greater among Alaska Nativesfrom wet villages (rate ratio [RR], 1.6; 95 % confidence interval [CI], 1.3-2.1),whereas this difference was not present for nonnatives (RR, 1.1; 95 % CI, 0.3-3.8). For Alaska Natives, the alcohol-related injury mortality rate was greateramong residents of wet villages (RR, 2.7; 95 % CI, 1.9-3.8) than among residentsof dry villages. The strength of this association was greatest for deaths due tomotor vehicle injury, homicide, and hypothermia. CONCLUSIONS: Althoughinsufficient data existed to adjust for the effects of all potential confounders,residence in a wet village was associated with alcohol-related injury death amongAlaska Native residents of remote Alaska villages. These findings indicate thatmeasures limiting access to alcoholic beverages in this region may decreasealcohol-related injury deaths.
Copyright: This citation is derived from the National Library of Medicine's Here under headings Major MeSH and Minor MeSH are presented the key words, on which publication has been indexed in the database.
Title: Analyses of coronary graft patency after aprotinin use: results from the International Multicenter Aprotinin Graft Patency Experience (IMAGE) trial.
Authors: Alderman EL, Levy JH, Rich JB, Nili M, Vidne B, Schaff H, Uretzky G, Pettersson G, Thiis JJ, Hantler CB, Chaitman B, Nadel A.
Affiliation: Division of Cardiovascular Medicine, Stanford University Medical Journal: J Thorac Cardiovasc Surg, V 116, N 5, Page: 716-30Date 1998 Major MeSH: Aprotinin [adverse effects], Coronary Artery Bypass, Graft Occlusion, Vascular [chemically induced], Hemostatics [adverse effects],Myocardial Infarction [chemically induced], K Adult, Aged, Anti-InflammatoryAgents, Non-Steroidal [administration and dosage] [adverse effects] Minor MeSH: Aprotinin [administration and dosage], Aspirin [administration and dosage] [adverse effects], Blood Loss, Surgical [prevention and control],Cardiopulmonary Bypass, Graft Occlusion, Vascular [mortality], Hemostatics[administration and dosage], Heparin [blood], Middle Age, Myocardial Infarction[mortality], Risk Factors, Survival Rate, Veins [transplantation], Female, Human,Male, Support, Non-U.S. Gov't Abstract: OBJECTIVE: We examined the effects of aprotinin on graft patency, prevalence of myocardial infarction, and blood loss in patientsundergoing primary coronary surgery with cardiopulmonary bypass. METHODS:Patients from 13 international sites were randomized to receive intraoperativeaprotinin (n = 436) or placebo (n = 434). Graft angiography was obtained a meanof 10.8 days after the operation. Electrocardiograms, cardiac enzymes, andblood loss and replacement were evaluated. RESULTS: In 796 assessablepatients, aprotinin reduced thoracic drainage volume by 43 % (P < .0001) andrequirement for red blood cell administration by 49 % (P < .0001). Among 703patients with assessable saphenous vein grafts, occlusions occurred in 15.4 % ofaprotinin-treated patients and 10.9 % of patients receiving placebo (P = .03).
After we had adjusted for risk factors associated with vein graft occlusion, theaprotinin versus placebo risk ratio decreased from 1.7 to 1.05 (90 % confidenceinterval, 0.6 to 1.8). These factors included female gender, lack of prior aspirintherapy, small and poor distal vessel quality, and possibly use of aprotinin-treated blood as excised vein perfusate. At United States sites, patients hadcharacteristics more favorable for graft patency, and occlusions occurred in 9.4% of the aprotinin group and 9.5 % of the placebo group (P = .72). At Danish andIsraeli sites, where patients had more adverse characteristics, occlusionsoccurred in 23.0 % of aprotinin- and 12.4 % of placebo-treated patients (P = .01).
Aprotinin did not affect the occurrence of myocardial infarction (aprotinin: 2.9 %;placebo: 3.8 %) or mortality (aprotinin: 1.4 %; placebo: 1.6 %). CONCLUSIONS:In this study, the probability of early vein graft occlusion was increased byaprotinin, but this outcome was promoted by multiple risk factors for graftocclusion.
Copyright: This citation is derived from the National Library of Medicine's The technology KEYS TO the TEXT has constructed as a result of computational procedure for the first of the given abstracts the following semantic pattern: injury, alcohol, death, Native, mortality, greater, Alaska, village, remote, BAC (blood alcohol concentration), wet, law, dry, availability.
aprotinin, occlusion, patency, graft, International, ivein, occurred, sites, infarction, characteristics, loss, blood, treated, myocardial, patients, assessable.
It is easy to see a good accordance of indexes computed as a result of formal procedure and selected by the experts of National medical library of USA. Thecomparison of 250 analyzed abstracts leads to the conclusion about high qualitycomputing semantic indexing carried out by our technology. On the average, more than95 % of the concepts are appropriate to the basic indexes (Major MeSH) MEDLINE andmore than 75 % of the concepts, appropriate to minor indexes (Minor MeSH), has comein the semantic patterns of the texts computed by technology KEY TO TEXTS. Andapproximately 75 % of the calculated indexes had semantic conformity in indexes ofMEDLINE.
To compare the results of searching by means of a the database MEDLINE with the use of the technology KEYS TO the TEXT we developed a computer system foranalyses and comparison of the search results and their statistical analysis andrepresentation of results in an evident form.
The comparison of results of search has confirmed rather high efficiency of our technology. For example, for the first sample: Professional experts produced this data by analysis and comparison of the found Basic feature of the technology KEYS TO the TEXT is the absence of the necessity of the semantic information for the semantic analysis of the textualinformation. Probably, it reflects as deep properties of human speech as the semioticsystem. It has appeared that if you perceive the text as it exists among other texts, itssemiotic determinants can be revealed as a result of a certain computing procedure.
The characteristics and architecture of computer technology of semantic
search of the textual information KEYS TO the TEXT
The system KEY TO the TEXT was developed as separate blocks: "client", "server", “dispatcher” and modules of the analysis of the data. The architecture of thesystem allows optimal use of computing resources, provides maximal productivity, andperforms any policy of access to information resources. The program "client" allows the user to formulate the problem of what information to search, to instruct the "server" to perform the task, to trace process of performance ofthe task, if necessary to stop performance, to copy results of the search and file of thereport. After starting the task the "client" is not obliged to trace its performance, and canbe disconnected. The "Server” is capable to work on the task independently before itsfinished. At repeated connection to the "server", the process of management and controlis restored. Generated by the “client" the task gets a name - up to 8 letters. This nameidentifies the user.
The program "server" itself is not engaged in the performance of settlement and search operations. It only operates processes of performance of tasks and isresponsible for connection of the “client" with the active task.
To perform a task the program "server" starts other programs – modules. These - computation of semantic patterns of the texts;- transformation of files of semantic patterns to inquiries;- contextual search in textual files on inquiries;- computation of semantic affinity of the found texts and sample texts;- creation of a file with lists of words used further for the summary;- summary of the texts.
The “dispatcher” starts the copies of the "server". This provides work in the multi user mode. Initially all clients address the “dispatcher”, and it directs the “client” to thenecessary copy of the "server". Then "client" works with its copy of the "server".
The program "server" is the console managing and communicating with other programs. The communications with the "client" is carried out under the protocol TCP/IPwith use of jacks SOCET. It allows the "server" to work both in Windows and on anysimilar UNIX operation environments on any computer platform. The program "server" carries out the following functions:- processing of the controls of the program "client";- generating the controls for different stages of the task to start up modules (these controls are textual files which use the internal language of the system); - consecutive start of the modules to carry out necessary actions during the - reception from modules of the report during performance (as a textual file).
The parameters necessary for the "server" to do correct work are set in a textual file, which name is in a start line of the program "server". In a similar way the "server"makes the adjustments and starts up the modules. The modules are also consoleprograms. Controlling the work of all programs of the system in this way is convenientand easy for the user.
After the “server” has started the module, the module gives out a report, which is accessible for the "server" as a text file. The "Server" copies this text file to the “client"and expects inside the text a code that will end the performance. After receiving thecode of the ending, or the code of the mistakes, the "server" makes the next logic step inthe general process of information processing. The result of the work of each module isone or several files of a non text format containing all necessary information on the process of performance, and text files with results of information analysis and/orretrieval.
When the computations have stopped the “client” can copy reports and results from the "server". These files include: the found texts or fragments of the texts, withdigital names; the summaries of the found texts; a file - report with names of the foundtexts in decreasing order of semantic affinity to the sample texts with quantity measureof the one. If user sets more than one sample simultaneously and more than oneindependent inquiry has been computed the report contains some number of thesubsets of above information for each sample separately. The program "client" is the dialogue communication program intended for work with the program "server". The communication part of the program "client" is developed onprinciples similar to the server. The "Client" is developed for from the "server"environment WINDOWS 98 or is compatible with it. One aim of the program is to givethe user an easy way to start and support an information search and to analyse aproblem on the "server".
The "Client" can be connected or disconnected to the "server" at any moment. The “Client” controls the process of automatic information search in textual resourcesaccessible for the "server"; copies results of searches on the local machine, on whichthe client is established. If necessary it is possible to stop the process of computation onthe "server" by the user. Viewing a resulting file of the report with the list of the foundtexts (sorted by semantic affinity) the “client” uses the built - in editor for visualization ofthe found texts. This editor automatically points with three different colors three groupsof words in the text (words of a semantic pattern of the found text, words from inquiry inthe found text, words simultaneously included in both specified groups). The “Client” cansave all current user’s adjustments of the environment in setup files.
The computational complexity of technology KEYS TO the TEXT is certainly of interest. Some rough figures: the search on a sample with the subsequent semanticanalysis of results in 10 Mbytes of textual information requires approximately 1 minute ofwork on a PC with a CPU Pentium II. If not to use for search of the data basesmechanisms for information retrieval, the time of search grows approximately linearlywith the growth of volume of the zone of search. Computational complexity of thesemantic analysis of the texts behaves in another way if one wants to optimize a modeof the analysis of the information. The optimization assumes association of the analyzedtexts in packages with the subsequent analysis of a package as a whole. The prize hereis achieved because the time necessary for creation by the computer the structuresused for the analysis of the textual information is convex function from number of thetexts. And at small number of the texts it practically does not depend on their number. Inresult, the average time of the analysis of one text at a batch mode of the analysisappears much less, than time of the analysis of one separately taken text. However, atsignificant growth of number of the texts in a package computational complexity growsmuch faster, than linearly. Therefore the principal orientation of technology KEYS TO theTEXT to parallel calculations and distributed computational environment for storage andanalysis of the data are capable really to supply semantic search and analysis of thetextual information in the distributed electronic libraries and information resources ofglobal telecommunication networks.
Appendix
The key words in alphabetic order of the presented paper without the MEDLINE texts (as computed by technology KEY OT the TEXT) are: analysis, analyze, computing,computational, database, indexes, information, MEDLINE, modulus, pattern, program,search, semantic, semiotic, server, subset, technology, text, textual. The summary of the paper (as computed by technology KEY TO the TEXT) is underlined in the text of the paper. The summary is 5% of the paper’s volume.
Reference set of the texts was all the text in the “TIMES” from 1 January 1995 to 10

Source: http://elpub.scix.net/data/works/att/0007.content.01221.pdf