Back to results

National Technical University of Athens (NTUA)

Αποδοτική αναζήτηση με χρήση λέξεων - κλειδιών σε ημιδομημένα δεδομένα

Abstract

dc:description

Keyword search is the most popular querying technique on large semistructured datasets, often of unknown structure, in the web. Keyword queries are simple and convenient. However, as a consequence of their imprecision, there is usually a huge number of candidate results of which only very few match the user's intent. Unfortunately, the existing semantics for keyword queries are ad-hoc and they generally fail to ``guess'' the user intent. Therefore, the quality of their answers is poor and the existing algorithms do not scale satisfactorily.In this context, three challenging problems are (a) to avoid missing useful results in the answer set, (b) to rank the results with respect to some relevance criterion and (c) to design algorithms that can efficiently compute the results on large datasets. A major challenge of a ranking approach is the efficiency of its algorithms as the number of keywords and the size and complexity of the data increase. To face this challenge most of the known approaches restrict their ranking to a subset of the LCAs (e.g., SLCAs, ELCAs), missing relevant results.In this thesis, we present a novel ranking semantics for keyword queries which is based on the concept of LCA size. Similarly to metric selection in Information Retrieval, LCA size reflects the proximity of keyword matches in the data tree. This semantics does not rank a predefined subset of LCAs and through a layered presentation of results, it demonstrates improved effectiveness compared to previous relevant approaches. To address performance challenges, we design novel stack-based algorithms, which exploit a lattice of the partitions of the keyword set to return, as an answer to a keyword query, all the results ranked on their size. This feature empowers a linear time performance on the size of the input data for a given number of query keywords. As a result, our algorithm can run efficiently on large input data for several keywords. We extend our approach to efficiently support top-k keyword query answering, with new top-k-size semantics. An extensive experimental study on various and large datasets confirms the theoretical analysis. The results show that, in contrast to other approaches, our algorithms scale smoothly when the size of the dataset and the number of keywords increase.Furthermore, we present a multi-level clustering methodology which groups together results with similar structural and semantic features, and allows the user to focus on a small subset of the results. In order to define our cluster hierarchy, we exploit homomorphisms between label paths which allow the detection of commonalities between patterns of results. An originality of our approach is that the clusters are ranked at different levels of granularity to quickly guide the user to the relevant result patterns. We design an efficient stack-based algorithm for generating result patterns and constructing the clustering hierarchy. Our extensive experimentation with multiple real datasets shows that our algorithm is fast and scalable. It is also shown that our clustering methodology allows the users to effectively retrieve their intended results, and outperforms a recent state-of-the-art clustering approach. Although keyword queries are simple and convenient, the existing semantics for keyword queries are prone to failure on ``guessing'' the user intent. Therefore, the quality of the answers is often poor. To address this issue, we introduce the novel concept of cohesive keyword queries for tree data. Intuitively, a cohesiveness relationship on keywords indicates that they should form a cohesive whole in a query result. Cohesive keyword queries allow term nesting and keyword repetition. They bridge the gap between flat keyword queries and structured queries. Although more expressive, they are as simple as flat keyword queries and they do not require any schema knowledge. We provide formal semantics for cohesive keyword queries and rank query results on the proximity of the keyword instances. We design a stack based algorithm which efficiently evaluates cohesive keyword queries. Our experiments demonstrate that our approach outperforms in quality previous filtering semantics and our algorithm scales smoothly on queries of even 20 keywords on large datasets.

Degree

thesis:*
Grantor dc:publisher
National Technical University of Athens (NTUA)
Year dc:date
2016

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Dimitriou, Aggeliki
  • Δημητρίου, Αγγελική

Subjects

dc:subject × 19

Rights

Language dc:language
gre

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/38536

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

Dimitriou, Aggeliki; Δημητρίου, Αγγελική. Αποδοτική αναζήτηση με χρήση λέξεων - κλειδιών σε ημιδομημένα δεδομένα. National Technical University of Athens (NTUA), 2016. http://hdl.handle.net/10442/hedi/38536