Discharge notes summarize reasons for hospital stays and diagnosis, include medical history and treatment received, and provide instructions for follow-up care and medications. These notes are often difficult for patients to understand due to medical jargon, abbreviations, and complex structures. Despite recommendations that patient-facing materials be written at a sixth-grade reading level, most discharge notes do not meet this target, creating barriers to comprehension. Large language models (LLMs) can simplify clinical text but risk omitting important information, introducing errors, or producing hallucinations. We propose a retrieval-augmented generation (RAG) pipeline to enhance LLM-based simplification of discharge notes by appending biomedical definitions to prompts. Our pipeline combines (1) direct UMLS concept linking with SciSpaCy to extract canonical names and definitions, and (2) FAISS-based semantic retrieval of additional relevant definitions not explicitly detected by SciSpaCy. These definitions are integrated into prompts for ChatGPT-4o to generate simplified summaries at a sixth-grade reading level. We evaluated this approach on 20 MIMIC-III discharge notes, comparing RAG-augmented outputs (R_notes) with baseline LLM simplifications (B_notes). Manual review measured completeness and correctness, readability was assessed with Flesch-Kincaid Grade Level (FKGL) and Flesch Reading Ease, and LLM-based judgments evaluated clarity. Results show that R_notes achieved higher completeness (77.6 % vs. 72.7 %, the completeness of$R$_notes is higher than that of B_notes in 16 cases with statistical significant), fewer errors (2 vs. 6), and better contextualization of medical terms ($\mathbf{4. 3 ~ v s. ~} \mathbf{3. 6}$on a 5 -point scale). Readability also improved, more closely aligning with the sixth-grade target. These improvements highlight the potential of RAG-enhanced prompting to strengthen patient understanding and engagement with their health information.

Discharge notes are dense, information-rich documents that contain patient histories, diagnoses, treatments, and clinical observations, as well as post-discharge care instructions. While they provide essential data for clinical decision-making and research, they are often written using abbreviations and complex medical jargon, making them difficult for patients to interpret. Automatic highlighting of discharge notes enhances information accessibility, supports summarization and simplification, and improves clinical interoperability of the notes. Achieving accurate highlighting requires terminologies that include fine-granularity phrases, which existing reference terminologies such as SNOMED CT lack. To address this limitation, in our previous work, we proposed the Cardiology Interface Terminology (CIT), tailored for accurate highlighting of discharge notes of cardiology patients. Candidate concepts to be added to CIT were extracted from notes through concatenation and anchoring operations, with each phrase undergoing automatic and manual review before inclusion in CIT. Manual review of these phrases is highly time-consuming and costly process. In this study, we propose a Machine Learning (ML)-assisted approach to reduce the manual review efforts involved in terminology curation. We trained a Neural Network (NN) model on varying subsets of phrases generated through concatenation and anchoring, to determine the minimum number of phrases that must be manually reviewed to effectively train the ML model to label the remaining phrases automatically. The optimal batch sizes were identified as$\mathbf{6, 0 0 0}$(out of$\mathbf{2 8, 6 1 7}$) for concatenation and$\mathbf{3, 0 0 0}$(out of 9,845) for anchoring. The resulting terminology (CIT${}_{\text {ML2+ }}$) achieved a coverage of 68.74 % and breadth of 1.6 on the test dataset, closely matching the fully manually curated CIT+ (coverage 70.21 %, breadth 1.6), with comparable completeness (97.4 % vs. 98.6 %) and conciseness (84.1 % vs. 83.6 %). These findings demonstrate that substantial reductions in manual review can be achieved without compromising highlighting quality, providing a scalable and efficient framework for curating interface terminologies across diverse medical domains.

Electronic Health Record (EHR) notes often contain complex medical language, making them difficult to understand for patients lacking medical background. Simplifying EHR notes to a 6th-grade reading level is recommended by the American Medical Association to enhance patient comprehension and engagement. Large Language Models (LLMs) show promise in achieving this goal but also face challenges, such as missing and generating false information. In our previous work, we have shown that providing LLMs with highlighted EHRs, where the important information is highlighted, results in more accurate summaries compared to summarizing unhighlighted notes. In this study, we simplify highlighted EHRs with LLMs, specifically ChatGPT-4o, using two approaches: two-step simplification (sequential) and one-step (CoT-based) simplification. In the sequential approach, we generate a structured summary of the highlighted EHR, as a first step, and then we convert this summary into language suitable for a 6th-grade reader, as a second step. In the CoT-based approach, we convert the highlighted EHR into a structured summary understandable for a 6th-grade reader in one step. Evaluating the simplified notes obtained from the two approaches, the sequential approach shows higher completeness (82.35% vs. 75.89%) and correctness, as well as better readability scores (FKGL: 7.72 vs. 10.73; Flesch: 67.71 vs. 45.31) and higher average understandability ratings from ChatGPT-4 (3.92 vs. 3.28), demonstrating its overall superiority in simplifying notes.

Highlighting of Electronic Health Records (EHRs) involves marking essential content of EHR notes, corresponding to concepts of a clinical terminology. However, employing the best clinical terminology (SNOMED CT) for highlighting EHRs, captures only a portion of their crucial content. In this paper, we describe the curation of a Cardiology Interface Terminology (CIT) dedicated to the application of highlighting EHRs of cardiology patients. We utilize a Clinical-Named Entity Recognition (Clinical NER) approach for extracting phrases, of higher granularity than SNOMED CT concepts, from EHRs, for enriching CIT. For this purpose, we train a neural network model with BIOE-tagged (Beginning, Inside, End, and Outside) cardiology entities. Transfer Learning can be used to facilitate the curation of an interface terminology for highlighting EHRs for other specialties e.g. Nephrology. Large-scale highlighting enables overworked physicians and other healthcare providers to fast skim the dense volume of EHRs they regularly read. Secondary research and EHRs interoperability are other applications that can be supported by highlighting.

Under the circumstances prevalent in current healthcare, medical professionals such as physicians and nurses need to read large numbers of Electronic Health Record (EHR) notes. This demand fosters a situation in which providers typically do not read a whole note but quickly skim it, to capture its essential content. Consequently, by fast skimming, one may miss a critical medical fact. Annotation highlights important content in EHR notes, and enables healthcare professionals to perform fast skimming, thereby minimizing the risk of missing critical information, which is detrimental to patient care. We designed the Cardiology Interface Terminology (CIT) for the purpose of annotation of cardiology EHRs. We emphasize that by annotation we refer to highlighting important information in the EHR notes for enabling fast skimming rather than just recognizing names of diseases, drugs, etc. from Reference Terminologies as is usually done by existing Named Entity Recognition (NER) systems. The CIT design starts with the cardiology components of SNOMED CT. It is enhanced by mining phrases from cardiology EHRs, as potential CIT concepts, which are of higher granularity than SNOMED concepts. Machine learning (ML), the state of the art technique for mining concepts from EHRs, requires training data. However, there is no training data for designing CIT. In the first stage, we introduce an innovative semi-automatic method for mining concepts from EHRs, to replace costly manual mining. The only manual portion is the review of the automatically mined phrases, before their insertion as CIT concepts. The effectiveness of annotation of cardiology EHRs with CIT was evaluated utilizing proper metrics, and compared to annotation with SNOMED CT. In a future second stage, ML mining techniques will be used for enhancing CIT with extra concepts from EHRs, utilizing the concepts added in the first stage as training data. This work focuses on a novel semi-automated method to design the Cardiology Interface Terminology (CIT) for annotation of cardiology EHRs to support fast skimming of EHR notes. Similar interface terminologies for other medical specialties could be obtained from CIT using Transfer Learning.

Clinical data stored in EHRs could provide valuable knowledge for research if it were annotated properly. However, almost no EHR notes are currently annotated as the performance of off the shelf annotation tools is unsatisfactory. Concentrating on the cardiology specialty, we propose to design a Cardiology Interface Terminology dedicated to the annotation of EHR notes in cardiology. This interface terminology will be developed by the addition of high granularity concepts, mined from cardiology EHR notes, to an initial version reusing SNOMED CT cardiology subhierarchies. Using text mining NLP tools with machine learning for extending this interface terminology requires proper training data. In this paper, we discuss concept-mining of EHR notes, using concatenation and anchoring operations iteratively to create such training data. This approach can be applied to other medical specialties.

The COVID-19 pandemic has overwhelmed the healthcare services of many countries with increased number of patients and also with a deluge of medical data. Furthermore, the emergence and global spread of new infectious diseases are highly likely to continue in the future. Incomplete data about presentations, signs, and symptoms of COVID-19 has had adverse effects on healthcare delivery. The EHRs of US hospitals have ingested huge volumes of relevant, up-to-date data about patients, but the lack of a proper system to annotate this data has greatly reduced its usefulness. We propose to design a COVID interface terminology for the annotation of EHR notes of COVID-19 patients. The initial version of this interface terminology was created by integrating COVID concepts from existing ontologies. Further enrichment of the interface terminology is performed by mining high granularity concepts from EHRs, because such concepts are usually not present in the existing reference terminologies. We use the techniques of concatenation and anchoring iteratively to extract high granularity phrases from the clinical text. In addition to increasing the conceptual base of the COVID interface terminology, this will also help in generating training data for large scale concept mining using machine learning techniques. Having the annotated clinical notes of COVID-19 patients available will help in speeding up research in this field.

OBJECTIVE: The study sought to describe the literature related to the development of methods for auditing the Unified Medical Language System (UMLS), with particular attention to identifying errors and inconsistencies of attributes of the concepts in the UMLS Metathesaurus. MATERIALS AND METHODS: We applied the PRISMA (Preferred Reporting Items for Systematic Reviews and Meta-Analyses) approach by searching the MEDLINE database and Google Scholar for studies referencing the UMLS and any of several terms related to auditing, error detection, and quality assurance. A qualitative analysis and summarization of articles that met inclusion criteria were performed. RESULTS: Eighty-three studies were reviewed in detail. We first categorized techniques based on various aspects including concepts, concept names, and synonymy (n = 37), semantic type assignments (n = 36), hierarchical relationships (n = 24), lateral relationships (n = 12), ontology enrichment (n = 8), and ontology alignment (n = 18). We also categorized the methods according to their level of automation (ie, automated systematic, automated heuristic, or manual) and the type of knowledge used (ie, intrinsic or extrinsic knowledge). CONCLUSIONS: This study is a comprehensive review of the published methods for auditing the various conceptual aspects of the UMLS. Categorizing the auditing techniques according to the various aspects will enable the curators of the UMLS as well as researchers comprehensive easy access to this wealth of knowledge (eg, for auditing lateral relationships in the UMLS). We also reviewed ontology enrichment and alignment techniques due to their critical use of and impact on the UMLS.

The Unified Medical Language System (UMLS) is an important terminological system. By the policy of its curators, each concept of the UMLS should be assigned the most specific Semantic Types (STs) in the UMLS Semantic Network (SN). Hence, the Semantic Types of most UMLS concepts are assigned at or near the bottom (leaves) of the UMLS Semantic Network. While most ST assignments are correct, some errors do occur. Therefore, Quality Assurance efforts of UMLS curators for ST assignments should concentrate on automatically detected sets of UMLS concepts with higher error rates than random sets. In this paper, we investigate the assignments of top-level semantic types in the UMLS semantic network to concepts, identify potential erroneous assignments, define four categories of errors, and thus provide assistance to curators of the UMLS to avoid these assignments errors. Human experts analyzed samples of concepts assigned 10 of the top-level semantic types and categorized the erroneous ST assignments into these four logical categories. Two thirds of the concepts assigned these 10 top-level semantic types are erroneous. Our results demonstrate that reviewing top-level semantic type assignments to concepts provides an effective way for UMLS quality assurance, comparing to reviewing a random selection of semantic type assignments.

The Gene hierarchy of the National Cancer Institute (NCI) Thesaurus (NCIt) is of high priority for NCI. It is important to have quality assurance (QA) techniques to improve its content quality. We present a two-step methodology concentrating on auditing the modeling of complex concepts, which are shown to have a higher error rate compared to control concepts. In the first step, we test whether concepts that appear complex in a so called “partial-area taxonomy” have a higher error rate than control concepts. In the second step, we introduce an innovative technique based on a “partial-area sub-taxonomy” (constructed with a subset of roles) to discover additional complex concepts. The results of the QA study show that these concepts are indeed statistically significantly more likely to have more errors than control concepts. This makes it easier for NCI staff to improve the modeling quality of gene concepts in NCIt.

SNOMED CT is important for clinical applications, such as Electronic Health Record (EHR) encoding. However, inconsistency in modeling its concepts may prevent SNOMED CT from providing proper support for clinical use. This study provides an effective methodology for locating inconsistently modeled SNOMED CT concepts. One can expect lexically similar concepts to be modeled similarly. Positional similarity sets, sets of lexically similar concepts having only one different word at the same position of their names, are introduced. Concepts in such sets have a higher likelihood of being unjustifiably inconsistently modeled. A technique to incorporate three structural indicators into the selected sets is provided to further improve the likelihood of finding inconsistently modeled concepts. An analysis of a sample of 50 such sets and for each of these three indicators is performed. The sample of positional similarity sets is found to have 18.6% inconsistent concepts. The use of structural indicators is shown to further improve the likelihood of finding inconsistently modeled concepts up to 41.6% with high statistical significance when compared to the previous sample of positional similarity sets. Positional similarity sets with different structural indicators are shown to help identify inconsistencies in concept modeling with high likelihood. Furthermore, such sets enable the comparison of concept modeling in the context of other lexically similar concepts, which enhances the effectiveness of corrections by auditors. Such quality assurance methods can be used to supplement IHTSDO's own efforts in order to improve the quality of SNOMED CT.

Terminologies are typically large and complex knowledge systems. It is difficult to obtain an orientation into their structure and content. In previous research we designed compact summary networks called partial-area taxonomies to provide a structural summary of a terminology. The sizes of a terminology and of its partial-area taxonomy are defined as their numbers of nodes. While a partial-area taxonomy is typically smaller than the original terminology, it is often not compact enough to provide a clear “big picture,” due to too many nodes that summarize only a small number of terminology concepts. The display of such a partial-area taxonomy is still overwhelming. In this paper, we introduce a more compact summary of a terminology, called an aggregate taxonomy, obtained by aggregating small partial-area taxonomy nodes into larger nodes. We present a parametrized technique to study the design of such an aggregate taxonomy and apply it to the Specimen hierarchy of SNOMED CT. A software tool for creating and displaying aggregate taxonomies is described. We illustrate how aggregate taxonomies derived across multiple SNOMED CT releases can be used to summarize the evolution of the Specimen hierarchy's content over eight years of SNOMED CT releases.

OBJECTIVE: Large and complex terminologies, such as Systematized Nomenclature of Medicine-Clinical Terms (SNOMED CT), are prone to errors and inconsistencies. Abstraction networks are compact summarizations of the content and structure of a terminology. Abstraction networks have been shown to support terminology quality assurance. In this paper, we introduce an abstraction network derivation methodology which can be applied to SNOMED CT target hierarchies whose classes are defined using only hierarchical relationships (ie, without attribute relationships) and similar description-logic-based terminologies. METHODS: We introduce the tribal abstraction network (TAN), based on the notion of a tribe-a subhierarchy rooted at a child of a hierarchy root, assuming only the existence of concepts with multiple parents. The TAN summarizes a hierarchy that does not have attribute relationships using sets of concepts, called tribal units that belong to exactly the same multiple tribes. Tribal units are further divided into refined tribal units which contain closely related concepts. A quality assurance methodology that utilizes TAN summarizations is introduced. RESULTS: A TAN is derived for the Observable entity hierarchy of SNOMED CT, summarizing its content. A TAN-based quality assurance review of the concepts of the hierarchy is performed, and erroneous concepts are shown to appear more frequently in large refined tribal units than in small refined tribal units. Furthermore, more erroneous concepts appear in large refined tribal units of more tribes than of fewer tribes. CONCLUSIONS: In this paper we introduce the TAN for summarizing SNOMED CT target hierarchies. A TAN was derived for the Observable entity hierarchy of SNOMED CT. A quality assurance methodology utilizing the TAN was introduced and demonstrated.

OBJECTIVE: Standards terminologies may be large and complex, making their quality assurance challenging. Some terminology quality assurance (TQA) methodologies are based on abstraction networks (AbNs), compact terminology summaries. We have tested AbNs and the performance of related TQA methodologies on small terminology hierarchies. However, some standards terminologies, for example, SNOMED, are composed of very large hierarchies. Scaling AbN TQA techniques to such hierarchies poses a significant challenge. We present a scalable subject-based approach for AbN TQA. METHODS: An innovative technique is presented for scaling TQA by creating a new kind of subject-based AbN called a subtaxonomy for large hierarchies. New hypotheses about concentrations of erroneous concepts within the AbN are introduced to guide scalable TQA. RESULTS: We test the TQA methodology for a subject-based subtaxonomy for the Bleeding subhierarchy in SNOMED's large Clinical finding hierarchy. To test the error concentration hypotheses, three domain experts reviewed a sample of 300 concepts. A consensus-based evaluation identified 87 erroneous concepts. The subtaxonomy-based TQA methodology was shown to uncover statistically significantly more erroneous concepts when compared to a control sample. DISCUSSION: The scalability of TQA methodologies is a challenge for large standards systems like SNOMED. We demonstrated innovative subject-based TQA techniques by identifying groups of concepts with a higher likelihood of having errors within the subtaxonomy. Scalability is achieved by reviewing a large hierarchy by subject. CONCLUSIONS: An innovative methodology for scaling the derivation of AbNs and a TQA methodology was shown to perform successfully for the largest hierarchy of SNOMED.

OBJECTIVE: Little information exists concerning SNOMED CT (systematized nomenclature of medicine-clinical terms) users. This report describes current impressions and preferences of direct SNOMED CT users regarding coverage, quality, and concept details, and the change request mechanism. DESIGN: A 43-question anonymous survey distributed electronically to relevant online communities. MEASUREMENTS: Data on user demographic characteristics, modes and purposes of use, means and frequencies of access, satisfaction with SNOMED CT content coverage and quality and with the change request mechanism were recorded. RESULTS: The survey was conducted in January 2010 and elicited 215 responses. Details regarding users' profiles, modes of use and access were reported elsewhere. The coverage of SNOMED CT was perceived to be at least 85% complete by 42% of responders, and 60% were at least satisfied with its quality. Various deficiencies were encountered at least 'somewhat often' by 28-61% of responders. Incorrect data were more bothersome than missing data. Users indicated that significant resources should be allocated to more consistent and complete conceptual representations and to further enhance content coverage. Enhanced synonym coverage and the introduction of textual definitions were important to users (54% and 63%, respectively). LIMITATIONS: A survey format with limited control over recruitment and selection bias. Lack of information regarding the SNOMED CT version used by responders. CONCLUSION: Despite overall satisfaction, direct users indicated a strong desire to improve consistency, quality, and completeness of conceptual representations and concept details, as well as a continued desire to expand coverage. The survey provides much needed data for informed decisions regarding the use and development goals of SNOMED CT. Focused periodical surveys are warranted.

OBJECTIVE: Each Unified Medical Language System (UMLS) concept is assigned one or more semantic types (ST). A dynamic methodology for aiding an auditor in finding concepts that are missing the assignment of a given ST, S is presented. DESIGN: The first part of the methodology exploits the previously introduced Refined Semantic Network and accompanying refined semantic types (RST) to help narrow the search space for offending concepts. The auditing is focused in a neighborhood surrounding the extent of an RST, T (of S) called an envelope, consisting of parents and children of concepts in the extent. The audit moves outward as long as missing assignments are discovered. In the second part, concepts not reached previously are processed and reassigned T as needed during the processing of S's other RSTs. The set of such concepts is expanded in a similar way to that in the first part. MEASUREMENTS: The number of errors discovered is reported. To measure the methodology's efficiency, "error hit rates" (i.e., errors found in concepts examined) are computed. RESULTS: The methodology was applied to three STs: Experimental Model of Disease (EMD), Environmental Effect of Humans, and Governmental or Regulatory Activity. The EMD experienced the most drastic change. For its RST "EMD intersection Neoplastic Process" (RST "EMD") with only 33 (31) original concepts, 915 (134) concepts were found by the first (second) part to be missing the EMD assignment. Changes to the other two STs were smaller. CONCLUSION: The results show that the proposed auditing methodology can help to effectively and efficiently identify concepts lacking the assignment of a particular semantic type.

OBJECTIVE: Chemical concepts assigned multiple "Chemical Viewed Structurally" semantic types (STs) in the Unified Medical Language System (UMLS) are subject to ambiguous interpretation. The multiple assignments may denote the fact that a specific represented chemical (combination) is a conjugate, derived via a chemical reaction of chemicals of the different types, or a complex, composed of a mixture of such chemicals. The previously introduced Refined Semantic Network (RSN) is modified to properly model these varied multi-typed chemical combinations. DESIGN: The RSN was previously introduced as an enhanced abstraction of the UMLS's concepts. It features new types, called intersection semantic types (ISTs), each of which explicitly captures a unique combination of ST assignments in one abstract unit. The ambiguous ISTs of different "Chemical Viewed Structurally" ISTs of the RSN are replaced with two varieties of new types, called conjugate types and complex types, which explicitly denote the nature of the chemical interactions. Additional semantic relationships help further refine that new portion of the RSN rooted at the ST "Chemical Viewed Structurally." MEASUREMENTS: The number of new conjugate and complex types and the amount of changes to the type assignment of chemical concepts are presented. RESULTS: The modified RSN, consisting of 35 types and featuring 22 new conjugate and complex types, is presented. A total of 800 (about 98%) chemical concepts representing multi-typed chemical combinations from "Chemical Viewed Structurally" STs are uniquely assigned one of the new types. An additional benefit is the identification of a number of illegal ISTs and ST assignment errors, some of which are direct violations of exclusion rules defined by the UMLS Semantic Network. CONCLUSION: The modified RSN provides an enhanced abstract view of the UMLS's chemical content. Its array of conjugate and complex types provides a more accurate model of the variety of combinations involving chemicals viewed structurally. This framework will help streamline the process of type assignments for such chemical concepts and improve user orientation to the richness of the chemical content of the UMLS.

OBJECTIVES: The UMLS constitutes the largest existing collection of medical terms. However, little has been published about the users and uses of the UMLS. This study sheds light on these issues. DESIGN: We designed a questionnaire consisting of 26 questions and distributed it to the UMLS user mailing list. Participants were assured complete confidentiality of their replies. To further encourage list members to respond, we promised to provide them with early results prior to publication. Sector analysis of the responses, according to employment organizations is used to obtain insights into some responses. RESULTS: We received 70 responses. The study confirms two intended uses of the UMLS: access to source terminologies (75%), and mapping among them (44%). However, most access is just to a few sources, led by SNOMED, MeSH, and ICD. Out of 119 reported purposes of use, terminology research (37), information retrieval (19), and terminology translation (14) lead. Four important observations are that the UMLS is widely used as a terminology (77%), even though it was not designed as one; many users (73%) want the NLM to mark concepts with multiple parents in an indented hierarchy and to derive a terminology from the UMLS (73%). Finally, auditing the UMLS is a top budget priority (35%) for users. CONCLUSIONS: The study reports many uses of the UMLS in a variety of subjects from terminology research to decision support and phenotyping. The study confirms that the UMLS is used to access its source terminologies and to map among them. Two primary concerns of the existing user base are auditing the UMLS and the design of a UMLS-based derived terminology.

OBJECTIVE: To develop and test an auditing methodology for detecting errors in medical terminologies satisfying systematic inheritance. This methodology is based on various abstraction taxonomies that provide high-level views of a terminology and highlight potentially erroneous concepts. DESIGN: Our auditing methodology is based on dividing concepts of a terminology into smaller, more manageable units. First, we divide the terminology's concepts into areas according to their relationships/roles. Then each multi-rooted area is further divided into partial-areas (p-areas) that are singly-rooted. Each p-area contains a set of structurally and semantically uniform concepts. Two kinds of abstraction networks, called the area taxonomy and p-area taxonomy, are derived. These taxonomies form the basis for the auditing approach. Taxonomies tend to highlight potentially erroneous concepts in areas and p-areas. Human reviewers can focus their auditing efforts on the limited number of problematic concepts following two hypotheses on the probable concentration of errors. RESULTS: A sample of the area taxonomy and p-area taxonomy for the Biological Process (BP) hierarchy of the National Cancer Institute Thesaurus (NCIT) was derived from the application of our methodology to its concepts. These views led to the detection of a number of different kinds of errors that are reported, and to confirmation of the hypotheses on error concentration in this hierarchy. CONCLUSION: Our auditing methodology based on area and p-area taxonomies is an efficient tool for detecting errors in terminologies satisfying systematic inheritance of roles, and thus facilitates their maintenance. This methodology concentrates a domain expert's manual review on portions of the concepts with a high likelihood of errors.

OBJECTIVE: The Enriched Semantic Network (ESN) was introduced as an extension of the Unified Medical Language System (UMLS) Semantic Network (SN). Its multiple subsumption configuration and concomitant multiple inheritance make the ESN's relationship structures and semantic type assignments different from those of the SN. A technique for deriving the relationship structures of the ESN's semantic types and an automated technique for deriving the ESN's semantic type assignments from those of the SN are presented. DESIGN: The technique to derive the ESN's relationship structures finds all newly inherited relationships in the ESN. All such relationships are audited for semantic validity, and the blocking mechanism is used to block invalid relationships. The mapping technique to derive the ESN's semantic type assignments uses current SN semantic type assignments and preserves nonredundant categorizations, while preventing new redundant categorizations. RESULTS: Among the 426 newly inherited relationships, 326 are deemed valid. Seven blockings are applied to avoid inheritance of the 100 invalid relationships. Sixteen semantic types have different relationship structures in the ESN as compared to those in the SN. The mapping of semantic type assignments from the SN to the ESN avoids the generation of 26,950 redundant categorizations. The resulting ESN contains 138 semantic types, 149 IS-A links, 7,303 relationships, and 1,013,876 semantic type assignments. CONCLUSION: The ESN's multiple inheritance provides more complete relationship structures than in the SN. The ESN's semantic type assignments avoid the existing redundant categorizations appearing in the SN and prevent new ones that might arise due to multiple parents. Compared to the SN, the ESN provides a more accurate unifying semantic abstraction of the UMLS Metathesaurus.

OBJECTIVE: The Unified Medical Language System's (UMLS's) Semantic Network's (SN's) two-tree structure is restrictive because it does not allow a semantic type to be a specialization of several other semantic types. In this article, the SN is expanded into a multiple subsumption structure with a directed acyclic graph (DAG) IS-A hierarchy, allowing a semantic type to have multiple parents. New viable IS-A links are added as warranted. DESIGN: Two methodologies are presented to identify and add new viable IS-A links. The first methodology is based on imposing the characteristic of connectivity on a previously presented partition of the SN. Four transformations are provided to find viable IS-A links in the process of converting the partition's disconnected groups into connected ones. The second methodology identifies new IS-A links through a string matching process involving names and definitions of various semantic types in the SN. A domain expert is needed to review all the results to determine the validity of the new IS-A links. RESULTS: Nineteen new IS-A links are added to the SN, and four new semantic types are also created to support the multiple subsumption framework. The resulting network, called the Enriched Semantic Network (ESN), exhibits a DAG-structured hierarchy. A partition of the ESN containing 19 connected groups is also derived. CONCLUSION: The ESN is an expanded abstraction of the UMLS compared with the original SN. Its multiple subsumption hierarchy can accommodate semantic types with multiple parents. Its representation thus provides direct access to a broader range of subsumption knowledge.

Abstract A semantic relationship is a data modeling construct that connects a pair of classes or categories and has inherent constraints and other functionalities that precisely reflect the characteristics of the specific relationship in an application domain. Examples of semantic relationships include part–whole, ownership, materialization and role‐of. Such relationships are important in the construction of information models for advanced applications, whether one is employing traditional data‐modeling techniques, knowledge‐representation languages or object‐oriented modeling methodologies. This paper focuses on the issue of providing built‐in support for such constructs in the context of object‐oriented database (OODB) systems. Most of the popular object‐oriented modeling approaches include some semantic relationships in their repertoire of data‐modeling primitives. However, commercial OODB systems, which are frequently used as implementation vehicles, tend not to do the same. We will present two frameworks by which a semantic relationship can be incorporated into an existing OODB system. The first only requires that the OODB system support manifest type with respect to its instances. The second assumes that the OODB system has a special kind of metaclass facility. The two frameworks are compared and contrasted. In order to ground our work in existing systems, we show the addition of a part–whole semantic relationship both to the ONTOS DB/Explorer OODB system and the VODAK Model Language. Copyright © 2003 John Wiley & Sons, Ltd.

Abstract In previous work, we have modeled a vocabulary given as a semantic network by an object‐oriented database (OODB). The OODB schema thus obtained provides a compact abstract view of the vocabulary. This enables the fast traversal of the vocabulary by a user. In the semantic network vocabulary, the IS‐A relationships express the specialization hierarchy. In our OODB modeling of the vocabulary, the SUBCLASS relationship expresses the specialization hierarchy of the classes and supports the inheritance of their properties. A typical IS‐A path in the vocabulary has a corresponding shorter SUBCLASS path in the OODB schema. In this paper we expose several cases where the SUBCLASS hierarchy fails to fully correspond to the IS‐A hierarchy of the vocabulary. In these cases there exist traversal paths in the semantic network for which there are no corresponding traversal paths in the OODB schema. The reason for this failure is the existence of some IS‐A relationships between concepts of two classes, which are not connected by a SUBCLASS relationship. This phenomenon weakens the accuracy of our modeling. To rectify the situation we introduce a new OODB semantic relationship IS‐A$'$ to represent the existence of IS‐A relationships between concepts of a pair of classes which are not connected via a SUBCLASS relationship. The resulting schema contains both SUBCLASS relationships and IS‐A$'$ relationships which completely model the IS‐A hierarchy of the vocabulary. We define a mixed‐class level traversal path to contain either SUBCLASS or IS‐A$'$ relationships. Consequently, each traversal path in the semantic network has a corresponding mixed traversal path in the OODB schema. Hence the introduction of the semantic OODB IS‐A$'$ relationship improves the modeling of semantic network vocabularies by OODBs. Copyright © 2003 John Wiley & Sons, Ltd.

The unified medical language system (UMLS) integrates many well-established biomedical terminologies. The UMLS semantic network (SN) can help orient users to the vast knowledge content of the UMLS Metathesaurus (META) via its abstract conceptual view. However, the SN itself is large and complex and may still be difficult to comprehend. Our technique partitions the SN into smaller meaningful units amenable to display on limited-sized computer screens. The basis for the partitioning is the distribution of the relationships within the SN. Three rules are applied to transform the original partition into a second more cohesive partition.

Semantic networks (SNs) are excellent knowledge representation structures. However, large semantic networks are hard to comprehend. To overcome this difficulty, several methods of partitioning have been developed that rely on different mixes of structural and semantic methods. However, little has appeared in the literature concerning the question whether a partition of a semantic network creates subnetworks that agree with human insight. We address this issue by presenting a comparison between the results of an algorithmic partitioning method and a partition created by a group of experts. Subsequently, we show how a network partition can be used to generate various partial views of a semantic network, which facilitate user orientation. Examples from the Unified Medical Language System (UMLS) SN are used to demonstrate partial views.

Controlled vocabularies (CVs) are networks of concepts that unify disparate terminologies and facilitate the process of information sharing within an application domain. We describe a general methodology for representing an existing CV as an object-oriented database (OODB), called an object-oriented vocabulary repository (OOVR). A formal description of the OOVR methodology, which is based on a structural abstraction technique, is given, along with an algorithmic description and a number of theorems pertaining to some of the methodology's formal characteristics. An OOVR offers a two-level (concept level and schema level) view of a CV, with the schema-level view serving as an important abstraction that can aid in orientation to the CV's contents. While an OOVR can also assist in traversals of the CV, we have identified certain special CV configurations where such traversals can be problematic. To address this, we introduce - based on the original methodology - an enhanced OOVR methodology that utilizes both structural and semantic features to partition and model a CV's constituent concepts. With its basis in the notions of area and the recursively defined articulation concept, an enhanced OOVR representation provides users with an improved CV view comprising groups of concepts that are uniform both in their structure and semantics. An algorithmic description of the singly-rooted OOVR methodology and theorems describing some of its formal properties are given. The results of applying it to a large existing CV are discussed.

OBJECTIVE: The Unified Medical Language System (UMLS) combines many well-established authoritative medical informatics terminologies in one knowledge representation system. Such a resource is very valuable to the health care community and industry. However, the UMLS is very large and complex and poses serious comprehension problems for users and maintenance personnel. The authors present a representation to support the user's comprehension and navigation of the UMLS. DESIGN: An object-oriented database (OODB) representation is used to represent the two major components of the UMLS-the Metathesaurus and the Semantic Network-as a unified system. The semantic types of the Semantic Network are modeled as semantic type classes. Intersection classes are defined to model concepts of multiple semantic types, which are removed from the semantic type classes. RESULTS: The authors provide examples of how the intersection classes help expose omissions of concepts, highlight errors of semantic type classification, and uncover ambiguities of concepts in the UMLS. The resulting UMLS OODB schema is deeper and more refined than the Semantic Network, since intersection classes are introduced. The Metathesaurus is classified into more mutually exclusive, uniform sets of concepts. The schema improves the user's comprehension and navigation of the Metathesaurus. CONCLUSIONS: The UMLS OODB schema supports the user's comprehension and navigation of the Metathesaurus. It also helps expose and resolve modeling problems in the UMLS.

OBJECTIVE: Controlled medical terminologies (CMTs) have been recognized as important tools in a variety of medical informatics applications, ranging from patient-record systems to decision-support systems. Controlled medical terminologies are typically organized in semantic network structures consisting of tens to hundreds of thousands of concepts. This overwhelming size and complexity can be a serious barrier to their maintenance and widespread utilization. The authors propose the use of object-oriented databases to address the problems posed by the extensive scope and high complexity of most CMTs for maintenance personnel and general users alike. DESIGN: The authors present a methodology that allows an existing CMT, modeled as a semantic network, to be represented as an equivalent object-oriented database. Such a representation is called an object-oriented health care terminology repository (OOHTR). RESULTS: The major benefit of an OOHTR is its schema, which provides an important layer of structural abstraction. Using the high-level view of a CMT afforded by the schema, one can gain insight into the CMT's overarching organization and begin to better comprehend it. The authors' methodology is applied to the Medical Entities Dictionary (MED), a large CMT developed at Columbia-Presbyterian Medical Center. Examples of how the OOHTR schema facilitated updating, correcting, and improving the design of the MED are presented. CONCLUSION: The OOHTR schema can serve as an important abstraction mechanism for enhancing comprehension of a large CMT, and thus promotes its usability.

Controlled vocabularies have been used as the means for unifying disparate terminologies found within an application field. This unification leads to better administration of information and enhanced communication among various parties. Semantic networks have been shown to be excellent vehicles for modeling controlled vocabularies. However, they often lack the necessary access flexibility and robustness required by external agents such as intelligent information-locators and decision-support systems. In this paper, we describe the process of mapping an existing medical vocabulary based on a semantic network model into an Object-Oriented Database (OODB) system. We first consider two straightforward approaches to carrying out this task and describe their deficiencies. We then present a new approach which yields a very compact OODB schema for the representation of the vocabulary's entire hierarchy and inter-connectivity. We refer to the resulting OODB as the Object-Oriented Healthcare Voc...

The work is motivated by the desire to develop methods to comprehend large vocabularies and large schemas of object-oriented databases. The ability of a user of a database participating in a federated system to retrieve information from the other database systems will be greatly enhanced by acquiring a better comprehension of these systems. The authors are trying to develop both a theoretical paradigm and a methodology to analyze existing large schemas. Their approach to achieve comprehension is based on combining two concepts: informational thinning (i.e. concentration on the specialization hierarchy of the schema) and partitioning. They present a new technique for modeling which is called disciplined modeling. Based on the rules of disciplined modeling we develop a theoretical paradigm to support the existence of a meaningful forest hierarchy within the specialization hierarchy. Such a hierarchy functions as a skeleton of the schema and supports comprehension and partitioning efforts.

The part-whole semantic relationship (the part relationship, for short) is an important modeling primitive in many advanced application domains such as manufacturing, design, and document processing. In this paper, we examine the problem of integrating such a construct into an OODB system. Specifically, two questions are addressed in this regard. This first is: Can a part relationship be made an intrinsic construct of an existing OODB system without having to rewrite a substantial portion of the system? The second: Can an “open” OODB system which claims to support such an integration really do so, and, more specifically, can the integration be done using a metaclass mechanism which purports to bring extensibility to the VODAK Model Language (VML)?

Derived schema components are an important aspect of traditional semantic data modeling.In this paper, we address the issue of defining

A path-method is used as a mechanism in object-Our experiments show that the traversal algorithm of PMG is a very successful tool for aiding the user with the dificult task of querying and updating a large OODB.

Article The new class of g-chain periodic sorters Share on Authors: Ronald I. Becker View Profile , David Nassimi View Profile , Yehoshua Perl View Profile Authors Info & Claims SPAA '93: Proceedings of the fifth annual ACM symposium on Parallel Algorithms and ArchitecturesAugust 1993 Pages 356–364https://doi.org/10.1145/165231.157378Online:01 August 1993Publication History 4citation147DownloadsMetricsTotal Citations4Total Downloads147Last 12 Months1Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

The inefficiency of interpolation search for an alphabetic table has been demonstrated by F.W. Burton and G.N. Lewis (1980). This inefficiency is expected since such tables are usually far from uniform in distribution. However, for nonuniformly distributed tables for which the cumulative distribution function F is known, applying F to the keys yields uniform distribution for which interpolation search is very fast. In arithmetic coding a string of characters is mapped into the (0, 1) interval according to the probabilities of its characters. It is found that this transformation, designed for data compression, is actually the cumulative distribution function F for alphabetic tables. Experiments confirm that interpolation search on alphabetic tables, applying arithmetic coding to the character strings in a sophisticated way, shows a performance very close to lg lg n accesses. Hence, a new fast search technique for alphabetic tables is designed.>

Both algorithms are adaptive and require no extra communication from the encoder to the decoder. The authors present a scheme to cascade these into an adaptive algorithm which achieves higher compression ratio and is appropriate for communication. Different refinements of the cascading are tested to optimize the secondary compression.>

A periodic sorting network consists of a sequence of identical blocks. In this paper, the periodic balanced sorting network, which consists of log n blocks, is introduced. Each block, called a balanced merging block, merges elements on the even input lines with those on the odd input lines. The periodic balanced sorting network sorts n items in O ([log n ] 2 ) time using ( n /2)(log n ) 2 comparators. Although these bounds are comparable to many existing sorting networks, the periodic structure enables a hardware implementation consisting of only one block with the output of the block recycled back as input until the output is sorted. An implementation of our network on the shuffle exchange interconnection model in which the direction of the comparators are all identical and fixed is also presented.

Abstract We construct a digraph with the maximum number of simple paths between two specified vertices, for a digraph with a given number of edges. The following cases are considered: digraphs with parallel edges, acyclic simple digraphs and general simple digraphs. The corresponding extremal digraphs are the tri‐chains, the (deficient) Fibonacci digraphs and (if our conjecture is true) the 3‐diamond strings, respectively. The similarity of these three families of digraphs is discussed. The related problem of digraphs with the maximum number of simple cycles for a given number of edges is considered too.

Although it is well-known that Huffman Codes are optimal for text compression in a character-per-character encoding scheme, they are seldom used in practical situations since they require a bit-per-bit decoding algorithm, which has to be written in some assembly language, and will perform rather slowly. A number of methods are presented that avoid these difficulties. The decoding algorithms efficiently process the encoded string on a byte-per-byte basis, are faster than the original algorithm, and can be programmed in any high level language. This is achieved at the cost of storing some tables in the internal memory, but with no loss in the compression savings of the optimal Huffman codes. The internal memory space needed can be reduced either at the cost of increased processing time, or by using non-binary Huffman codes, which give sub-optimal compression. Experimental results for English and Hebrew text are also presented.

Cographs are the graphs formed from a single vertex under the closure of the operations of union and complement. Another characterization of cographs is that they are the undirected graphs with no induced paths on four vertices. Cographs arise naturally in such application areas as examination scheduling and automatic clustering of index terms. Furthermore, it is known that cographs have a unique tree representation called a cotree. Using the cotree it is possible to design very fast polynomial time algorithms for problems which are intractable for graphs in general. Such problems include chromatic number, clique determination, clustering, minimum weight domination, isomorphism, minimum fill-in and Hamiltonicity. In this paper we present a linear time algorithm for recognizing cographs and constructing their cotree representation.

Abstract We consider the following problem: Given an integer k and a network G with two distinct vertices s and t, find a maximum number of vertex disjoint paths from s to t of length bounded by k. In a recent work [9] it was shown that for length greater than four this problem is NP‐hard. In this paper we present a polynomial heuristic algorithm for the problem for general length. The algorithm is proved to give optimal solution for length less than five. Experiments show very good results for the algorithm.

This paper introduces a new sorting network, called the balanced sorting network, that sorts n items in O([lgn]2) time using (n/2)(lgn)2 comparators. Although these bounds are comparable to many existing sorting networks, the balanced sorting network possess some distinct advantages. In particular, its structure is highly regular consisting of a sequence of identicalbalanced merging networks. We prove that lg n identical merging networks are both necessary and sufficient to sort n items. We also present an explicit implementation of our network on the shuffle exchange interconnection model in which the direction of the comparitors are all identical and fixed.

Abstract The problem of partitioning a circuit into subcomponents with constraints on the size of each subcomponent and the number of external connections is examined. While this problem is shown to be NP‐complete even for very restricted cases, a pseudo‐polynomial dynamic programming algorithm is given for the case where the circuit has a tree structure.

The problem of finding a mm-max partmon of a weJghted tree T with n veruces into q subtrees by means of k = q -1 cuts is considered.A top-down shifting algorithm for this problem ts presented An outhne is given of an efficJent implementatmn of the algorithm wtth complexity O(k3rd(T) + kn), where rd(T) ts the number of edges m the radius of T Categories and Subject Descriptors F 2 2 [Analysis of Algorithms and Problem Complexity].Nonnumencai Algorithms and Problems; G 2 2 [Discrete Mathematics]' Graph Theory--network problems, trees General Terms.

Abstract The following problem is considered: Given an integer K, a graph G with two distinct vertices s and t, find the maximum number of disjoint paths of length K from s to t. The problem has several variants: the paths may be vertex‐disjoint or edge‐disjoint, the lengths of the paths may be equal to K or bounded by K, the graph may be undirected or directed. It is shown that except for small values of K all the problems are NP‐complete. Assuming P ≠ NP, for each problem, the largest value of K for which the problem is not NP‐complete is found. Whenever a polynomial algorithm exists, an efficient algorithm is described.

The max-rain k-partition algorithm may be formulated as follows: Given a tree T with n edges and a nonnegative weight associated with each vertex, assign a cut to each of k distinct edges of T so as to maximize the weight of the lightest resulting connected subtree.An algorithm for this problem is presented which initially assigns all k cuts to one edge incident with a terminal vertex of T; thereafter the cuts are shifted from edge to adjacent edge on the basis of local information.An efficient implementation with complexity O(k 2. rd(T) + kn), where rd(T) is the number of edges in the radius of T, is described.An algorithm for a simpler problem, namely, the partitioning of Tinto the maximum number of connected components whose weight is bounded below, is then described.Combined with the technique of binary search, it yields an alternative algorithm for the max-rain k-partition problem with complexity dependent on the range of the given weights.

Abstract Horn's algorithm for weighted mean flow scheduling with treelike precedence constraints is reexamined. A new analysis of an efficient implementation of Horn's algorithm shows an O(n log n) complexity. This is an improvement on the known O(n2) complexity of this algorithm. An application of Horn's algorithm to a problem of optimal scheduling of a treelike communication network is presented.

article Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph Share on Authors: Y. Shiloach Weizmann Institute of Science, Rehovot, Israel and Computer Science Department, Stanford University, Stanford, CA Weizmann Institute of Science, Rehovot, Israel and Computer Science Department, Stanford University, Stanford, CAView Profile , Y. Perl Department of Mathematics and Computer Science, Bar-Ilan University, Ramat-Gan, Israel Department of Mathematics and Computer Science, Bar-Ilan University, Ramat-Gan, IsraelView Profile Authors Info & Claims Journal of the ACMVolume 25Issue 1Jan. 1978 pp 1–9https://doi.org/10.1145/322047.322048Published:01 January 1978 98citation1,915DownloadsMetricsTotal Citations98Total Downloads1,915Last 12 Months47Last 6 weeks5 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

ABSTRACrr.An algorithm for constructing an optimal prefix code of n eqmprobable words over r unequal cost coding letters is given.The discussion is in terms of rooted labeled trees.The algorithm consists of two parts.The first one is an extension algorithm which constructs a prefix code of n words.This code is either optimal or is a "good" approximation The second part is a mending algorithm which changes the code constructed by the extension algorithm into an optimal code in case it is not already optimal.The validity of the combined algorithm is proved and its structure is analyzed.The analysis leads to further improvement of the algorithm's efficiency.It is shown that the number of steps required is at mnst O(r.n.log n), if a heap data structure is used Alternatively, one can use a data structure of r queues, in which case the number of steps is bounded by O(r.n).