NASH: Range Search over Temporal, Numerical, and Geographical Annotated Documents

Abstract

Tekstdokumenter som nyhetsartikler og encyklopediartikler inneholder store mengder informasjon om ekte hendelser. Det er likevel en utfordring å kunne hente ut de mest relevante delene av informasjon fra millioner av større dokumenter. Semantikk kan trekkes ut som annoteringer av teksten ved å bruke Natural Language Processing (NLP) verktøy. Disse annoteringene kan inneholde entiteter som personer, organisasjoner, og lokasjoner, så vel som tidsmessige og numeriske uttrykk. For øvrig kan noen annotasjoner som beskriver numeriske, tidsmessige, og geografiske uttrykk representere usikker informasjon, for eksempel frasen “1990-tallet” som referer til et ti-års intervall. Denne oppgaven presenterer en tilnærmingsmetode for å støtte fulltekst semantisk søk over tekstdokumenter og deres ekstraherte annotasjoner, med mulighet for romlige restriksjoner på usikre annotasjoner. Dette presenteres som indekseringssystemet NASH. De annoterte dokumentene er lagret ved bruk av inverterte indekser som en del av en lagvis datamodell. Hvert lag representerer en annotasjonstype, mens alle lagene deler posisjonsinformasjon for toknene. For å effektivisere søking etter numeriske, tidsmessige, og geografiske uttrykk, reduseres uttrykkene til én dimensjon ved bruk av Z-ordenskurver, som oversetter de to-dimensjonale verdiene til en-dimensjonale hasjer. Hasjene lagres som en del av den lagvise indeksen for å tillate fulltekst semantisk søk med område-baserte søkemuligheter. Forskjellige optimeringsmetoder brukes for å gjøre de område-baserte spørringene mer effektive over Z-ordenskurven. Systemet evalueres ved å bruke et sett av semantiske intervall-spørringer over numeriske og tidsmessige annotasjoner, og måler tiden det tar fra spørringskonstruksjon til listen av treff er mottatt. Spørringene kjøres med forskjellige konfigurasjoner av intervallstørrelse og søkepresisjon over tre annoterte dokumentsamlinger av forskjellige størrelser. Resultatene demonstrerer et funksjonelt system og indikerer at system skalerer godt med økende størrelse på samlingene. Små forskjeller i treffstørrelser og kjøretid mellom nivåer av søkepresisjon, indikerer at optimaliseringene for intervallsøket fungerer bra, med et lite tap av presisjon mens treffandelen til søket økes.

Text documents such as news and encyclopedia articles contain tremendous amounts of information about real-world events. However, there is a challenge to extract the most relevant snippets of information from millions of lengthy documents. Semantics can be extracted as annotations from the text using Natural Language Processing tools. These annotations can contain entities such as persons, organizations, and locations, as well as temporal and numerical expressions. Moreover, some annotations describing numerical, temporal, and geographical expressions can represent uncertain information, e.g., the phrase “1990s” referring to a ten-year interval. This thesis presents an approach to support full-text semantic search over text documents and their extracted annotations, with capabilities of spatial restrictions on the uncertainty-aware interval annotations. This is presented as the indexing system NASH. The annotated documents are stored using inverted indexes in a layered data model. Each layer represents one annotation type, and all layers share the positional information of the tokens. To support efficient retrieval, the numerical, temporal, and geographical expressions are reduced to one dimension by using Z-order curves, which translate the two-dimensional values into one-dimensional hashes. These hashes are stored as part of the layered index to allow for full-text semantic search with spatial query capabilities. Different optimizations are implemented to make the range-based queries over the Z-order curves more efficient. The system is evaluated using a set of semantic range queries, measuring the time used from query creation to the posting list retrieval. The queries are executed using different configurations of range sizes and search precision over three annotated document collections of differing sizes. The results demonstrate a functioning system and indicate that the system scales well with increasing collection sizes. Slight differences in result-set sizes and execution times between levels of search precision indicate that the range search optimizations are working well, with a small loss of precision, while increasing recall of the search.