Back to search

University of Ioannina

Efficient storage indexing of structured and unsructured data

Abstract

dc:description

Commercial and public organizations currently strive to manage massive amounts of structured and unstructured data in all fields of society. The data collected across different local and online services, such as news websites, social media, mail servers and file systems, is inherently semi-structured or unstructured. Therefore, effective text indexing and search is crucial for data usability and exploration. Moreover, the exploding amount of structured data that needs to be managed and the demanding workloads that include both throughput-oriented batch jobs and latency-sensitive data serving drive the development of horizontally-expandable, distributed storage systems, called scalable datastores. In this thesis, we study the analysis, design, and implementation of storage systems to efficiently store, access, and search both structured and unstructured data.Real-time text search requires to incrementally ingest content updates and make them searchable almost immediately, but also serve search queries at low latency. Recent methods for incremental index maintenance substantially increase search latency with the index fragmented across multiple disk locations. For the support of fast indexing and search over disk-based storage, we introduce a method called Selective Range Flush (SRF). We organize the disk index over blocks, which allow to selectively update only the parts of the index that can be efficiently updated based on SRF. We show that SRF reduces the indexing time, but requires substantial experimental effort to tune specific parameters for performance efficiency. Subsequently, we propose the Unified Range Flush (URF) method, which is conceptually simpler than SRF, achieves similar or better performance with fewer parameters and less tuning, and is amenable to I/O complexity analysis. We implement the two methods in the Zettair open-source search engine, using carefully optimized storage and memory management. Then, we do extensive experiments with three different web datasets of size up to 1TB. Across different open-source systems, we show that our methods offer search latency that matches or reduces up to half the lowest achieved by existing disk-based methods. In comparison to an existing method of comparable search latency on the same system, our methods reduce by a factor of 2.0-2.4 the I/O part of build time, and by 21-24% the total build time.Scalable datastores are required to manage enormous amounts of structured data for online serving and analytics applications. Across different workloads, they weaken the relational and transactional assumptions of traditional databases to achieve horizontal scalability and availability, and meet demanding throughput and latency requirements. Efficiency tradeoffs at each storage server often lead to design decisions that sacrifice query responsiveness for higher insertion throughput. In order to address this limitation, we introduce the Rangetable storage structure and Rangemerge method so that we efficiently manage structured data in granularity of key ranges. We develop both a general prototype framework and a storage system based on Google's LevelDB open-source key-value store. In these two platforms, we implement several representative methods as plugins to experimentally evaluate their performance under common operating conditions. We conclude that our approach incurs range-query latency that is minimal and has low sensitivity to concurrent insertions, while it achieves insertion performance that approximates that of write-optimized methods under modest query load. Our method also reduces down to half the reserved disk space, improves the write throughput proportionally to the available main memory, and naturally exploits the key skewness of the inserted dataset.

Degree

thesis:*
Grantor dc:publisher
University of Ioannina
Year dc:date
2014

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Margaritis, Giorgos
  • Μαργαρίτης, Γεώργιος

Subjects

dc:subject × 24

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/37421

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Margaritis, Giorgos; Μαργαρίτης, Γεώργιος. Efficient storage indexing of structured and unsructured data. University of Ioannina, 2014. http://hdl.handle.net/10442/hedi/37421