Efficient Queries of Stand-off Annotations for Natural Language Processing on Electronic Medical Records.
In natural language processing, stand-off annotation uses the starting and ending positions of an annotation to anchor it to the text and stores the annotation content separately from the text. We address the fundamental problem of efficiently storing stand-off annotations when applying natural lang...
| Publicado en: | Biomedical Informatics Insights no. 8; pp. 29 - 39 |
|---|---|
| Autores principales: | , |
| Formato: | equations & formulas pictorial tables/charts Journal Article |
| Publicado: |
Sage Publications Inc.
2016
|
| Acceso en línea: | Ver este registro en EBSCOhost |
| fields | @attributes: recordID: 1 pdfLink: plink: https://search.ebscohost.com/login.aspx?direct=true&db=ccm&AN=118546794&site=ehost-live header: @attributes: shortDbName: ccm uiTerm: 118546794 longDbName: CINAHL Complete uiTag: AN controlInfo: bkinfo: dissinfo: jinfo: jid: 11782226 B077 jtl: Biomedical Informatics Insights issn: 11782226 maglogo: Y pubinfo: dt: 2016 iid: 8 pid: 344 pub: Sage Publications Inc. place: Thousand Oaks, California artinfo: ui: 118546794 118546794 118546794 10.4137/BII.s38916 118546794 ppf: 29 ppct: 10 formats: fmt: @attributes: type: P tig: atl: Efficient Queries of Stand-off Annotations for Natural Language Processing on Electronic Medical Records. aug: au: Luo, Yuan Szolovits, Peter affil: Assistant Professor, Department of Preventive Medicine, Northwestern University, Chicago, IL, USA sug: subj: Natural Language Processing Electronic Health Records Clinical Exemplars Standing Algorithms ab: In natural language processing, stand-off annotation uses the starting and ending positions of an annotation to anchor it to the text and stores the annotation content separately from the text. We address the fundamental problem of efficiently storing stand-off annotations when applying natural language processing on narrative clinical notes in electronic medical records (EMRs) and efficiently retrieving such annotations that satisfy position constraints. Efficient storage and retrieval of stand-off annotations can facilitate tasks such as mapping unstructured text to electronic medical record ontologies. We first formulate this problem into the interval query problem, for which optimal query/update time is in general logarithm. We next perform a tight time complexity analysis on the basic interval tree query algorithm and show its nonoptimality when being applied to a collection of 13 query types from Allen’s interval algebra. We then study two closely related state-of-the-art interval query algorithms, proposed query reformulations, and augmentations to the second algorithm. Our proposed algorithm achieves logarithmic time stabbing-max query time complexity and solves the stabbing-interval query tasks on all of Allen’s relations in logarithmic time, attaining the theoretic lower bound. Updating time is kept logarithmic and the space requirement is kept linear at the same time. We also discuss interval management in external memory models and higher dimensions. pubtype: Academic Journal doctype: equations & formulas pictorial tables/charts Journal Article ougenre: Article language: English refInfo: holdings: @attributes: islocal: N |
|---|