Back to search

Athens University Economics and Business (AUEB)

Similarity computation in modern applications

Abstract

dc:description

Computing the similarity between data items is a fundamental operation in data management. The first part of the thesis proposes a technique that is utilized in distributed applications for computing the similarity between data descriptions that are streamed from remote sources. The proposed technique utilizes prior knowledge of the data distribution in order to produce, with the same space, more accurate descriptions than the Random Hyperplane Projection (RHP) method (i.e. a locality sensitive hashing method). We present algorithms that materialize RHP dimensions that better describe the underlying data, while additional dimensions are derived in real-time using simple stored statistics we maintain. Our method is resilient to data distribution changes because of a fail-safe mechanism that detects in real time cases where particular data instances cannot be accurately described using the selected dimensions. In such cases the method automatically falls-back into using the basic RHP scheme. The second part of this work introduces a novel user-centric approach for similarity computation between products. Unlike techniques that focus on product features our method takes into account users’ preferences by utilizing the recent concept of reverse top-k queries. In contrast to a top-k query that returns the k products with the best score for a specific customer, the result of a reverse top-k query is the set of customers(or their rankings) for whom a given product belongs to their top-k set. Two novel query types (θ-similarity and m-nearest neighbor) for user-centric similarity search are defined, while algorithms for efficient processing of these queries are also discussed. The presented algorithms prune the search space by identifying effective similarity bounds and exploit conventional multi-dimensional indexes for efficient query processing. In the third part of this thesis we address the problem of outlier detection in hierarchically organized data domains. Outlier detection is critical for modern applications such as decision support (OLAP) and network management. However, existing techniques do not take into consideration the hierarchical nature of the data domains that is inherent in such applications. The natural aggregation of atomic values along a domain hierarchy is an intuitive summarization technique that can be used to detect diferent grades of abnormal behavior by looking across all levels of the hierarchy. In this work, we first formally define the notion of a hierarchical outlier and describe an intuitive monotonicity property that permits us to rate an outlier with a single grade value. We then present a technique that combines locality sensitive hashing and clustering in order to index the data descriptions. The fusion of both techniques permits us to reduce the storage space for the index and the execution time for an outlier computation query.

Degree

thesis:*
Grantor dc:publisher
Athens University Economics and Business (AUEB)
Year dc:date
2017

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Georgoulas, Konstantinos
  • Γεωργούλας, Κωνσταντίνος

Subjects

dc:subject × 6

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/41418

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

Georgoulas, Konstantinos; Γεωργούλας, Κωνσταντίνος. Similarity computation in modern applications. Athens University Economics and Business (AUEB), 2017. http://hdl.handle.net/10442/hedi/41418